Clockwise Sweep: More accurate and faster intersect of Circle with Polygon

[caewok]

Environment Details

• Foundry VTT Version: 10.270

Issue Description

Currently, ClockwiseSweep uses Circle.toPolygon to construct a polygon from the limited radius circle and then intersects that polygon against the sweep polygon. This is less than ideal in terms of speed (because a polygon representation of a circle has a lot of edges) and accuracy (because the intersection points will not be as precise as they could be if the circle was intersected directly.

Proposed Solution

Use a different algorithm (a "tracing" algorithm) to intersect a circle with a polygon in limited cases. Requirements:

1. The polygon is convex or
2. The polygon is concave (i.e., does not intersect itself or contain holes) and the polygon and circle share a common weighted center point such that the intersection will result in a single polygon. For example, if you have a "C" shaped polygon, it is possible to intersect it with a circle such that you get one polygon or two, depending on where the circle overlaps the "C".

Requirement 2 occurs naturally when dealing with the sweep polygon, because that polygon is constructed from an origin point that is also the center of the limited radius circle. It is possible to deal with all concave polygons by modifying the algorithm, described below.

Tracing Algorithm

The basic tracing algorithm: Pretend you are tracing over the shapes in order to draw the intersect of them. You are only allowed to draw clockwise around either shape. Start by tracing the polygon by drawing along it in a clockwise direction. At each intersection with the other shape, turn clockwise (right) (to form the intersect) or counterclockwise (left) (to form the union). Repeat at each intersection. The traced object will be the intersection or union of the polygon with the shape. (This is easier to draw than to describe, and so I encourage you to draw a few examples on paper.)

This works particularly well for a circle shape because (a) there are likely few intersections; (b) intersection points can be defined precisely using foundry.util.lineCircleIntersection; and (c) we can easily get all the points that approximate a circle between two intersection points.

I have a generic implementation that handles unions and intersections for any polygon with any other polygon, circle, rectangle, or limited angle shape. But of those shapes, circle has the most benefit (as would an ellipse, for the same reasons). Polygon intersecting polygon is slower than clipper in most cases. The other shapes depend on layout but are probably not worth it if you wanted to implement a less generic version. Clipper2 is likely to improve this such that only circles and ellipses would probably be worth it.

For a polygon-circle intersection, the basic steps are:

1. Identify all the intersection points of the polygon and circle. Order them clockwise, in the sense that as you trace the polygon clockwise, you will encounter the intersection points in order.
2. At the first intersection, determine whether a clockwise turn will put you on the circle or the polygon. Go in the desired direction (for intersect, clockwise). Note whether you are now tracing the polygon or the circle. (For circles, if the intersecting polygon edge ends inside the circle, then following that edge into the circle will be the clockwise turn to form the intersect.)
3. At each subsequent intersection:

• Determine if you should switch to the other shape at the intersection. Again, it is a question of whether turning to the other shape will be a clockwise turn or not. Another way to think about it, however, is whether the shapes cross at the intersection. If they do in fact cross (most of the time), then you should switch from one shape to the other.
• If you in fact switch shapes at this intersection, fill in the points between the previous intersection and this one. For the polygon, this means the B endpoints of each edge between. For a circle, this means what ClockwiseSweep used to call paddingPoints---endpoints of a set of lines approximating the arc of the circle between the two intersections.

4. Repeat (3) until back at the first intersection. Be sure to fill padding if needed for that last iteration.

It is possible to use this algorithm in cases where the polygon/shape intersect will result in multiple polygons. The catch is that you have to run it from each intersection separately because you will get only one of the multiple resulting polygons depending on what intersection you begin.

[aaclayton]

De-prioritizing from V10 until after we get clipper2 integrated (once its ready) and we can re-evaluate the tradeoff here.

[aaclayton]

Closing, this was done in V11P1