Abstract:

Introduction

Figure 1: A polygon set with four contours.

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.

 
 
Figure 2: Difference, intersection, exclusive-or and union operations.

Recent API changes

• An additional hole field in the gpc_polygon datatype to differentiate hole contours from external contours.
• A similar additional hole parameter to gpc_add_contour().
• An extra parameter in the gpc_read_polygon() and gpc_write_polygon() functions to specify the polygon datafile format (with or without hole contour flags).

Data types

          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;

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;

Library functions

          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);

    <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.0

          void gpc_add_contour(gpc_polygon     *p,
                               gpc_vertex_list *c,
                               int              hole);

          void gpc_polygon_clip(gpc_op       operation,
                                gpc_polygon *subject_p,
                                gpc_polygon *clip_p,
                                gpc_polygon *result_p);

          void gpc_tristrip_clip(gpc_op        operation,
                                 gpc_polygon  *subject_p,
                                 gpc_polygon  *clip_p,
                                 gpc_tristrip *result_t);

 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);

          void gpc_free_polygon(gpc_polygon *p);

          void gpc_free_tristrip(gpc_tristrip *t);

Hole and external contours

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.

Associating holes with external contours

Coincident and near-coincident edges

A code example

          #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;
          }

Known bugs

Non-serious

Tristrip and polygonal output forms will not always be optimal in minimising triangle or vertex counts.

Release notes

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 gpc@cs.man.ac.uk.

See the VERSIONS.TXT file for a revision history.

References

[1]

Vatti, B.R., "A Generic Solution to Polygon Clipping", Communications of the ACM, 35(7), July 1992, pp.56-63.