## 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":

This approach ensures robustness of intersection, since there's always a unique representation of the output polygon (as opposed to doing polygon intersection on floating point numbers where due to numerical precision, intersection points might now have an actual representation as floating point number, leading to errors when they are "rounded" to a float.)

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