Search code examples
algorithmpolygontriangulation

What is a Steiner point in poly2tri?


The poly2tri Readme talks about Steiner points, what are they? (Is it related to triangle Steiner points?)

Why would one add Steiner points?


Solution

  • Poly2tri has the ability to add something called Steiner Points. You can add these inside a polygon to get a triangulation with shorter edges

    Here are a few resources from what you have posted:
    1.Triangulation of spline to mesh, questions and results (read the comments)

    2.Youtube Video with concept: Triangle Tribualtions



    Conceptually, i believe these are linked with the famous NP-complete Steiner Tree Problem

    From Wikipedia:

    The Steiner tree problem is superficially similar to the minimum spanning tree problem: given a set V of points (vertices), interconnect them by a network (graph) of shortest length, where the length is the sum of the lengths of all edges. The difference between the Steiner tree problem and the minimum spanning tree problem is that, in the Steiner tree problem, extra intermediate vertices and edges may be added to the graph in order to reduce the length of the spanning tree. These new vertices introduced to decrease the total length of connection are known as Steiner points or Steiner vertices. It has been proved that the resulting connection is a tree, known as the Steiner tree. There may be several Steiner trees for a given set of initial vertices.

    Also, you might want to look at Euclidean Steiner Tree on the wiki page. Seems relevant to your problem