"""Coordinate hygiene at the rounding boundary.
Everything here exists because rounding to the output grid is what creates
the constructs 4.10.3 forbids, not what removes them: a shapely-derived
outline routinely carries vertices less than a nanometer apart, and three
points of a shallow curve become exactly collinear once they land on the
grid. So the scrubbing runs *after* the coordinates are quantized, and the
same rules apply to a macro outline primitive as to a region contour -
4.5.1.6 says an outline "must comply with all the requirements of a contour
according to 4.10.3".
"""
from __future__ import annotations
import math
from itertools import pairwise
from .model import Contour, CurveSeg, Seg
from .units import NM_PER_MM, grid, nm
MIN_ARC_MM = 0.002
"""Arcs shorter than this are emitted as draws; below it the center is
numerically meaningless at the coordinate resolution."""
Point = tuple[float, float]
[docs]
class ContourError(ValueError):
"""A contour cannot be made to satisfy 4.10.3."""
def _cross(a: Point, b: Point, c: Point) -> int:
"""Twice the signed area of the triangle, in grid units."""
ax, ay = nm(a[0]), nm(a[1])
bx, by = nm(b[0]), nm(b[1])
cx, cy = nm(c[0]), nm(c[1])
return (bx - ax) * (cy - ay) - (by - ay) * (cx - ax)
def _same(a: Point, b: Point) -> bool:
return (nm(a[0]), nm(a[1])) == (nm(b[0]), nm(b[1]))
[docs]
def arc_angles(
start: Point, end: Point, center: Point, ccw: bool
) -> tuple[float, float]:
"""The start angle and signed sweep of an arc, in radians.
The sweep is positive counter-clockwise. A coincident start and end is a
full circle, which takes the full turn in the requested direction rather
than a zero sweep.
"""
a0 = math.atan2(start[1] - center[1], start[0] - center[0])
a1 = math.atan2(end[1] - center[1], end[0] - center[0])
sweep = a1 - a0
if ccw:
while sweep <= 0:
sweep += 2 * math.pi
else:
while sweep >= 0:
sweep -= 2 * math.pi
if _same(start, end):
sweep = 2 * math.pi if ccw else -2 * math.pi
return a0, sweep
[docs]
def split_arc(start: Point, end: Point, center: Point, ccw: bool) -> list[Point]:
"""Intermediate points splitting an arc into sweeps of at most 180°.
Returns the points between `start` and `end`, in order; empty when the
arc already fits. The spec singles out near-full arcs as numerically
unstable, and a full circle has no valid single-segment form inside a
contour at all.
"""
a0, sweep = arc_angles(start, end, center, ccw)
pieces = max(1, math.ceil(abs(sweep) / math.pi - 1e-9))
if pieces == 1:
return []
radius = math.hypot(start[0] - center[0], start[1] - center[1])
step = sweep / pieces
return [
(
grid(center[0] + radius * math.cos(a0 + step * i)),
grid(center[1] + radius * math.sin(a0 + step * i)),
)
for i in range(1, pieces)
]
[docs]
def arc_length(start: Point, end: Point, center: Point, ccw: bool) -> float:
"""Arc length in mm."""
_, sweep = arc_angles(start, end, center, ccw)
radius = math.hypot(start[0] - center[0], start[1] - center[1])
return abs(sweep) * radius
[docs]
def scrub(contour: Contour) -> Contour:
"""Put a contour on the output grid and make it satisfy 4.10.3.
Snaps every coordinate, drops zero-length and collinear straight
segments, turns sub-resolution arcs into straight segments, splits arcs
over 180 degrees, and verifies the closure holds after rounding rather
than before it.
Raises:
ContourError: nothing survives the scrubbing, or the contour does
not close on the grid.
"""
start = (grid(contour.start[0]), grid(contour.start[1]))
steps: list[Seg | CurveSeg] = []
here = start
for segment in contour.segments:
end = (grid(segment.x), grid(segment.y))
if isinstance(segment, Seg):
steps.append(Seg(*end))
else:
center = (grid(segment.cx), grid(segment.cy))
if arc_length(here, end, center, segment.ccw) < MIN_ARC_MM:
steps.append(Seg(*end))
else:
for mid in split_arc(here, end, center, segment.ccw):
steps.append(CurveSeg(mid[0], mid[1], *center, segment.ccw))
steps.append(CurveSeg(end[0], end[1], *center, segment.ccw))
here = end
ring = _cycle(start, steps)
ring = _dedupe(ring)
ring = _drop_collinear(ring)
_check_size(ring, contour)
return _uncycle(ring)
# A contour is scrubbed as a cyclic list of (vertex, incoming segment)
# pairs, so the closure point is an ordinary vertex rather than a special
# case. Without that the start vertex is the one place a collinear spike can
# survive, and it is exactly as illegal there as anywhere else.
_Cycle = list[tuple[Point, "Seg | CurveSeg"]]
def _cycle(start: Point, steps: list[Seg | CurveSeg]) -> _Cycle:
points = [start] + [(s.x, s.y) for s in steps[:-1]]
incoming = [steps[-1]] + steps[:-1]
return list(zip(points, incoming, strict=True))
def _uncycle(ring: _Cycle) -> Contour:
start = ring[0][0]
return Contour(start=start, segments=tuple(seg for _, seg in ring[1:] + ring[:1]))
def _check_size(ring: _Cycle, source: Contour) -> None:
"""A straight-edged contour needs three vertices; one built from arcs
needs two, since two half arcs are how this package writes a circle."""
least = 3 if all(isinstance(seg, Seg) for _, seg in ring) else 2
if len(ring) < least:
raise ContourError(f"contour degenerate after rounding: {source}")
def _dedupe(ring: _Cycle) -> _Cycle:
"""Drop a vertex a straight segment arrives at without moving.
Arc segments are kept regardless: a coincident start and end has already
been split above, so a surviving arc is a real sweep.
"""
out: _Cycle = []
for point, seg in ring:
if isinstance(seg, Seg) and out and _same(out[-1][0], point):
continue
out.append((point, seg))
while len(out) > 1 and isinstance(out[0][1], Seg) and _same(out[-1][0], out[0][0]):
out.pop()
return out
def _drop_collinear(ring: _Cycle) -> _Cycle:
"""Remove a vertex lying on the straight segment through its neighbours.
4.10.3 forbids a vertex on a segment anywhere other than at its
endpoints, and rounding to nanometers is a standard way to make one.
Only a vertex between two straight segments is a candidate; a vertex
adjacent to an arc is a real corner of the contour whatever the
collinearity of its coordinates says.
"""
out = list(ring)
index = 0
while len(out) > 3 and index < len(out):
point, seg = out[index]
following = out[(index + 1) % len(out)][1]
previous = out[index - 1][0]
after = out[(index + 1) % len(out)][0]
if (
isinstance(seg, Seg)
and isinstance(following, Seg)
and _cross(previous, point, after) == 0
):
del out[index]
index = 0
continue
index += 1
return out
[docs]
def validate(contour: Contour) -> None:
"""Check a scrubbed contour against 4.10.3.
Self-intersection is not checked here; it needs real geometry and the
format layer carries no shapely dependency, so §8's polarity layer owns
it.
Raises:
ContourError: a zero-length segment, a collinear vertex or an open
contour survived.
"""
least = 3 if all(isinstance(s, Seg) for s in contour.segments) else 2
if len(contour.segments) < least:
raise ContourError(f"contour has too few segments: {contour}")
here = contour.start
for step in contour.segments:
end = (step.x, step.y)
if isinstance(step, Seg) and _same(here, end):
raise ContourError(f"zero-length segment at {end}")
here = end
if not _same(here, contour.start):
raise ContourError(f"contour does not close: {here} != {contour.start}")
ring = _cycle(contour.start, list(contour.segments))
for index, (point, seg) in enumerate(ring):
following = ring[(index + 1) % len(ring)]
if not isinstance(seg, Seg) or not isinstance(following[1], Seg):
continue
if _cross(ring[index - 1][0], point, following[0]) == 0:
raise ContourError(f"vertex on a segment at {point}")
[docs]
def closed_ring(points: list[Point]) -> Contour:
"""A contour from a point ring, closing it if the caller has not.
The convention this package fixes, because the spec leaves it open and
§8's polarity simulator needs one to interpret: outer contours run
counter-clockwise, holes clockwise. This helper does not reorder;
it is the callers that owe the convention.
"""
ring = list(points)
if ring and not _same(ring[0], ring[-1]):
ring.append(ring[0])
return scrub(Contour(start=ring[0], segments=tuple(Seg(x, y) for x, y in ring[1:])))
[docs]
def signed_area(contour: Contour) -> float:
"""Twice the signed polygon area of a contour's vertices, in mm².
Positive is counter-clockwise. Arc bulges are ignored, so this is for
checking and fixing winding, not for measuring.
"""
points = [contour.start] + [(s.x, s.y) for s in contour.segments]
total = 0
for (x1, y1), (x2, y2) in pairwise(points):
total += nm(x1) * nm(y2) - nm(x2) * nm(y1)
return total / (NM_PER_MM * NM_PER_MM)