WIP: Add CircularArcIntersector

[dbaston]

This PR adds a CircularArcIntersector that computes intersections between circular arcs and/or line segments. The intersections may be points or arcs. The interface generally mimics that of the LineIntersector.

Missing features:

Use of a PrecisionModel Handling of Z, M isProper() isInteriorIntersection()

A challenge I ran into when writing test cases is the lossy conversion between how arcs are stored (three points) and how we generally must work with them (a center point, radius, two angles). This can cause small differences in the computed center point, which currently prevents the code from recognizing the arcs as co-circular. It may be necessary to add some tolerance in the center-point equality testing, possibly by using the scale of a provided PrecisionModel.

[pramsey]

Is there a similar tolerance issue around arcs with infinite radius (aka straight lines (aka three control points in a line))?

[dbaston]

Is there a similar tolerance issue around arcs with infinite radius (aka straight lines (aka three control points in a line))?

Good point. See the final (failing) test added in https://github.com/libgeos/geos/pull/1171/commits/9910456b3acc5be3fd651f65d7fdcb6de8e65158.

[dbaston]

A couple of recent notes on this:

1. I plugged in the following robust quadratic equation solver: https://github.com/archermarx/quadratic . It did not help with failing CircularArcIntersector test 40, but may be worthwhile nonetheless.

2. I ported CircularArcIntersector test 40 into https://github.com/claeis/iox-ili, where it passed (intersection point computed with an error of 2.5e-10). So it may be valuable to study that implementation. I also ported additional tests from iox-ili into GEOS.

[pramsey]

I feel like for the degenerate arcs it is totally fine to have a big hammer, which says something like if the ratio of the distance between end points and radius is small enough, it's actually linear. Or the ratio of the distance between the control point and the end points and the distance between end points. Too small? That's just plain invalidity. I guess the downside is starting every arc computation with a litany of conformance checks.

[dbaston]

Yes, I have to remind myself that the baseline is linearizing everything, and we're clearly doing better than that. Test 40 isn't a catastrophic failure in any case, it's just that the computed point is outside the arbitrary tolerance.

[dbaston]

Current status of this: tests passing except for:

• CircularArcIntersector test 40 - the computed intersection point is outside the arbitrary distance tolerance
• CircularArcIntersector 42 and 53. These relate to arcs that intersect at an endpoint. In both cases the computed intersection points (incorrectly) do not fall on the input arcs. We probably need some special logic for endpoint intersections, as is the case for linear segment intersection.

I think it is mergeable as-is; it is not accessible though the C API, and we can return to it later to improve robustness after more of the curve integration is completed. Thoughts, @pramsey ?

[pramsey]

Yes, merge it so it can be worked on in core.