svg_path/arrangement

Arrangement-graph primitives for Boolean path operations.

This module provides arrangement construction, endpoint clustering, coincident-edge multiplicity, and invariant validation. build refines intersections and endpoint-bounded overlaps into atomic segments before inserting them as graph edges.

An atomic segment has no proper intersection or partial overlap with any other edge segment. Atomic segments may meet at their endpoint vertices. Geometrically coincident atomic segments are represented by one edge with directional multiplicities.

The public types are transparent so callers can inspect, serialize, and draw an arrangement. build is the supported constructor: code that assembles these representations directly is responsible for all documented invariants.

Types

ArrangementEdge

</>

One directed geometric edge of an arrangement.

The stored segment runs from start_vertex to end_vertex. Its endpoints remain the source endpoints and are within the build tolerance of the corresponding vertex points; construction does not move the segment to the cluster centers. The segment’s chord is at least minimum_chord.

forward_multiplicity counts coincident source segments oriented like the stored segment, and reverse_multiplicity counts those oriented against it. Both are non-negative and their sum is positive in a constructed graph.

pub type ArrangementEdge {
  ArrangementEdge(
    id: Int,
    segment: svg_path.Segment,
    bounds: svg_path.BoundingBox,
    start_vertex: Int,
    end_vertex: Int,
    forward_multiplicity: Int,
    reverse_multiplicity: Int,
  )
}

Constructors

```
ArrangementEdge(
  id: Int,
  segment: svg_path.Segment,
  bounds: svg_path.BoundingBox,
  start_vertex: Int,
  end_vertex: Int,
  forward_multiplicity: Int,
  reverse_multiplicity: Int,
)
```
Arguments

id

The edge’s unique identifier in a graph returned by build.

segment

The atomic segment, oriented from start_vertex to end_vertex.

bounds

Exact axis-aligned bounding box of segment.

start_vertex

Identifier of the segment’s start endpoint cluster.

end_vertex

Identifier of the segment’s end endpoint cluster.

forward_multiplicity

Number of coincident source segments with the stored orientation.

reverse_multiplicity

Number of coincident source segments with the reverse orientation.

ArrangementEdgeFaces

</>

The two dual faces incident to one arrangement edge.

A bridge has the same face on both sides.

pub type ArrangementEdgeFaces {
  ArrangementEdgeFaces(
    edge_id: Int,
    left_face: Int,
    right_face: Int,
  )
}

Constructors

ArrangementEdgeFaces(
  edge_id: Int,
  left_face: Int,
  right_face: Int,
)

ArrangementFace

</>

One connected open region of the plane complementary to an arrangement.

outer is true only for the infinite face. For a bounded face, the first walk is its enclosing outer walk and any remaining walks surround islands. The infinite face has no enclosing outer walk, so all of its walks have outer: False.

pub type ArrangementFace {
  ArrangementFace(
    id: Int,
    outer: Bool,
    walks: List(ArrangementFaceWalk),
  )
}

Constructors

ArrangementFace(
  id: Int,
  outer: Bool,
  walks: List(ArrangementFaceWalk),
)

ArrangementFaceEdge

</>

One arrangement edge used by a face boundary walk.

left is true when the face lies on the visual left of the edge’s stored direction. A face walk follows the stored direction when left is true and reverses it otherwise.

pub type ArrangementFaceEdge {
  ArrangementFaceEdge(edge_id: Int, left: Bool)
}

Constructors

ArrangementFaceEdge(edge_id: Int, left: Bool)

ArrangementFaceWalk

</>

One connected boundary component of an arrangement face.

outer identifies the enclosing boundary of a bounded face. Such a walk is always first in its face’s walk list. Every edge is traversed with the face on its visual left.

pub type ArrangementFaceWalk {
  ArrangementFaceWalk(
    outer: Bool,
    edges: List(ArrangementFaceEdge),
  )
}

Constructors

ArrangementFaceWalk(
  outer: Bool,
  edges: List(ArrangementFaceEdge),
)

ArrangementGraph

</>

A possibly disconnected planar arrangement of source path segments.

Graphs returned by build have unique vertex and edge identifiers. Every edge refers to two existing, distinct vertices, and every vertex is incident to an edge. Different atomic edges have no proper intersections or partial overlaps; they meet only through endpoint clusters. Coincident pieces are consolidated into one edge with directional multiplicities.

cyclic_orders records every incident oriented edge in clockwise SVG order at each vertex. Each edge is directed outward from its vertex. The outer list gives the certified clockwise order of groups. Oriented edges within one group could not be separated by the configured geometric tests; their order is a deterministic best-effort majority order across sampled radii. For closed-boundary input, the sum of incident edge multiplicities at every vertex is positive and even. validate enforces this closed-boundary condition, so an arrangement built from open subpaths may be inspectable but fail validation.

pub type ArrangementGraph {
  ArrangementGraph(
    vertices: List(ArrangementVertex),
    edges: List(ArrangementEdge),
    cyclic_orders: List(
      #(Int, List(List(@internal OrientedArrangementEdge))),
    ),
  )
}

Constructors

