Given a map of vertices {(x1,y1), (x2,y2), ... (xn,yn)}, how can I generate a 2D triangular mesh covering all vertices, and where the area of all triangles completely covers the map?

The triangular areas may fully enclose other triangular areas, but no two triangles may intersect.


1 Answer 1


First you need to create a polygon from the points. One way to do that is start with the point with the smallest x (since that has to be part of the final polygon). Let's call that point A. Then you need to find the next point of the polygon. Since the polygon has to contain all the other points you can pick one (B) and test if all the other points are to the right of that line. If you find a point to the left you set that to B instead. In the following picture the blue line is the edge we're testing and the green is the point we're testing against: enter image description here

The line from A-B is then the first edge of the polygon. After that you do the same thing with B as A. Repeat this until the next point in the polygon should be the first point, i.e. you've closed it. In the example above you'll get this:

enter image description here

The next step is to triangulate it. There are many algorithms for this, but if you want to do it yourself I'd recommend ear clipping since your polygon won't contain any holes.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .