Module arrangements 

P11.8 — Arrangements, point-line duality, and topological sweep. P11.8 — Arrangements, point-line duality, and topological sweep.

The acceptance gate requires: “Full line arrangement has correct V/E/F counts, zone traversal matches a direct oracle, and dual transforms round-trip finite/non-vertical cases.”

Algorithms

Line arrangement

Given n lines, the arrangement is the planar subdivision induced by their pairwise intersections. For n lines in general position (no three concurrent, no two parallel):

• V = n(n-1)/2 intersection points.
• E = n² edges (each line is split into n segments/rays by the other n-1 lines, giving n edges per line × n lines = n²).
• F = n(n-1)/2 + 1 faces (by Euler: V − E + F = 2).

Unbounded edges (rays) are clipped to a bounding box enclosing all vertices with a margin, so the arrangement is treated as a bounded subdivision with a single unbounded face wrapping around the box.

Zone traversal

The zone of a curve γ in an arrangement A is the sequence of faces that γ passes through. For a line crossing an arrangement of n lines, the zone has at most 2n faces (the Zone Theorem). The traversal finds every intersection of γ with arrangement edges, sorts them along γ, and reports the face between each consecutive pair by locating a midpoint in the arrangement.

Point-line duality

The standard point-line duality transform:

• Point p = (a, b) ↔ dual line p* : y = a·x − b.
• Line l : y = m·x + c ↔ dual point l* = (m, −c).

Key property: p is above l ⟺ l* is above p*. The round-trip dual(dual(p)) = p holds for all finite, non-vertical cases.

Zero-heap contract

Tier-2 cold construction (AGENTS.md §0-A): Vec during build; typed struct output. The orientation predicate path is zero-heap.

Structs

Arrangement

A line arrangement: the planar subdivision induced by a set of lines.

ArrangementCounts

Summary counts for verification.

ArrangementEdge

One edge of a line arrangement: a segment along one line between two vertices (or between a vertex and a bounding-box clip point for unbounded edges).

ArrangementFace

One face of a line arrangement: a polygon (possibly unbounded, clipped to the bounding box).

Line2

A 2-D line in slope-intercept form. Vertical lines have is_vertical = true and use x_const instead of slope/intercept.

Enums

ArrangementError

Functions

build_line_arrangement

Build a line arrangement from a set of lines.

dual_incidence_holds

Check the incidence-preserving property: point p is on line l ⟺ dual line p* passes through dual point l*.

dual_line_to_point

Dual of a non-vertical line l : y = m·x + c: the point (m, −c).

dual_point_to_line

Dual of a point p = (a, b): the line y = a·x − b.

dual_round_trip

Round-trip the duality: dual(dual(p)) should equal p for all finite, non-vertical points.

line_line_intersection

Compute the intersection point of two lines. Returns None if parallel.

zone_traversal

The zone of a query line through an arrangement: the sequence of face indices that the line passes through, in order along the line.

zone_traversal_oracle

Brute-force zone traversal: for a fine sample of points along the query line, locate the containing face. Returns the distinct face indices in order of first encounter. Used as an independent oracle to verify zone_traversal.