search

artem-ogre / CDT

Constrained Delaunay Triangulation (C++)
https://artem-ogre.github.io/CDT/
Mozilla Public License 2.0
1.02k stars 129 forks source link

bugs: duplicate point during triangulatePseudoPolygon are not handled #70

Closed LeGamerDc closed 2 years ago

LeGamerDc commented 2 years ago

according to paper,in insert edge step, there might be duplicate points of left point and right point. say we have a edge[1, 2], after eliminate triangle, we have [3, 4, 5, 4, 6] in left points, and we have a two triangle not tie right neighbor(of edge [4, 5]), so we must fix their neighbor after we do two triangulatePseudoPolygon.

since i'm not familiar with cpp, i could not give a merge request, sorry about that.

artem-ogre commented 2 years ago

Could you provide an image illustrating the issue perhaps? I am afraid I don’t follow your explanation.

artem-ogre commented 2 years ago

An input for reproducing the issue would be the best.

LeGamerDc commented 2 years ago
企业微信截图_285d1f40-d54c-438b-8158-a206f713d9e6

take the graph from paper, we could find the Pu after eliminate triangle is [dedg], the vertex d appear twice. if later we triangulate result is tri (abe) (aed) (ebd) (dbg), then triangle (aed) and (ebd) would miss each other as neighbor.

LeGamerDc commented 2 years ago

so, we should find pattern [aba] in Pu and Pl, and fix the edge [ab]'s neighorship

artem-ogre commented 2 years ago

@LeGamerDc Hanging vertices are already handled properly in CDT. This exact case is represented in file Hanging.txt. You can run CDT on that input and inspect resulting triangles. All the neighboring information for the triangles should be set properly.

Please come back to confirm this or let me know if something is overlooked.