Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Triangulate Concave Shape

  1. Mar 16, 2009 #1
    I am looking for a "good" way to triangulate a closed concave shape of vertices and edges.

    "good" is quite a vague term, but the basic principles I'm interested in are:
    1) Minimize "sliver" triangles that are very thin and contain really small angles.
    2) Must be reasonable to compute. Ideally it would take less than a day to compute the triangulization for a mesh with ~10,000 vertices on a standard computer (so complete brute force is out).

    Here is a diagram (initial shape in black):
    http://img394.imageshack.us/img394/3077/concavetriangle.png [Broken]

    If the mesh was convex, a good strategy would be http://en.wikipedia.org/wiki/Delaunay_trianglulation [Broken] method could work well if I had a fast way of finding the worst possible triangle among a subset of the shape, but I'm having no luck there.
    Last edited by a moderator: May 4, 2017
  2. jcsd
  3. Mar 16, 2009 #2


    User Avatar
    Science Advisor
    Gold Member

    Suggestion (it may not be very good): Form the convex hull of the polygon. Use Delaunay, being careful you don't cross any existing lines. Get rid of lines outside original polygon.
  4. Mar 16, 2009 #3
    I think the Delaunay triangulization is unique
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Triangulate Concave Shape
  1. Triangulation Report (Replies: 0)

  2. Strange triangulation (Replies: 2)

  3. Triangulated radius (Replies: 8)