Polygon representation

Polygons in gfxpoly are represented as a set of line segments. The internal representation doesn't have a way to represent curves (splines), however it's possible to convert splines to a gfxpoly structure by approximating them with lines (See creating polygons.)

Polygon endpoints, furthermore, are rounded to a grid (i.e., represented as integer coordinates.)
During polygon intersection, the resulting polygons are again rounded- also, new intersection points will cause adjacent lines (i.e. lines passing through that grid point) to be "routed" through the intersection point, a concept known as "snap rounding to hot pixels":

There are a lot of academic papers about why snap rounding is preferrable to numeric approaches. gfxpoly uses the algorithm from Hobby with a few additional ideas from Hershberger and Bhattacharya et al.

(In the above figure, you might have noticed that gfxpoly snaps to the lower right corner of grid points, instead of the center- this is an optimization that makes snapping faster)

Creating polygons

The easiest way to create a gfxpoly polygon is to first represent the shape you want to process as an outline of lines and splines:

double gridsize = 0.01;

gfxline_t*outline = NULL;
outline = gfx_moveTo(outline, 0,0);
outline = gfx_lineTo(outline, 100,0);
outline = gfx_lineTo(outline, 100,100);
outline = gfx_splineTo(outline, 50,50, 0,100);
outline = gfx_lineTo(outline, 0,0);

gfxpoly_t*poly = gfxpoly_from_fill(outline, gridsize);

Here, gridsize is the spacing of grid points- i.e., the numerical precision of your coordinate system. So a coordinate like 7.392 will be truncated to 7.39 during conversion to gfxpoly_t (and since gfxpoly_t represents coordinates as integers, be internally stored as 739.)

You can also create polygons from a stroke:

gfxpoly_t*poly = gfxpoly_from_stroke(outline, /*line width*/10.0, gfx_capRound, gfx_joinRound, 0.0, gridsize);

The parameters are defined as following:

Boolean operations between polygons

Once you have a representation of your polygon as gfxpoly you can intersect polygons:

gfxpoly_t*poly12 = gfxpoly_intersect(poly1, poly2);

You can also build the union of two polygons:

gfxpoly_t*poly12 = gfxpoly_union(poly1, poly2);

It also sometimes makes sense to intersect a polygon with itself (for example, to determine which parts of it are filled.)
There are two convenience functions that apply the corresponding fillstyle and generate a self-intersected polygon:

gfxpoly_t* new_polygon = gfxpoly_selfintersect_evenodd(poly);

gfxpoly_t* new_polygon = gfxpoly_selfintersect_circular(poly);

Notice: gfxpoly_intersect, gfxpoly_union and gfxpoly_selfintersect_* are really just convenience wrappers for gfxpoly_process. See gfxpoly_process.
By using gfxpoly_process directly, you can implement other polygon operations, like symmetric difference, overlay, transparency etc.

Polygon area and moments

You can also compute the area of a polygon:

double area = gfxpoly_area(poly);

If you're interested in the degree of overlap between two polygons, there's a shortcut that does gfxpoly_intersect and gfxpoly_area in a single step:

double area = gfxpoly_intersection_area(poly1, poly2);

Advanced

Creating gfxpoly through gfxcanvas

Representing polygons as a gfxline_t list first has the disadvantage of having to allocate that structure first. A faster way is to use the gfxcanvas_t abstraction to convert a shape to a gfxpoly on the fly:

gfxcanvas_t*canvas = gfxcanvas_new(gridsize);
canvas->moveTo(canvas, 0,0);
canvas->lineTo(canvas, 100,0);
canvas->lineTo(canvas, 100,100);
canvas->splineTo(canvas, 50,50, 0,100);
canvas->lineTo(canvas, 0,0);
canvas->close(canvas);
gfxpoly_t* poly = (gfxpoly_t*)canvas->result(canvas);

This also has the advantage that you can overlay multiple input polygons using the same gfxcanvas object, and then later process them in one go. Use canvas->setUserData(canvas, data) to store polygon-specific data. This data will later be passed back to you by windrule.add().

gfxpoly_process

Internally, for every polygon operation, a scanline pass is run over all the line segments using gfxpoly_process. It has the following prototype:

gfxpoly_t* gfxpoly_process(gfxpoly_t*poly1, gfxpoly_t*poly2, 
                           windrule_t*windrule, windcontext_t*context, 
			   moments_t*moments);

To implement custom polygon operations, you would create your own windcontext. To understand how this works, we need to talk about scanline algorithms first.
A scanline algorithm processes a set of line segments from top to bottom (or left to right, depending on the implementation), and during every scanline, shoots an imaginary ray from negative infinity to positive infinity, looking at which polygon segments it hits, and in which order:

The state of the ray is represented as a windstate_t structure- it e.g. stores whether the current polygon area we're in is filled or not, or how many polygons are currently on top of each other.

A windrule_t structure specifies what should happen to the windstate_t every time we pass through an edge, it's initial value (at negative infinity) and also, when generating the output polygon, what kind of edge to place between two different windstate_t areas.

An edgestyle_t structure is attached to every edge, and can store user data that applies to that edge (e.g. for polygon overlays, the color of the polygon belonging to that edge.)

Hence, for creating your own windrule, you have to implement the following functions:

windstate_t start(windcontext_t*context);
windstate_t add(windcontext_t*context, windstate_t left, edgestyle_t*edge, segment_dir_t dir, int polygon_nr);
edgestyle_t* diff(windstate_t*left, windstate_t*right);

winrules / fillstyles

gfxpoly already contains windrule (a.k.a. fillstyle) implementations for:

• Even/Odd self-intersection (windrule_evenodd)
• Circular self-intersection (windrule_circular)
• Two polygon intersection (windrule_intersect)
• Two polygon union (windrule_union)