How to triangulate a polygon without random inner points?

I would like to create triangles a predefined polygon. My requirement is that I don't want to create random points inside of this polygon for processing it with a Delaunay Triangulation algorithm.

The polygon can be concave or convex.

It's totally ok for me to use a Delaunay Triangulation but I don't want to create random points inside the polygon. It would be much nicer if I can create as less points as possible inside开发者_如何学Python this polygon.

I would like to minimize the number of used triangles.

How can I establish this?

Comment: It's more a language agnostic thing, I like to know how to implement this on my own.

---

You can use Ear Clipping or monotone polygons. Neither algorithm will introduce extra points.

(If you choose to form monotone polygons, the monotone polygons are convex, and can be broken into triangle fans directly.)

---

I found the very helpfull library Poly2Tri. The Java branch of this library does exactly what I need.

I just need to use it correctly. It does not add any points to the polygon.

---

If the polygon is convex, it's easy to just use the boundary and triangulate using points along the boundary. If it's non-convex I would make a convex boundary, and mark the points inserted as inserted. Then, when done with everything else, remove the inserted points.

You can also use a mesh refinement algorithm to refine the mesh if you get long and thin triangles. Using Delaunay you can just check if a triangle is "thin" by some definition, and if it's "thin" insert a point in the circumcenter of that triangle. Thus all you then have to do is use Delaunay theory.