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.

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 edge order is not stored. Consumers derive it from the segment geometry and vertex point. 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),
  )
}

Constructors

```
ArrangementGraph(
  vertices: List(ArrangementVertex),
  edges: List(ArrangementEdge),
)
```
Arguments

vertices

Endpoint clusters in the arrangement.

edges

Non-intersecting atomic edges in the arrangement.

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)

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,
  )
  UndirectedMultiplicityMismatch(edge: Int)
  OddSkeletonCycle(edge: Int)
  UndirectedTraceFailed(vertex: 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.

```
UndirectedMultiplicityMismatch(edge: Int)
```
An undirected decomposition does not reconstruct the source graph.
```
OddSkeletonCycle(edge: Int)
```
An odd skeleton contains a cycle.
```
UndirectedTraceFailed(vertex: Int)
```
An even undirected contour could not be traced into closed loops.

OddEvenDecomposition

</>

Decomposition of an undirected arrangement into odd and even parts.

odd_skeleton is an acyclic subgraph whose odd-degree vertices are exactly the odd-degree vertices of the original graph. even_graph is the remaining graph after subtracting that skeleton.

pub type OddEvenDecomposition {
  OddEvenDecomposition(
    odd_skeleton: UndirectedArrangementGraph,
    even_graph: UndirectedArrangementGraph,
  )
}

Constructors

OddEvenDecomposition(
  odd_skeleton: UndirectedArrangementGraph,
  even_graph: UndirectedArrangementGraph,
)

UndirectedArrangementEdge

</>

One undirected edge of an arrangement graph.

This forgets source traversal direction and keeps only total multiplicity. It is intended for parity/topology operations where forward and reverse directional multiplicities should not be interpreted.

pub type UndirectedArrangementEdge {
  UndirectedArrangementEdge(
    id: Int,
    segment: svg_path.Segment,
    start_vertex: Int,
    end_vertex: Int,
    multiplicity: Int,
  )
}

Constructors

```
UndirectedArrangementEdge(
  id: Int,
  segment: svg_path.Segment,
  start_vertex: Int,
  end_vertex: Int,
  multiplicity: Int,
)
```
Arguments

id

The corresponding arrangement edge identifier.

segment

The edge geometry, with the same stored orientation as the source edge.

start_vertex

Identifier of one endpoint cluster.

end_vertex

Identifier of the other endpoint cluster.

multiplicity

Total undirected multiplicity of this edge.

UndirectedArrangementGraph

</>

An arrangement graph with edge orientation forgotten.

vertices are copied from the directed arrangement. Each edge multiplicity is the sum of forward and reverse multiplicities from the source graph.

pub type UndirectedArrangementGraph {
  UndirectedArrangementGraph(
    vertices: List(ArrangementVertex),
    edges: List(UndirectedArrangementEdge),
  )
}

Constructors

UndirectedArrangementGraph(
  vertices: List(ArrangementVertex),
  edges: List(UndirectedArrangementEdge),
)

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.

odd_even_decomposition

</>

pub fn odd_even_decomposition(
  graph: UndirectedArrangementGraph,
) -> Result(OddEvenDecomposition, Error)

Decompose an undirected arrangement into an acyclic odd skeleton and even remainder.

The odd skeleton is computed by greedily pairing odd vertices along shortest undirected paths.

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.

to_undirected

</>

pub fn to_undirected(
  graph: ArrangementGraph,
) -> UndirectedArrangementGraph

Forget edge orientation and keep only total edge multiplicity.

undirected_nested_contours

</>

pub fn undirected_nested_contours(
  graph: UndirectedArrangementGraph,
  tolerance tolerance: Float,
) -> Result(List(svg_path.Subpath), Error)

Trace an even undirected arrangement into nested closed contour subpaths.

Every retained edge unit is traced once. At each vertex, the next edge is chosen by cyclic ray order, matching the filled-sector traversal used by CSG boundary reconstruction. The input must have even weighted degree at every vertex.

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.

verify_odd_even_decomposition

</>

pub fn verify_odd_even_decomposition(
  original: UndirectedArrangementGraph,
  decomposition: OddEvenDecomposition,
) -> Result(Nil, Error)

Verify that an odd/even decomposition reconstructs its source graph and satisfies the parity contracts.

Constructors

Arguments

Constructors

Arguments

Constructors

Arguments

Constructors

Constructors

Arguments

Constructors

Constructors

Constructors

Constructors

Arguments

Constructors