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
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?
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
trianglesarray. A counter example can be found in the following code:which prints
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?