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.
The largest number of vertices a polygon can have in this library.
We have to consider floating point round-off errors when dealing with
polygons. For example we will take
A as the maximum of
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
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
ordinds array. Such that calling the input coordinates in the
following fashion will give an anti-clockwise order when there are 4
1st vertice: in[ordinds*2], in[ordinds*2+1] 2nd vertice: in[ordinds*2], in[ordinds*2+1] 3rd vertice: in[ordinds*2], in[ordinds*2+1] 4th vertice: in[ordinds*2], in[ordinds*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.
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.
Find the area of a polygon with vertices defined in
points to an array of doubles which keep the positions of the vertices such
v are the positions of the first vertice to
1 if the point
p is within the polygon whose vertices
are defined by
0 otherwise. Note that the vertices of
the polygon have to be sorted in an anti-clock-wise manner.
gal_polygon_pin, except that if the point
p is on
one of the edges of a polygon, this will return
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.