mapbox / mapbox/delaunator

Degenerate triangles on boundary

Open
#91 2 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

bug
Dominant language
JavaScript
Stars
2.6k
Forks
152
PR merge metrics
No merged PRs in 30d

Description

I've been chasing an unexpected behavior and boiled it down to a very basic input. I'm adding points to an existing triangle (on boundary, inside, etc) and using Delaunator to retriangulate and Constrainautor to constrain certain edges. I've been getting degenerate triangles on the boundary.

Consider this input:

[[0, 0], [30.51591076416662, -5.272057753973058], [13.955446995823877, 16.74653639495955], [22.3355613751919, -3.8587860099360114]]

The first three points are the original triangle, and the last point is one I add, which was inserted on the edge [P0, P1]. Delaunator treats the 4th point as inside, instead of on the convex hull.

I get the following triangles:

[2, 3, 0], [3, 1, 0], [2, 1, 3]

And the hull:

[2, 1, 0]

A visual of the data, where the blue line is the degenerate triangle (note, I'm in a +Y up coordinate system, so everything's CW) -

Image

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start by reproducing the reported result with the four-point input using Delaunator, then inspect how it classifies the fourth point and constructs the hull and triangles. Done means the boundary point no longer produces the reported degenerate triangle while the triangulation and hull remain valid.

Written by the indexing model from the issue text.

Assessment

Tech stack
javascript
Domain
computer-graphics
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Quiet
Clarity
Needs clarification
Newbie friendliness
42/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.