quad-edge

Important

‼️ Announcing the thi.ng user survey 2024 📋

Please participate in the survey here!
(open until end of February)

To achieve a better sample size, I'd highly appreciate if you could circulate the link to this survey in your own networks.

Discussion

Note

This is one of 189 standalone projects, maintained as part of the @thi.ng/umbrella monorepo and anti-framework.

🚀 Help me to work full-time on these projects by sponsoring me on GitHub. Thank you! ❤️

• About
• Status
• Related packages
• Installation
• Dependencies
• API
• Authors
• License

About

Quadedge data structure after Guibas & Stolfi.

See the related @thi.ng/geom-voronoi package for concrete usage. This package merely provides the underlying graph data structure.

Reference:

• http://www.cs.cmu.edu/afs/andrew/scs/cs/15-463/2001/pub/src/a2/quadedge.html
• https://github.com/thi-ng/c-thing/blob/develop/src/geom/quadedge.h
• Guibas & Stolfi: Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams, ACM Transactions on Graphics, 4, 1985, p.75-123

Status

STABLE - used in production

Search or submit any issues for this package

Related packages

• @thi.ng/geom-voronoi - Fast, incremental 2D Delaunay & Voronoi mesh implementation

Installation

yarn add @thi.ng/quad-edge

ES module import:

<script type="module" src="https://cdn.skypack.dev/@thi.ng/quad-edge"></script>

Skypack documentation

For Node.js REPL:

const quadEdge = await import("@thi.ng/quad-edge");

Package sizes (brotli'd, pre-treeshake): ESM: 559 bytes

Dependencies

• @thi.ng/errors

API

Generated API docs

TODO

Authors

• Karsten Schmidt

If this project contributes to an academic publication, please cite it as:

@misc{thing-quad-edge,
  title = "@thi.ng/quad-edge",
  author = "Karsten Schmidt",
  note = "https://thi.ng/quad-edge",
  year = 2015
}

License

© 2015 - 2024 Karsten Schmidt // Apache License 2.0