ArrangementGraph(
  vertices: List(ArrangementVertex),
  edges: List(ArrangementEdge),
  cyclic_orders: List(
    #(Int, List(List(@internal OrientedArrangementEdge))),
  ),
)

Arguments

vertices: Endpoint clusters in the arrangement.
edges: Non-intersecting atomic edges in the arrangement.
cyclic_orders: Clockwise incident oriented-edge order for every vertex.

ArrangementGraphBuild

</>

An arrangement graph and source-segment images for the paths from which it was constructed.

segment_images has one entry for every input segment, in path, subpath, and segment order. Each image lists the atomic graph edges in that segment’s traversal order. A reference’s reversed flag is true when that traversal opposes the edge’s stored direction. An image can be empty when every refined piece is shorter than minimum_chord.

pub type ArrangementGraphBuild {
  ArrangementGraphBuild(
    graph: ArrangementGraph,
    segment_images: List(ArrangementSegmentImage),
  )
}

Constructors

```
ArrangementGraphBuild(
  graph: ArrangementGraph,
  segment_images: List(ArrangementSegmentImage),
)
```
Arguments

graph

The arrangement produced from the input paths.

segment_images

Ordered graph-edge images of every source segment.

ArrangementSegmentImage

</>

The ordered atomic graph edges produced from one source segment.

The three indices address the segment in the original input paths.

pub type ArrangementSegmentImage {
  ArrangementSegmentImage(
    path_index: Int,
    subpath_index: Int,
    segment_index: Int,
    edges: List(DirectedEdgeReference),
  )
}

Constructors

ArrangementSegmentImage(
  path_index: Int,
  subpath_index: Int,
  segment_index: Int,
  edges: List(DirectedEdgeReference),
)

ArrangementVertex

</>

One endpoint cluster in the embedded arrangement.

point is the center of the smallest circle enclosing endpoint_samples. Construction accepts a sample only when that circle’s squared radius does not exceed the graph’s squared endpoint tolerance. Consequently every sample lies within tolerance of point, without making the result depend on endpoint insertion order.

pub type ArrangementVertex {
  ArrangementVertex(
    id: Int,
    point: svg_path.Point,
    endpoint_samples: List(svg_path.Point),
  )
}

Constructors

```
ArrangementVertex(
  id: Int,
  point: svg_path.Point,
  endpoint_samples: List(svg_path.Point),
)
```
Arguments

id

The vertex identifier referenced by incident edges.

point

The representative location of this endpoint cluster.

endpoint_samples

The original segment endpoints assigned to this cluster.

DirectedEdgeReference

</>

One graph edge traversed as part of a source segment.

edge_id identifies an edge in the containing build’s graph. reversed records whether the source traversal opposes that edge’s stored segment.

pub type DirectedEdgeReference {
  DirectedEdgeReference(edge_id: Int, reversed: Bool)
}

Constructors

DirectedEdgeReference(edge_id: Int, reversed: Bool)

DualArrangementGraph

</>

The planar dual derived from an ArrangementGraph.

faces contains exactly one infinite face, identified by outer: True, and that face is first. edge_faces records the faces on the visual left and right of every stored arrangement-edge direction.

pub type DualArrangementGraph {
  DualArrangementGraph(
    faces: List(ArrangementFace),
    edge_faces: List(ArrangementEdgeFaces),
  )
}

Constructors

DualArrangementGraph(
  faces: List(ArrangementFace),
  edge_faces: List(ArrangementEdgeFaces),
)

Error

</>

Errors returned while constructing or validating an arrangement graph.

InvalidTolerance and InvalidMinimumChord report invalid caller options. The remaining variants report a path failure or a violated graph invariant.

pub type Error {
  PathError(svg_path.Error)
  InternalNormalizationError
  InvalidTolerance(tolerance: Float)
  InvalidMinimumChord(minimum_chord: Float)
  SegmentTooShort(chord: Float, minimum: Float)
  SegmentCollapsedToVertex(vertex: Int)
  LoopEdge(vertex: Int)
  MissingVertex(vertex: Int)
  MissingEdge(edge: Int)
  IsolatedVertex(vertex: Int)
  InvalidMultiplicity(edge: Int)
  OddWeightedDegree(vertex: Int, degree: Int)
  EdgeEndpointMismatch(edge: Int, vertex: Int, distance: Float)
  VertexWithoutEndpointSamples(vertex: Int)
  VertexCenterMismatch(vertex: Int, distance_squared: Float)
  VertexSampleOutsideTolerance(
    vertex: Int,
    distance_squared: Float,
    tolerance_squared: Float,
  )
  ContourTraceFailed(vertex: Int)
  CyclicOrderMissingVertex(vertex: Int)
  CyclicOrderRadiusUnavailable(vertex: Int)
  InvalidCyclicOrderAttempts(max_attempts: Int)
  CyclicOrderCircleIntersectionFailed(
    vertex: Int,
    edge: Int,
    radius: Float,
  )
  DualMissingCyclicOrder(vertex: Int)
  DualMissingIncidentEdge(vertex: Int, edge: Int)
  DualWalkDidNotClose(edge: Int, left: Bool)
  DualFaceSampleUnavailable(edge: Int, left: Bool)
  DualInvalidOuterWalkCount(count: Int)
  DualMissingEdgeFace(edge: Int, left: Bool)
  DualInvalidOuterFaceCount(count: Int)
}

