Alan Murta
Advanced Interfaces Group
Department of Computer Science
University of Manchester
Manchester M13 9PL, UK
Figure 1 shows a polygon set comprised of four contours. Over to the left is a seven sided concave contour. Lying completely within it is a four-sided contour, which forms a hole in the surrounding shape. A third, triangular contour intersects the boundary of the first. Finally, over to the right is a disjoint self-intersecting four-sided contour. The interior of the polygon has been shaded for clarity.
The library supports four kinds of clipping (Boolean set) operation: difference, intersection exclusive-or or union of subject and clip polygon pairs. These are illustrated in Figure 2. In each case, the (single) resulting polygon is shown shaded.
typedef struct /* Polygon vertex */ { double x; double y; } gpc_vertex; typedef struct /* Polygon contour */ { int num_vertices; gpc_vertex *vertex; } gpc_vertex_list; typedef struct /* Polygon set */ { int num_contours; int *hole; gpc_vertex_list *contour; } gpc_polygon;The clipper takes a pair of subject and clip polygons and combines them to form a result polygon. For each contour polygon in the result polygon, the hole value flags whether or not the given contour forms a hole or an external boundary.
Alternatively a collection of tristrips may be generated as the result, this form being more suitable for rendering filled shapes. (The polygon result form is better for drawing outlines, or as intermediate values in multi-clip operations.) Tristrip collections are represented using the following data type:
typedef struct /* Set of tristrips */ { int num_strips; gpc_vertex_list *strip; } gpc_tristrip;
void gpc_read_polygon(FILE *fp, int read_hole_flags, gpc_polygon *polygon); void gpc_write_polygon(FILE *fp, int write_hole_flags, gpc_polygon *polygon);A polygon is stored in an ASCII file using the format:
<num-contours>
<num-vertices-in-first-contour>
[<first-contour-hole-flag>]
<vertex-list>
<num-vertices-in-second-contour>
[<second-contour-hole-flag>]
<vertex-list>
etc. The hole-flag values are optional, their reading and writing being controlled by setting the second argument of gpc_read_polygon() and gpc_write_polygon() to 1 (TRUE) or 0 (FALSE). Clip operations will correctly set the contour hole flags of the result polygon. This information may be ignored by the user application if it is not required.
For example, a single polygon consisting of a triangular hole within a quadrilateral (with hole flags included) may take the form:
2 3 1 4.0 4.0 6.0 5.0 5.0 6.0 4 0 2.0 1.0 8.0 2.0 7.0 9.0 1.0 7.0An interactive drawing program may require the ability to construct a polygon contour-by-contour in an incremental fashion. The function gpc_add_contour() facilitates the merging of a new contour with an existing polygon. The final parameter has the value 1 (TRUE) or 0 (FALSE), and indicates whether or not the contour should be considered to be a hole. It is suggested that all contours are initially treated as non-hole (external) contours. Any subsequent clipping operation will set the result polygon hole flags correctly.
void gpc_add_contour(gpc_polygon *p, gpc_vertex_list *c, int hole);The clipping operation itself is performed by the function
void gpc_polygon_clip(gpc_op operation, gpc_polygon *subject_p, gpc_polygon *clip_p, gpc_polygon *result_p);or, if a tristrip based result is required
void gpc_tristrip_clip(gpc_op operation, gpc_polygon *subject_p, gpc_polygon *clip_p, gpc_tristrip *result_t);In both cases the first parameter specifies the clip operation to be performed (namely GPC_DIFF, GPC_INT, GPC_XOR or GPC_UNION). This is followed by subject and clip polygon parameters. The final parameter delivers the result, either as a polygon structure or as a collection of tristrips.
A polygon may be converted to the equivalent tristrip form using the function
void gpc_polygon_to_tristrip(gpc_polygon *source_p, gpc_tristrip *result_t);Finally, the functions
void gpc_free_polygon(gpc_polygon *p); void gpc_free_tristrip(gpc_tristrip *t);may be used to release the memory taken up by a polygon or trapezoid on the heap.
When contour edges cross (in self intersecting shapes for example) the clipper will always generate a local maximum vertex below the intersection (or when one of the edges is horizontal, to the left of the intersection) which connects the two edge parts which meet at the intersection point from below or from the left. The edge parts which emerge from the opposite side of the intersection point originate from a new local minimum vertex. The closed contours generated by the clipper will never self-intersect.
Figure 3: Self-intersecting contours which decompose into an external contour containing a nested hole contour.
These rules have implications with regard to how self intersecting shapes decompose into a set of closed, non-intersecting contours. The intersecting square examples of Figure 3, will each create two nested contours. In each case, the upper / rightmost maximum vertex of the internal contour forms an internal maximum, therefore the contour is classed as a hole (shown dotted). The corresponding outer contour is considered external as it terminates with an external maximum vertex.
Figure 4: Self-intersecting contours which decompose into two touching external contours.
The examples of Figure 4, however, show how similar self intersecting shapes may each create two external contours which touch at the points of intersection. In summary, the contour paths generated by the clipper are affected not only by the shape of the input polygons, but also by their orientation.
#include <stdio.h> #include "gpc.h" int main(void) { gpc_polygon subject, clip, result; FILE *sfp, *cfp, *ofp; sfp= fopen("subjfile", "r"); cfp= fopen("clipfile", "r"); gpc_read_polygon(sfp, 0, &subject); gpc_read_polygon(cfp, 0, &clip); gpc_polygon_clip(GPC_INT, &subject, &clip, &result); ofp= fopen("outfile", "w"); gpc_write_polygon(ofp, 0, &result); gpc_free_polygon(&subject); gpc_free_polygon(&clip); gpc_free_polygon(&result); fclose(sfp); fclose(cfp); fclose(ofp); return 0; }
You may not use this software, in whole or in part, in support of any commercial product without the express consent of the author.
There is no warranty or other guarantee of fitness of this software for any purpose. It is provided solely "as is". Although no direct support for the use of this software will be given, bug reports may be sent to toby.howard@manchester.ac.uk.
See the VERSIONS.TXT file for a revision history.