Crate straight_skeleton

Expand description

The straight skeleton of a polygon, on the i16 integer lattice.

Shrink a polygon by sliding every edge inward at the same speed, keeping the edges straight and letting them stay connected. The corners trace out a tree of straight line segments. That tree is the straight skeleton, and this crate computes it.

   +-----------------------+        +-----------------------+
   |                       |        |\                     /|
   |                       |        |  \                 /  |
   |                       |        |    \_____________/    |
   |                       |   ->   |    /             \    |
   |                       |        |  /                 \  |
   |                       |        |/                     \|
   +-----------------------+        +-----------------------+
        input polygon                   its straight skeleton

Straight skeletons are how you find a polygon’s medial ridge, generate mitred offset curves, or raise a roof over a floor plan — hip, mansard, or truncated, all off the same skeleton, since each node’s distance from the boundary is the run the roof has had to rise over. See Roof and the roof example.

§Quick start

use straight_skeleton::{skeleton, Point, Polygon};

// A 10x10 square.
let square = Polygon::from_outer(&[
    Point::new(0, 0),
    Point::new(10, 0),
    Point::new(10, 10),
    Point::new(0, 10),
])?;

let skel = skeleton(&square)?;

// Its skeleton is an X: the four corners meet at the centre.
assert_eq!(skel.arc_count(), 4);
let centre = skel.nodes().iter().find(|n| !n.is_boundary()).unwrap();
assert_eq!(centre.position, Point::new(5, 5));

§Tracing output back to input

Every skeleton Arc separates the faces of exactly two input edges, and carries those two ids in Arc::sources. This is not a nearest-neighbour search bolted on afterwards — it is what an arc is, so the lookup is a field access:

use straight_skeleton::{skeleton, Point, Polygon};

let square = Polygon::from_outer(&[
    Point::new(0, 0), Point::new(10, 0), Point::new(10, 10), Point::new(0, 10),
])?;
let skel = skeleton(&square)?;

for arc in skel.arcs() {
    let [e0, e1] = arc.sources;
    // Every point on this arc is equidistant from the supporting lines of
    // input edges e0 and e1.
    assert_ne!(e0, e1);
}

// Nodes carry the same information, with 3+ sources where arcs meet.
let centre = skel.nodes().iter().find(|n| !n.is_boundary()).unwrap();
assert_eq!(centre.sources.len(), 4); // equidistant from all four edges

Each input edge also owns one skeleton face, the region its wavefront swept. The faces tile the polygon, and every face is planar once lifted to z = offset — which is why Roof can raise a roof over a floor plan by reading the skeleton off rather than computing anything:

use straight_skeleton::{skeleton, Point, Polygon, Roof};

let plan = Polygon::from_outer(&[
    Point::new(0, 0), Point::new(120, 0), Point::new(120, 80), Point::new(0, 80),
])?;
let skel = skeleton(&plan)?;

let roof = Roof::new(&skel, 0.5)?;
assert_eq!(roof.panels().len(), 4);   // one flat panel per wall
assert_eq!(roof.ridge_height(), 20);  // i16, like every other coordinate

// The skeleton is the roof's *plan*, not its height, so a mansard reads off
// the very same one — only its [`Profile`] differs.
let mansard = Roof::mansard(&skel, 2.0, 10.0, 0.25)?;
assert_eq!(mansard.panels().len(), 8);  // the break cuts each wall's in two

One caveat, and it is a real one rather than an implementation wrinkle: a straight skeleton is not the medial axis. It bisects edges’ infinite supporting lines, which is what keeps every arc straight; a medial axis bisects the nearest features, and grows parabolas around reflex vertices. The two agree exactly when the polygon is convex, and part company around reflex corners. So sources means “the edges whose faces meet here”, which is the notion you actually want. Node::sources works through an example.

§Constrained skeletons

skeleton_constrained caps how far each edge is allowed to travel, individually. An edge that hits its limit simply stops, and its neighbours slide along it instead of over it. Use it to truncate a roof to a given eave-to-ridge rise, or to build a variable-width offset.

use straight_skeleton::{skeleton_constrained, Point, Polygon};

let square = Polygon::from_outer(&[
    Point::new(0, 0), Point::new(20, 0), Point::new(20, 20), Point::new(0, 20),
])?;

// Stop every edge after travelling 3 units, well before the centre at 10.
let limits = [3.0; 4];
let skel = skeleton_constrained(&square, &limits)?;

