mapbox / mapbox/delaunator

Not all points triangulated

Open
#94 1 comment 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

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

Description

Hello, and thank you for this project!

While investigating issue 15 of Constrainautor, I found that one of my assumptions about the output of Delaunator does not hold. I assumed that every point will have at least one incoming half-edge (and at least one outgoing one), i.e. every point-index should appear at least once in the resulting triangles array. A counter example can be found in the following code:

const coords = [
    [0,0],
    [0.05626429153399996,0],
    [0.024093852080076722,4.80267923973791e-18],
    [0.01379050745122589,0.1463775332929564],
    [0.05177587092034522,0.015468457826306506],
    [0.024093852080076705,-5.204170427930421e-18],
];
const del = Delaunator.from(coords);
for(let pnt = 0; pnt < coords.length; pnt++){
    if(!del.triangles.includes(pnt)){
        console.error(`point ${pnt} not triangulated`);
    }
}

which prints

point 5 not triangulated

on my machine.

I see similar results when triangulating robustness1.json, ukraine.json, and others, from the Delaunator cases.

A very cursory glance at the Delaunator source code seems to corroborate the conclusion that Delaunator will skip 'near-duplicate' points. However, I might be missing something due to not having studied the code extensively enough.

Without existing incoming/outgoing half-edges to some point, Constrainautor cannot generate any constrained edge between that point and any other point, since it works by flipping existing edges. My question is: is my assumption invalid, is it a bug in Constrainautor, or a bug in Delaunator, or something that could be clarified in the documentation?

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

Reproduce the coordinate example with Delaunator.from(coords), then compare the result with robustness1.json and ukraine.json from the Delaunator cases. Read the near-duplicate handling in index.js around the linked line 219 and determine whether omitted points are expected; done requires a decided behavior or documentation direction for Constrainautor users.

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
Stale
Clarity
Needs clarification
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.