0

I've checked multiple related answers but none seem to capture the problem I face.

  1. I have to triangulate various polyhedra.
  2. Each polyhedral face is closed.
  3. Faces are usually convex but not exclusively.
  4. Faces can occasionally be self-intersecting but if so they probably have radial symmetry (for example a pentagram)
  5. Each face is mostly planar (I'm prepared to suffer the consequences if not as it's technically an error)

By observation it seems that adding a new vertex at the centroid and creating a new face by connecting each edge to this vertex always successfully triangulates the face. However - it has a performance cost and simple fan triangulation also succeeds in 95% of cases. However when it fails it fails badly.

Is there an efficient way to detect self-intersecting and/or concave faces so I can fall back to the slower path? Obviously the detection algorithm has to be pretty efficient if the cost of checking isn't to exceed the cost of just assuming the worst and using centroid triangulation in all cases.

I actually suspect my energies are better spent on optimising centroid triangulation rather than working on detecting if it's actually necessary but I was curious what the Stack Overflow community thought.

Andy Baker
  • 21,158
  • 12
  • 58
  • 71
  • For determining whether a polygon is convex or not, see [this question](/questions/471962/how-do-i-efficiently-determine-if-a-polygon-is-convex-non-convex-or-complex). For 3D, this may work unless the polygon's points all have the same X-coordinate or all the same Y-coordinate. – Peter O. Dec 27 '18 at 03:52
  • Centroid triangulation can also fail (imagine an E-shaped or U-shaped face). – Nico Schertler Dec 29 '18 at 07:55
  • @NicoSchertler - yep. I actually mentioned that in the first paragraph after my numbered list. Currently it won't happen because of how the polyhedra are constructed. – Andy Baker Dec 29 '18 at 16:45
  • 1
    Have you considered simply running a pass of [ear clipping](https://en.wikipedia.org/wiki/Polygon_triangulation#Ear_clipping_method)? It first classifies all corners. If you find that all corners are convex, you can continue with fan triangulation. – Nico Schertler Dec 30 '18 at 10:21
  • @NicoSchertler - yep but it seems like that is past the threshold where it will be any better than just doing a centroid triangulation in all cases. According to Wikipedia does mention an efficient algorithm but it's still pretty complex. There are also simpler algorithms here: http://cgm.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Ian/cutting_ears.html but they only work on a limited range of input polys - none of which seem to apply to me. – Andy Baker Dec 31 '18 at 14:02

0 Answers0