// Nothing gets further from the boundary than the limit allows.
assert!(skel.max_offset() <= 3.0 + 1e-4);

What the wavefront stops as is the other half of the answer, and Skeleton::residual returns it: the input polygon offset inward by the limit — the flat left in the middle of a truncated roof. The arcs are the stubs reaching in from the boundary; the residual is the outline they stop on.

use straight_skeleton::{skeleton, skeleton_constrained, Point, Polygon};

let square = Polygon::from_outer(&[
    Point::new(0, 0), Point::new(100, 0), Point::new(100, 100), Point::new(0, 100),
])?;

// Stop every edge at 20 and a 60x60 square is left standing in the middle.
let skel = skeleton_constrained(&square, &[20.0; 4])?;
assert_eq!(skel.residual()[0].len(), 4);

// A plain skeleton has none: its wavefront always shrinks away to nothing.
assert!(skeleton(&square)?.residual().is_empty());

§Coordinates: `i32` and `f32`, and no `f64`

Input and output coordinates are Points of i16, and the algorithm runs entirely in i32 and f32. There is no f64 anywhere in it, and no i64 either: the crate is meant to be portable to hardware where f64 is slow or missing, and a type you only use “internally” is still a type the hardware has to have.

That costs one bit of coordinate range. Coordinates are capped at Point::MIN_COORD..=Point::MAX_COORD, i.e. -16384..=16383, and Polygon rejects anything outside it. One expression sets that cap — the orientation determinant, which needs 2 * d^2 for a largest coordinate difference d:

coordinates	`2 * d^2`	in `i32`?
full `i16`	8_589_672_450	overflows, reporting the wrong side
capped	2_147_352_578	fits, with 131_069 to spare

So one bit buys exact predicates (predicates): no epsilon, no rounding, no overflow. f32 cannot do that job at any range — the tests pin down a real triple inside the cap where it reports a genuine turn as collinear.

The simulation itself is f32. Skeleton nodes are irrational in general, so there is no lattice to compute on; positions are rounded back to it at the boundary, and Node::exact keeps the unrounded value. The cap is also what leaves f32 enough absolute resolution — about 0.002 at its worst — to work in. docs/DESIGN.md works through the analysis, including what it costs in robustness.

§Feature flags

The crate has no required dependencies. Everything below is opt-in.

Feature	Default	Effect
`std`	yes	`std::error::Error` impls, hardware `sqrt`. Disable for `no_std`.
`serde`	no	`Serialize`/`Deserialize` on the public types.
`geo-types`	no	Conversions to and from `geo_types`.
`glam`	no	Conversions to and from `glam` vectors.
`mint`	no	Conversions to and from `mint` vectors.
`num-traits`	no	Generic numeric conversions.

§`no_std`

Disable default features. The crate needs alloc but nothing else — the only std maths it uses is sqrt, which it carries its own implementation of rather than take a dependency on libm.

straight-skeleton = { version = "0.1", default-features = false }

Modules§

predicates: Exact geometric predicates, in i32.

Structs§

Arc: An edge of the skeleton graph: a straight segment traced by one wavefront vertex as it moved.
ArcId: Identifies an Arc of a Skeleton.
EdgeId: Identifies an input edge of a Polygon.
Node: A vertex of the skeleton graph.
NodeId: Identifies a Node of a Skeleton.
Panel: One flat plane of roof.
Point: A point on the integer lattice.
Point3: A point on the 3D integer lattice.
Polygon: A simple polygon, optionally with holes, on the i16 lattice.
ResidualLoop: A loop of the wavefront that stopped rather than collapsing: the offset polygon a skeleton_constrained leaves behind.
RingId: Identifies a ring of a Polygon. Ring 0 is always the outer boundary.
Roof: A roof over a floor plan.
RoofVertex: One corner of a roof.
RoofVertexId: Identifies a corner of a Roof.
Skeleton: The straight skeleton of a Polygon.
VertexId: Identifies an input vertex of a Polygon.

Enums§

NodeKind: What produced a Node.
PanelKind: What part of a roof a Panel is.
PolygonError: Why a Polygon could not be built.
Profile: How a roof’s height grows with distance from the eaves.
RoofError: Why a roof could not be raised.
SkeletonError: Why a skeleton could not be computed.

Functions§

skeleton: Computes the straight skeleton of a polygon.
skeleton_constrained: Computes a straight skeleton in which each edge stops after travelling a given distance.