Module planar 

Regions of the plane bounded by weighted chains of segments, found robustly: the engine under shadow and the outline fit’s offsets.

A set of directed segments with integer weights, closed as a chain (at every point the weights in equal the weights out), gives every point off the segments a winding count: the weights of the segments a ray from it crosses, from right to left minus from left to right. region returns the boundary of the points whose counts a rule accepts. Two independent counts are carried, so a rule can take a difference as well as a union.

Every decision is exact. The endpoints are first snapped to a grid of 2^-38 of the chain’s extent, a power of two, and from then on every coordinate is an integer and every test is integer arithmetic: the orientation of three points, where two segments cross, whether a segment meets a grid cell. The crossings are resolved by snap rounding: every cell holding an endpoint or a crossing is hot, and every segment is replaced by the path through the centres of the hot cells it meets, in the order it meets them. The paths cross nowhere but at shared centres, each moved by at most sqrt(2)/2 of a cell from its segment, and a segment’s path starts and ends where the segment does, so the chain stays closed and every count stays defined.

The paths are then the constraints of a triangulation. A count changes across a constraint by its weight and across nothing else, so one walk from the unbounded face, whose counts are zero, gives every triangle’s counts. The boundary is every triangle edge with an accepted triangle on its left and a rejected one on its right, linked into loops by turning through accepted triangles only, so two loops touching at a corner come out as two loops. Points where a loop runs straight on are dropped.

Structs

Edge2

A directed segment of a chain, with its weight in each of the two counts.

Loop2

One closed loop of a region’s boundary.

Functions

region

The boundary of the points whose winding counts inside accepts.