Crate dcel 

dcel

Dynamic doubly-connected edge list (DCEL) in Rust.

A DCEL is a topological data structure that represents an embedding of a planar graph in the plane. DCEL partitions a surface into easily and quickly traversable vertices, edges, and faces, while making only minimal assumptions about their shapes. You can freely choose wherever the vertices should have two or more dimensions, or wheverer the edges are line segments or curved arcs.

DCEL is also known as half-edge data structure.

In mathematics, particularly in topological graph theory and algebraic graph theory, planar graph embeddings in the plane are instead represented using concepts such as cellularly embedded graph, ribbon graph, band decomposition, ram graph, arrow presentation, signed rotation system, all of which have many similarities to the DCEL.

Usage

Adding dependency

First, add dcel as a dependency to your Cargo.toml

[dependencies]
dcel = "0.8"

Documentation

See the documentation for more information about dcel’s usage.

Packaging

dcel is published as a crate on the Crates.io registry.

Contributing

Venues

We welcome issues and pull requests from anyone to our canonical repository on GitHub.

AI policy

We accept contributions created with the help of generative AI tools. Disclosure is welcome but not required, unless we ask you.

However, outside of our repository’s code, everywhere in our community’s spaces (including bug tracker), any text or other media that has been synthesized with LLMs or any other generative tool should be clearly marked as such.

Licence

Outbound licence

dcel is dual-licensed as under either of

• MIT license,
• Apache License, Version 2.0,

at your option.

Inbound licence

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in this work by you will be dual-licensed as described above, without any additional terms or conditions.

Structs

Dcel

A doubly-connected edge list (DCEL).

EdgeId

A unique identifier to an edge made of an ascendingly sorted pair of half-edge ids.

Face

The data which describes a face.

FaceId

An index pointing to a face.

HalfEdge

The data which describes a half-edge.

HalfEdgeId

An index pointing to a half-edge.

HalfSpokesIter

Iterator over half-spokes of a vertex in forward direction. This is HalfSpokesWalker, together with an immutably borrowed Dcel, wrapped in an iterator.

HalfSpokesReverseIter

Iterator over half-spokes of a vertex in backward direction. This is HalfSpokesReverseWalker, together with an immutably borrowed Dcel, wrapped in an iterator.

HalfSpokesReverseWalker

Walker over half-spokes of a vertex in backward direction.

HalfSpokesWalker

Walker over half-spokes of a vertex in forward direction.

SpokesIter

Iterator over spokes of a vertex in forward direction. This is SpokesWalker, together with an immutably borrowed Dcel, wrapped in an iterator.

SpokesReverseIter

Iterator over spokes of a vertex in backward direction. This is SpokesReverseWalker, together with an immutably borrowed Dcel, wrapped in an iterator.

SpokesReverseWalker

Walker over spokes of a vertex in backward direction.

SpokesWalker

Walker over spokes of a vertex in forward direction.

Vertex

The data which describes a vertex.

VertexId

An index pointing to a vertex.