mapbox / mapbox/delaunator

Conforming/Constrained Delaunay

Open
#9 16 comments 10 reactions 0 assignees View on GitHub
enhancement
Dominant language
JavaScript
Stars
2.6k
Forks
152
PR merge metrics
No merged PRs in 30d

Description

Conforming or constrained triangulation would be utter-cool. Input can be points, lines and polygons while output edges will not cross existing input edges. _Conforming_ would introduce new points in order to be true delaunay triangles (steiner points) while _constrained_ is not always truely delaunay but doesn't introduce extra points.

Relevant information:
- [http://www.cs.cmu.edu/~quake/triangle.defs.html#conform](http://www.cs.cmu.edu/~quake/triangle.defs.html#conform)
- [http://www.cs.cmu.edu/~quake/triangle.delaunay.html](http://www.cs.cmu.edu/~quake/triangle.delaunay.html)
- [http://lin-ear-th-inking.blogspot.nl/2009/04/delaunay-triangulation-in-jts-111.html](http://lin-ear-th-inking.blogspot.nl/2009/04/delaunay-triangulation-in-jts-111.html)

Contributor guide

Open the contributing guide

Research direction

Start with the external Triangle and JTS references linked in the issue, then inspect the repository's current triangulation API and implementation. Done means supporting points, lines, and polygons without crossing input edges, with conforming mode adding Steiner points for true Delaunay triangles and constrained mode avoiding extra points.

Written by the indexing model from the issue text.

Assessment

Tech stack
javascript
Domain
computer-graphics
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.