A diagonal segment's copper has no axis-aligned exact tile, so segment_box falls
back to the bounding box -- a huge conservative cover that makes diagonal traces
conflict with everything. segment_octagon builds the tight cover instead: the
copper of a 0/45/90/135-degree segment swept by a radius, as a convex integer
Simplex bounded by the four axis and four x+y / x-y diagonal half-planes.
Diagonal bounds widen by ceil_sqrt2(radius) -- the exact integer ceiling of
radius*sqrt(2) via math.isqrt, no float -- rounded outward, so the octagon is a
provable superset of segment (+) disk(radius) (verified over 20k sampled copper
points). Growing by clearance is just a larger radius, giving both the stored
copper tile and the queried clearance region. overlaps_2d tests a real 2-D
overlap via exact Simplex intersection, accepting mixed IntBox/Simplex tiles.
Displaces one segment of a trace polyline perpendicular by a given
offset, keeping the trace orthogonal and its two pad endpoints fixed: a
jog corner is inserted when the moved segment is first or last, and
interior neighbours simply resize. Collinear/duplicate corners are
dropped. This is the foundation for shoving a trace aside to make room
for another. Unit-tested for single-segment, interior-segment, and
orthogonality-preservation cases.
Ports the trace-relevant subset of geometry/planar/{Polyline,PolylineShape,
LineSegment}: a Polyline is a trace centreline (integer corners); a
PolylineShape is that centreline swept by the half-width, returned as exact
convex IntBox tiles (one flush box per orthogonal segment plus a square at
each interior corner to cover the turn). Exact for orthogonal segments; a
conservative bounding box for a diagonal one (never under-reports an
overlap). 45-degree/IntOctagon caps are deferred.
Ports geometry/planar/Polygon.java (corner de-duplication and collinear
removal, winding number) and PolygonShape.java, including the recursive
split_to_convex that decomposes a simple polygon into convex Simplex
tiles by dividing at concave corners along minimal axis-parallel lines.
Orientation and convexity tests are exact; the division-point search is
approximate (float line evaluation, split point rounded to an integer
corner) as upstream. The concave-corner search starts deterministically
at corner 0 rather than a seeded PRNG; this only affects which valid
decomposition is produced.
Supporting additions: Simplex.from_corners (convex polygon to simplex)
and Line.function_value_approx / function_in_y_value_approx.
Invariant tests over L, plus, staircase and square polygons: tile areas
sum to the polygon area (no gaps, no overlap), a point is in the polygon
iff in some tile, and no point is strictly inside more than one tile
(interiors disjoint). Also covers Polygon normalization and orientation.
Ports geometry/planar/TileShape.java (the border-line-based containment,
area, and centre-of-gravity logic) and Simplex.java (a convex region as
the intersection of directed half-planes). Corners are exact
intersections of consecutive border lines; point containment uses exact
side_of. The remove_redundant_lines normalization — dropping lines that
do not contribute and detecting emptiness — is ported line-for-line.
Supporting additions: Line.compare_to/__lt__ (angular sort order),
Line.fast_equals, Line.side_of_intersection, Line.translate (perpendicular
offset), IntDirection.determinant, and IntBox.to_simplex.
offset is approximate (rounded translated lines, as upstream); enlarge
clips to the enlarged bounding box pending the IntOctagon port.
Since there is no JVM oracle, tests assert invariants: corners lie
exactly on their border lines (exact side_of == 0), IntBox -> Simplex
preserves the region over a sampled grid, intersection is contained in
both operands and a point is in the result iff in both, and get_instance
normalization drops redundant lines and detects empty half-plane pairs.
Ports IntBox, the simplest concrete convex tile (RegularTileShape): exact
integer-corner rectangle with contains (border-inclusive and interior),
intersection, union, intersects/overlaps, offset (round half up),
horizontal/vertical offset, shrink, box containment, translate, and
dimension. Adds the package __init__ exporting the geometry API.
The general convex machinery beyond IntBox — TileShape/Simplex/IntOctagon
and polygon split_to_convex — is deferred to the next geometry phase.
Tests cover boundary vs interior containment, degenerate tiles
(empty/point/segment), edge-touching intersects-vs-overlaps, rational
point on a border, and half-up offset rounding.
Ports Direction/IntDirection (equivalence classes of vectors, gcd-
normalized, exact angular compare) and Line. Line.side_of uses an exact
integer determinant; Line.intersection returns an IntPoint when the
crossing is integral and a RationalPoint otherwise, with the orthogonal
and 45-degree fast paths from the source preserved. Parallel lines yield
a point at infinity (z=0). BigIntDirection is folded into IntDirection
since unbounded int always fits.
Tests cover integral and rational intersections, parallel-line infinity,
exactness beyond double precision (verified via exact collinearity of the
result), and direction normalization/ordering.
Ports the point/vector foundation of geometry/planar: Side and Signum
(three-valued signs), Limits, FloatPoint (approximate), and the exact
IntPoint/IntVector plus projective RationalPoint/RationalVector.
Arithmetic model per type is documented in each module. The key
simplification over the Java source: Python's unbounded int makes the
exact orientation determinants and rational (x,y,z) coordinates trivial,
so side_of is kept exact (upstream uses a double for speed) and no
BigInteger or CRIT_INT overflow promotion is needed. Rational points use
the projective triple with z=0 denoting the point at infinity.
Tests cover collinearity, determinants beyond Java long range, rational
equality/reduction, and integer/rational promotion.
