search

gradientspace / geometry3Sharp

C# library for 2D/3D geometric computation, mesh algorithms, and so on. Boost license.
http://www.gradientspace.com
Boost Software License 1.0
1.71k stars 384 forks source link

Extra Vertex in TriangulatedPolygonGenerator #145

Closed runette closed 3 years ago

runette commented 4 years ago

Hi

I am using TriangulatedPolygonGenerator to mesh Polygons with holes. It mostly seems to work very well, but sometimes it seems to add a vertex to one of the linear rings of the polygon. I have not been able to work out a pattern to why it is doing this.

Do you have any idea of why this is happening?

This is a problem since what I am actually doing is using this to triangulated a 2.5D Polygon - using OrthogonalPlaneFit3 to find the nearest plane, projecting the vertices onto the plane as a Polygon2D and then creating the triangulation. Unfortunately, I cannot project back to the original points - I have to do a matching between the Polygon2D vertices and the 3D vertices in the triangulation (and there does not seem to be a simple mapping between the vertices in the final mesh and the vertices from the original Polygon2D). At the moment I have to do some fancy footwork around the extra vertex if it there - and it also means that I do not have round trip integrity.

rms80 commented 4 years ago

The triangulation method used in TriangulatedPolygonGenerator does this, sorry. It's because it does not actually triangulate the polygon, it cuts the polygon into a mesh (a rectangle formed from 2 triangles), by incrementally inserting the edges. Sometimes this adds vertices. It's not really the right way to triangulate a polygon - Delaunay triangulation works better, but the library does not have an implementation of that.

TriangulatedPolygonGenerator is just a wrapper around MeshInsertUVPolycurve, which has a function Simplify() which will try to remove these extra vertices. However it doesn't always work.

runette commented 4 years ago

Thanks

On Sun, 16 Aug 2020, 06:26 Ryan Schmidt, notifications@github.com wrote:

The triangulation method used in TriangulatedPolygonGenerator does this, sorry. It's because it does not actually triangulate the polygon, it cuts the polygon into a mesh (a rectangle formed from 2 triangles), by incrementally inserting the edges. Sometimes this adds vertices. It's not really the right way to triangulate a polygon - Delaunay triangulation works better, but the library does not have an implementation of that.

TriangulatedPolygonGenerator is just a wrapper around MeshInsertUVPolycurve, which has a function Simplify() which will try to remove these extra vertices. However it doesn't always work.

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/gradientspace/geometry3Sharp/issues/145#issuecomment-674477226, or unsubscribe https://github.com/notifications/unsubscribe-auth/AARC2MZQPL3EH6VPJR2SBA3SA5NWJANCNFSM4O52EGRQ .