mapbox
Triangulation does not preserve original edges
In the above image, the two neighbor triangles (where the red arrow points) are not fully connected, while all other neighbor triangles are.
(please let me know if I didn't make myself clear.)
@mikelmaron @hjanetzek @zugaldia @incanus @springmeyer sorry to disturb, but this issue is important to me. can any of you guys answers it for me? thanks in advance
@mikelmaron @hjanetzek @zugaldia @incanus @springmeyer @zzfoo
I changed pointInTriangle() to
// check if a point lies within a convex triangle
function pointInTriangle(ax, ay, bx, by, cx, cy, px, py) {
return (cx - px) * (ay - py) - (ax - px) * (cy - py) > 0 &&
(ax - px) * (by - py) - (bx - px) * (ay - py) > 0 &&
(bx - px) * (cy - py) - (cx - px) * (by - py) > 0;
}
change >= to > .
It could solve this problem ， but I don't know whether it is the best way.
My test case :
var testPoints = [
[
[10, 10], [300, 10], [10, 300]
],
[
[50, 50], [100, 50], [50, 100]
],
[
[150, 50], [200, 50], [150, 100]
],
];
Just replace the testPoints in viz.js
.
Is this behavior causing any particular issues? It seems like a result I would expect.
@mourner
Current result of earcut is :
I would expect is :
I think the result of Polygon triangulation should be a mesh， One border could most belong to two triangles.
If one border shared to many triangles ， the triangulation will lost the value in the real-world（e.g. ： NavMesh Pathfinding , Mesh Transform )
NavMesh Pathfinding:
Mesh Transform:
Maybe earcut would not be used in those use case , but it's the base of Polygon triangulation, I hope it could support this feature.
And , there is result of current version earcut :
You look the triangles below two rect holes ， they are correct， But the triangles above two rect holes are wrong.
@mourner , there is a document about Triangulation : https://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf It said that :
The key point : "Each vertex shares exactly two edges. The only place where edges are allowed to intersect are at the vertices."
In the famous & classic book "Geometric Tools for Computer Graphics" ， there is similar claim :
The key point : "The edges are only allowed to intersect at the vertices. "
.
In fact, by definition, the result of current version earcut in my test case is not Triangulation at all.
. I'm a Chinese guy , with bad english , I hope you could understand me. If my words is impolite ， I hope you could forgive me . It's not because I'm impolite , just because my poor english , I don't know how to express my opinion in the right way.
And the most words above are translated by google.
.
I see the issue now — thanks for the explanation. I don't have immediate suggestions to fix this — this problem might stem from the original tactics from https://www.cosy.sbg.ac.at/~held/projects/triang/triang.html to deal with degenerate cases by filtering out collinear points at various stages of the algorithm. Needs investigation.
Thank you , @mourner .
And there is a better test case :
// replace the testPoints in viz.js.
var testPoints = [
[
[10, 10],
[300, 10],
[300, 300],
[10, 300]
],
[
[50, 50],
[100, 50],
[100, 100],
[50, 100]
],
[
[150, 50],
[200, 50],
[200, 100],
[150, 100]
],
[
[50, 150],
[100, 150],
[100, 200],
[50, 200]
],
[
[150, 150],
[200, 150],
[200, 200],
[150, 200]
],
];
My solution can't solve this bug in this test case, So I think this test case is more representative.
@mourner , I think the bug at eliminateHoles().
The node linkList that return value of eliminateHoles in my test case is this :
I think the correct one should be like this :
And , whatever , 10 ,11 ,12 will be in one line , the filterPoints will remove 11.
@mourner I'm using earcut.js to divide the walkable area of our game map into triangles. I was expecting all the triangles are fully connected with their neighbors such that game characters can walk from one triangle area to another unobstructedly as long as they are walking through the common edge. anyway, if this bug can't be fixed in the near future, then I have to find another solution. thanks a lot for your reply.
@mourner , I create a new version at : https://github.com/finscn/earcut/blob/master/src/earcut.js It just can't pass only 3 test cases : 'steiner', 'water-huge', 'water-huge2'.
And for steiner test , the current earcut can't get correct result too.
It's missing the blue line.
No updates on this yet unfortunately. If anyone has an idea on how to fix the issue without breaking existing test cases, I'll be glad to see a PR!