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 length upper bound is at least minimum_length (the segment-length upper-bound threshold).

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,
)

ArrangementEdgeImage

</>

The input-segment occurrences corresponding to one arrangement edge.

The first source is the first occurrence found in source order and is the provisional owner used by ArrangementSegmentEdgeImage.own.

pub type ArrangementEdgeImage {
  ArrangementEdgeImage(
    edge_id: Int,
    sources: List(ArrangementEdgeSourceImage),
  )
}

Constructors

ArrangementEdgeImage(
  edge_id: Int,
  sources: List(ArrangementEdgeSourceImage),
)

ArrangementEdgeSourceImage

</>

One input segment occurrence corresponding to an arrangement edge.

ta <= tb are parameters on the input segment. reversed records whether the input segment traversal opposes the stored graph edge orientation.

pub type ArrangementEdgeSourceImage {
  ArrangementEdgeSourceImage(
    segment_index: Int,
    ta: Float,
    tb: Float,
    reversed: Bool,
  )
}

Constructors

ArrangementEdgeSourceImage(
  segment_index: Int,
  ta: Float,
  tb: Float,
  reversed: Bool,
)

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_closed_boundaries checks this extra condition; validate_representation also accepts open arrangements.

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

Constructors

```
ArrangementGraph(
  vertices: List(ArrangementVertex),
  edges: List(ArrangementEdge),
  cyclic_orders: List(#(Int, List(List(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 has a segment length upper bound below minimum_length.

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.

ArrangementSegmentBuild

</>

Arrangement graph build result for direct segment-list construction.

This path does not normalize or rewrite caller input before construction.

pub type ArrangementSegmentBuild {
  ArrangementSegmentBuild(
    graph: ArrangementGraph,
    segments: List(svg_path.Segment),
    segment_images: List(ArrangementSourceSegmentImage),
    edge_images: List(ArrangementEdgeImage),
  )
}

Constructors

ArrangementSegmentBuild(
  graph: ArrangementGraph,
  segments: List(svg_path.Segment),
  segment_images: List(ArrangementSourceSegmentImage),
  edge_images: List(ArrangementEdgeImage),
)

ArrangementSegmentEdgeImage

</>

One atomic graph edge in the image of one input segment.

ta <= tb are source parameters retained through subdivision, not recovered by endpoint projection. reversed records whether the input traversal opposes the stored graph edge orientation. own is true for the first input segment occurrence assigned to the edge.

pub type ArrangementSegmentEdgeImage {
  ArrangementSegmentEdgeImage(
    ta: Float,
    tb: Float,
    edge_id: Int,
    reversed: Bool,
    own: Bool,
  )
}

Constructors

ArrangementSegmentEdgeImage(
  ta: Float,
  tb: Float,
  edge_id: Int,
  reversed: Bool,
  own: Bool,
)

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),
)

ArrangementSourceSegmentImage

</>

The ordered atomic graph-edge image of one input segment.

pub type ArrangementSourceSegmentImage {
  ArrangementSourceSegmentImage(
    segment_index: Int,
    edges: List(ArrangementSegmentEdgeImage),
  )
}

Constructors

ArrangementSourceSegmentImage(
  segment_index: Int,
  edges: List(ArrangementSegmentEdgeImage),
)

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. The enclosing-circle center is determined by the samples in a given cluster, but greedy assignment of endpoints to clusters can depend on 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

</>

Stable errors returned by arrangement construction and validation.

pub type Error {
  PathError(error: svg_path.Error)
  InvalidTolerance(tolerance: Float)
  InvalidMinimumLength(minimum_length: Float)
  InvalidEndpointSliverTolerance(tolerance: Float)
  SegmentTooShort(length_upper_bound: Float, minimum: Float)
  DualCertificationFailed
  ConstructionFailed
}

Constructors

```
PathError(error: svg_path.Error)
```
An underlying path operation failed.
```
InvalidTolerance(tolerance: Float)
```
Endpoint tolerance must be greater than zero.
```
InvalidMinimumLength(minimum_length: Float)
```
The minimum length-upper-bound threshold must be greater than zero.
```
InvalidEndpointSliverTolerance(tolerance: Float)
```
Endpoint-sliver tolerance must be finite and non-negative.
```
SegmentTooShort(length_upper_bound: Float, minimum: Float)
```
A segment length upper bound is below the requested threshold.
```
DualCertificationFailed
```
The bounded dual sweep search could not certify all face relationships. This does not establish that the input graph is invalid.
```
ConstructionFailed
```
The arrangement construction or validation failed an internal invariant.

OrientedArrangementEdge

</>

One arrangement edge with an outward orientation from an incident vertex.

reversed is false when the oriented edge follows the stored edge direction and true when it opposes it.

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

Constructors

OrientedArrangementEdge(edge_id: Int, reversed: Bool)

Values

build

</>

pub fn build(
  paths: List(svg_path.Path),
  tolerance tolerance: Float,
  minimum_length minimum_length: 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. Remaining self-intersecting pieces are subdivided only after comparisons against existing edges; the children re-enter ordinary insertion. The minimum_length argument filters by segment length upper bound, so a zero-chord loop is not discarded merely because its endpoints coincide.

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 using accepted infinite-line sweeps through the components. Vertex hits, tangencies, overlaps and inseparable crossings are rejected. Independent accepted lines must agree. Exhausting the search budget returns DualCertificationFailed; contradictory accepted results return ConstructionFailed. No displaced containment probes are used.

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_closed_boundaries

</>

pub fn validate_closed_boundaries(
  graph: ArrangementGraph,
  tolerance tolerance: Float,
  minimum_length minimum_length: Float,
) -> Result(Nil, Error)

Check representation invariants and even weighted degree at every vertex.

This adds the closed-boundary degree requirement to validate_representation. It does not certify geometric atomicity or guarantee that dual construction will succeed.

validate_representation

</>

pub fn validate_representation(
  graph: ArrangementGraph,
  tolerance tolerance: Float,
  minimum_length minimum_length: Float,
) -> Result(Nil, Error)

Check local representation invariants for open or closed arrangements.

Checks unique vertex/edge IDs, nonnegative directional multiplicities with positive totals, vertex references, non-loop edges, endpoint tolerance, minimum length upper bounds, endpoint-cluster centers/radii, and incidence. Use the tolerance and minimum length supplied during construction. Does not certify atomicity, pairwise intersections, cached bounds, or cyclic orders. Use build to establish the full construction invariants.

Constructors

Arguments

Constructors

Constructors

Constructors

Constructors

Constructors

Constructors

Constructors

Arguments

Constructors

Arguments

Constructors

Constructors

Constructors

Constructors

Constructors

Arguments

Constructors

Constructors

Constructors

Constructors