-1

I've found a good sample of triangulation: High performance version by Salvatore Previti in C# 2.0.

The left side of the mesh is twisted in the following image. Is there some way to prevent it?

triangulation

tuomastik
  • 4,559
  • 5
  • 36
  • 48
Vladimir Bilichenko
  • 3
  • 3
  • Hi, I wrote that code long time ago, mostly for experimentation, 10 years ago or so. It is a bug, because a Delaunay triangulation is supposed to provide also a convex hull, the smallest CONVEX polygon that contains all points in, and that polygon is not convex at all. There is an edge missing, indeed, between the top left and bottom left points. At the moment I don't have much time to take care of it, can't debug the code, and of course I don't even remember much of it :) – Salvatore Previti May 28 '17 at 16:40
  • Did you try with another implementation of the same algorithm and see if the same problem happens? Try http://paulbourke.net/papers/triangulate/c_sharp.zip and see if it has the same bug or not – Salvatore Previti May 28 '17 at 16:42
  • Thanks man for your reply. I'll try: http://paulbourke.net/papers/triangulate/c_sharp.zip – Vladimir Bilichenko May 28 '17 at 19:38
  • It has the same bug – Vladimir Bilichenko May 28 '17 at 19:40
  • Interesting, indeed there is a bigger issue here, some common misunderstanding of the algorithm in two implementations? I should spend some time in trying to fix it, if you find why, please, let me know, I will try to look in the meantime. – Salvatore Previti May 28 '17 at 19:49
  • 1
    Of course, i let you know if I find the problem. One more time, thanks for your help. – Vladimir Bilichenko May 28 '17 at 19:55
  • Possible duplicate of [Bowyer-Watson algorithm: how to fill "holes" left by removing triangles with super triangle vertices](https://stackoverflow.com/questions/30741459/bowyer-watson-algorithm-how-to-fill-holes-left-by-removing-triangles-with-sup) – Micromega May 30 '17 at 15:58

1 Answers1

1

Possible duplicate: So I have found a relatively cheap but imperfect work-around. My super triangle is programmatically determined to surround the sites' bounding box without intersecting its sides. This idea was caused by all sorts of frustrating problems with Java considering some of my calculated circumcenter coordinates or distances between coordinates to be infinite. This caution led me to make my super triangle so small that its vertices sometimes fell in valid triangles' circumcenters. Increasing the size of the super triangle has made the problem seem to disappear. However, it is possible that a triangle on the convex hull can be so obtuse that one of the vertices still could fall inside a valid circumcircle.

[1]Bowyer-Watson algorithm: how to fill "holes" left by removing triangles with super triangle vertices

Micromega
  • 12,486
  • 7
  • 35
  • 72
  • I've found good sample of triangulation implemented on Unity. https://github.com/parahunter/triangle-net-for-unity It also implemented as dll: https://triangle.codeplex.com/ – Vladimir Bilichenko May 31 '17 at 16:19