Constructors

```
PathError(svg_path.Error)
```
An underlying path operation failed.
```
InternalNormalizationError
```
Normalization failed for a reason outside its path-operation contract.
```
InvalidTolerance(tolerance: Float)
```
Endpoint tolerance must be greater than zero.
```
InvalidMinimumChord(minimum_chord: Float)
```
Minimum edge chord length must be greater than zero.
```
SegmentTooShort(chord: Float, minimum: Float)
```
A segment is shorter than the required minimum chord length.
```
SegmentCollapsedToVertex(vertex: Int)
```
Endpoint clustering collapsed an inserted segment to one vertex.
```
LoopEdge(vertex: Int)
```
A graph edge refers to the same vertex at both ends.
```
MissingVertex(vertex: Int)
```
An edge refers to a vertex that is not in the graph.
```
MissingEdge(edge: Int)
```
A segment image refers to an edge that is not in its build graph.
```
IsolatedVertex(vertex: Int)
```
A vertex has no incident edge.
```
InvalidMultiplicity(edge: Int)
```
An edge’s total directional multiplicity is not positive.
```
OddWeightedDegree(vertex: Int, degree: Int)
```
A closed-boundary graph has an odd weighted degree at a vertex.
```
EdgeEndpointMismatch(edge: Int, vertex: Int, distance: Float)
```
A segment endpoint is farther than tolerance from its vertex point.
```
VertexWithoutEndpointSamples(vertex: Int)
```
A vertex does not retain any source endpoints for its cluster.
```
VertexCenterMismatch(vertex: Int, distance_squared: Float)
```
A vertex point is not the canonical center of its endpoint samples.

VertexSampleOutsideTolerance(
  vertex: Int,
  distance_squared: Float,
  tolerance_squared: Float,
)

A vertex’s endpoint cluster exceeds the graph tolerance.

```
ContourTraceFailed(vertex: Int)
```
A contour could not be traced into closed loops.
```
CyclicOrderMissingVertex(vertex: Int)
```
A cyclic edge order was requested for a vertex outside the graph.
```
CyclicOrderRadiusUnavailable(vertex: Int)
```
No positive common sampling radius exists at a vertex.
```
InvalidCyclicOrderAttempts(max_attempts: Int)
```
A cyclic-order search requires at least one sampling radius.

CyclicOrderCircleIntersectionFailed(
  vertex: Int,
  edge: Int,
  radius: Float,
)

An incident edge did not yield a certified first circle intersection.

```
DualMissingCyclicOrder(vertex: Int)
```
A dual walk could not find the cyclic order at its arrival vertex.
```
DualMissingIncidentEdge(vertex: Int, edge: Int)
```
A dual walk could not find its incoming edge in a vertex’s cyclic order.
```
DualWalkDidNotClose(edge: Int, left: Bool)
```
A dual walk repeated an edge side before returning to its start.
```
DualFaceSampleUnavailable(edge: Int, left: Bool)
```
A face boundary could not provide a non-boundary point on its left side.
```
DualInvalidOuterWalkCount(count: Int)
```
A bounded face did not have exactly one enclosing outer walk.
```
DualMissingEdgeFace(edge: Int, left: Bool)
```
An arrangement edge side was absent from the derived faces.
```
DualInvalidOuterFaceCount(count: Int)
```
Dual construction did not identify exactly one infinite face.

Values

build

</>

pub fn build(
  paths: List(svg_path.Path),
  tolerance tolerance: Float,
  minimum_chord minimum_chord: Float,
) -> Result(ArrangementGraphBuild, Error)

Build an arrangement graph from the input paths.

Construction flattens the input paths into their existing segments, then nodes them progressively at intersections and endpoint-bounded overlap boundaries.

dual

</>

pub fn dual(
  graph: ArrangementGraph,
) -> Result(DualArrangementGraph, Error)

Derive the planar dual without modifying the arrangement graph.

The existing clockwise cyclic orders determine face successors. Boundary walks are grouped when points immediately on their visual-left sides occupy the same combination of nested boundary regions.

segment_image_edges

</>

pub fn segment_image_edges(
  build: ArrangementGraphBuild,
  image: ArrangementSegmentImage,
) -> Result(List(#(ArrangementEdge, Bool)), Error)

Resolve one segment image to graph edges and traversal directions.

validate

</>

pub fn validate(
  graph: ArrangementGraph,
  tolerance tolerance: Float,
  minimum_chord minimum_chord: Float,
) -> Result(Nil, Error)

Validate local representation and closed-boundary invariants.

This checks multiplicity totals, vertex references, non-loop edges, endpoint tolerance, minimum chord length, endpoint-cluster centers and radii, vertex incidence, and even weighted degree. It does not test pairwise edge intersections, atomicity, identifier uniqueness, or individual directional multiplicity signs; use build to establish those construction invariants.