Struct Polygon 

pub struct Polygon { /* private fields */ }

A simple polygon, optionally with holes, on the i16 lattice.

Invariants

A Polygon can only be constructed through Polygon::new or Polygon::from_outer, which enforce that:

• Ring 0 is the outer boundary; rings 1.. are holes.
• The outer ring winds counter-clockwise and holes wind clockwise, so the polygon’s interior is always on the left of every directed edge. Rings supplied the other way round are reversed automatically.
• Every coordinate is within Point::MIN_COORD..=Point::MAX_COORD.
• Every ring has at least 3 vertices, no repeated consecutive vertices, and encloses a non-zero area.
• No two edges cross, and no vertex is a zero-width spike.
• Every hole lies inside the outer ring.

The uniform “interior on the left” rule is what lets the wavefront treat outer boundary and holes identically — see docs/ALGORITHM.md.

Vertex and edge numbering

Vertices are numbered 0..n across all rings, outer ring first. Edge i starts at vertex i; see EdgeId.

Examples

use straight_skeleton::{Point, Polygon};

// A square. Winding is fixed up for you.
let square = Polygon::from_outer(&[
    Point::new(0, 0),
    Point::new(10, 0),
    Point::new(10, 10),
    Point::new(0, 10),
])?;
assert_eq!(square.vertex_count(), 4);
assert_eq!(square.ring_count(), 1);

// A square with a square hole.
let with_hole = Polygon::new(
    &[Point::new(0, 0), Point::new(30, 0), Point::new(30, 30), Point::new(0, 30)],
    &[vec![
        Point::new(10, 10),
        Point::new(20, 10),
        Point::new(20, 20),
        Point::new(10, 20),
    ]],
)?;
assert_eq!(with_hole.ring_count(), 2);
assert_eq!(with_hole.vertex_count(), 8);

Implementations

impl Polygon

pub const MAX_VERTICES: usize

The largest number of vertices a polygon may have.

Bounded by VertexId’s u16, minus one so that “one past the end” indices cannot overflow.

pub fn new(outer: &[Point], holes: &[Vec<Point>]) -> Result<Self, PolygonError>

Builds a polygon from an outer ring and a list of holes.

Ring winding is normalised for you: the outer ring is made counter-clockwise and holes clockwise, reversing any ring given the other way round.

Errors

Returns a PolygonError naming the offending ring if the input is not a simple polygon with holes. See Polygon’s invariants for the full list of checks.

Examples

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

// A ring that crosses itself is rejected, not silently accepted.
let crossed = Polygon::from_outer(&[
    Point::new(0, 0),
    Point::new(10, 10),
    Point::new(10, 0),
    Point::new(0, 4),
]);
assert!(matches!(crossed, Err(PolygonError::SelfIntersection { .. })));

pub fn from_outer(outer: &[Point]) -> Result<Self, PolygonError>

Builds a polygon with no holes.

Errors

As Polygon::new.

pub fn vertex_count(&self) -> usize

Total number of vertices across all rings.

pub fn ring_count(&self) -> usize

Number of rings: 1 (outer) plus one per hole.

pub fn hole_count(&self) -> usize

Number of holes.

pub fn vertices(&self) -> &[Point]

All vertices, outer ring first, then holes in order.

pub fn vertex(&self, v: VertexId) -> Point

The position of a vertex.

Panics

Panics if v does not belong to this polygon.

pub fn ring(&self, ring: RingId) -> &[Point]

The vertices of one ring, in order.

Panics

Panics if ring does not belong to this polygon.

pub fn ring_of(&self, v: VertexId) -> RingId

Which ring a vertex belongs to.

Panics

Panics if v does not belong to this polygon.

pub fn rings(&self) -> impl Iterator<Item = &[Point]> + '_

Iterates every ring’s vertices in order, outer ring first.

pub fn next_vertex(&self, v: VertexId) -> VertexId

The vertex following v within its ring, wrapping at the ring’s end.

pub fn prev_vertex(&self, v: VertexId) -> VertexId

The vertex preceding v within its ring, wrapping at the ring’s start.

pub fn edge(&self, e: EdgeId) -> (Point, Point)

The endpoints of an edge, in direction order.

The polygon’s interior lies to the left of start -> end.

Panics

Panics if e does not belong to this polygon.

pub fn edge_count(&self) -> usize

Total number of edges, which equals the number of vertices.

pub fn edge_ids(&self) -> impl Iterator<Item = EdgeId> + '_

Iterates every edge id.

pub fn vertex_ids(&self) -> impl Iterator<Item = VertexId> + '_

Iterates every vertex id.

pub fn is_reflex(&self, v: VertexId) -> bool

Whether the interior angle at v exceeds 180°, i.e. v is a reflex (“notch”) corner.

Reflex vertices are the only ones that can trigger split events, so this drives the algorithm’s main branch.

pub fn signed_area2(&self) -> i64

Twice the signed area of the polygon: the outer ring’s area minus every hole’s. Always positive for a valid polygon.

Trait Implementations

impl Clone for Polygon

fn clone(&self) -> Polygon

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for Polygon

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<'de> Deserialize<'de> for Polygon

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl Eq for Polygon

impl PartialEq for Polygon

fn eq(&self, other: &Polygon) -> bool

Equality operator ==.

fn ne(&self, other: &Rhs) -> bool

Inequality operator !=.

impl Serialize for Polygon

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.

impl StructuralPartialEq for Polygon