CODEWITHSUNDEEP
algorithmlanguage-agnosticgeometrycomputational-geometry
guerda
guerda

Reputation: 24049

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 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.

Upvotes: 3

Views: 2053

Answers (3)

guerda
guerda

Reputation: 24049

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.

Upvotes: 2

martiert
martiert

Reputation: 1686

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.

Upvotes: 0

Reed Copsey
Reed Copsey

Reputation: 564433

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.)

Upvotes: 5

Related Questions