GNU Astronomy Utilities


Next: , Previous: , Up: Gnuastro library   [Contents][Index]


10.3.15 Polygons (polygon.h)

Polygons are commonly necessary in image processing. In Gnuastro, they are used in Crop (see Crop) for cutting out non-rectangular regions of a image. Warp (see Warp) uses them to warp the images into a new pixel grid. The polygon related Gnuastro library macros and functions are introduced here.

In all the functions here the vertices (and points) are defined as an array. So a polygon with 4 vertices will be identified with an array of 8 elements with the first two elements keeping the 2D coordinates of the first vertice and so on.

Macro: GAL_POLYGON_MAX_CORNERS

The largest number of vertices a polygon can have in this library.

Macro: GAL_POLYGON_ROUND_ERR

We have to consider floating point round-off errors when dealing with polygons. For example we will take A as the maximum of A and B when A>B-GAL_POLYGON_ROUND_ERR.

Function:
void
gal_polygon_ordered_corners (double *in, size_t n, size_t *ordinds)

We have a simple polygon (that can result from projection, so its edges don’t collide or it doesn’t have holes) and we want to order its corners in an anticlockwise fashion. This is necessary for clipping it and finding its area later. The input vertices can have practically any order.

The input (in) is an array containing the coordinates (two values) of each vertice. n is the number of corners. So in should have 2*n elements. The output (ordinds) is an array with n elements specifying the indexs in order. This array must have been allocated before calling this function. The indexes are output for more generic usage, for example in a homographic transform (necessary in warping an image, see Warping basics), the necessary order of vertices is the same for all the pixels. In other words, only the positions of the vertices change, not the way they need to be ordered. Therefore, this function would only be necessary once.

As a summary, the input is unchanged, only n values will be put in the ordinds array. Such that calling the input coordinates in the following fashion will give an anti-clockwise order when there are 4 vertices:

1st vertice: in[ordinds[0]*2], in[ordinds[0]*2+1]
2nd vertice: in[ordinds[1]*2], in[ordinds[1]*2+1]
3rd vertice: in[ordinds[2]*2], in[ordinds[2]*2+1]
4th vertice: in[ordinds[3]*2], in[ordinds[3]*2+1]

The implementation of this is very similar to the Graham scan in finding the Convex Hull. However, in projection we will never have a concave polygon (the left condition below, where this algorithm will get to E before D), we will always have a convex polygon (right case) or E won’t exist!

            Concave Polygon        Convex Polygon

             D --------C          D------------- C
              \        |        E /              |
               \E      |          \              |
               /       |           \             |
              A--------B             A ----------B

This is because we are always going to be calculating the area of the overlap between a quadrilateral and the pixel grid or the quadrilateral its self.

The GAL_POLYGON_MAX_CORNERS macro is defined so there will be no need to allocate these temporary arrays separately. Since we are dealing with pixels, the polygon can’t really have too many vertices.

Function:
double
gal_polygon_area (double *v, size_t n)

Find the area of a polygon with vertices defined in v. v points to an array of doubles which keep the positions of the vertices such that v[0] and v[1] are the positions of the first vertice to be considered.

Function:
int
gal_polygon_pin (double *v, double *p, size_t n)

Return 1 if the point p is within the polygon whose vertices are defined by v and 0 otherwise. Note that the vertices of the polygon have to be sorted in an anti-clock-wise manner.

Function:
int
gal_polygon_ppropin (double *v, double *p, size_t n)

Similar to gal_polygon_pin, except that if the point p is on one of the edges of a polygon, this will return 0.

Function:
void
gal_polygon_clip (double *s, size_t n, double *c, size_t m, double *o, size_t *numcrn)

Clip (find the overlap of) two polygons. This function uses the Sutherland-Hodgman polygon clipping algorithm. Note that the vertices of both polygons have to be sorted in an anti-clock-wise manner.


Next: , Previous: , Up: Gnuastro library   [Contents][Index]