overlay: Minkowski sum and erosion of a mid-size region by a convex shape in time near linear in its corners #344

Reported by axioval/engine (engine#427), against axiolid-overlay 0.3.19.

Case

• Calls: Region::minkowski_sum(ring) and minkowski_erosion of an obstacle region with 150–300 corners (tessellated furniture), by an axis-aligned rectangle of about 1.7 m.
• Time: each call takes 30–120 ms. One free-floor rectangle search needs 10–100 of them, which comes to about 1,200 s of thread time across one check of a real model.
• Profile: dominated by exact_arc::arrangement::build, point::sign, BigInt/Dyadic arithmetic, and about 20 % malloc/free.

Cause, to verify

minkowski.rs puts one hull e + K per boundary edge into a single ArcArrangement. With a shape far larger than the region's features, every hull overlaps nearly every other one, so the crossings, and the exact arithmetic on them, grow with the square of the corners. #292 made reading the faces cheap and #323 trimmed the hulls along walls of collinear and short edges, but neither helps when the hulls overlap because the shape is large.

Needed

• A sum whose cost depends on its output for a convex K, for example the reduced convolution: pair each boundary edge of R only with the vertex of K whose normal cone holds the edge's outward normal, and pair each edge of K with the vertices of R likewise. Then settle the arrangement of those segments by winding, and keep its nonzero faces, minus the loops that the reduced convolution leaves inside. A convex obstacle reduces to the classic slope merge.
• The result must be identical, up to vertex order, to the current one, with exactness and refusal behaviour unchanged. The erosion path benefits through the sum of the complement.

Done when

• A committed benchmark, in minkowski_plan or a new bench, covers a synthetic region of 150, 300, 1,000 and 3,000 corners: clustered, non-convex furniture outlines, far from the origin and turned, summed and eroded by a 1.7 m × 0.9 m rectangle. It shows a wall-clock improvement on the 150–300 case, with growth close to the output size.
• Results agree with the current implementation on the existing test corpus and on the synthetic cases.
• A mutation probe shows that the pairing and loop filtering are load-bearing.

Related: #292 (memory of large regions), #323 (short and collinear edges).