Geek Answers Handbook

Polygon and Triangulation

Hey, so I recently asked this question about how to cut a concave polygon into convex ones, and I was offered to make triangulation or polygonal separation.

The library I use (SFML \ Box2D) accepts only convex forms.

This is what I want to know:

  • Is the polygon partially or triangulation of the polygons faster?

  • How Polygon Partioning Works / How Do You Do It?

Do not forget that triangulation does not require the creation of convex forms ...

+7
source share
2 answers

Not a complete answer to your question, but if you have a common polygon (concave, convex, any), and you want to triangulate it (perhaps for subsequent rendering in the OpenGL style), you could look at packages with a Delaunay triangulation constraint, One of these examples is the Triangle package, which is considered fast and reliable.

As I understand it, the algorithms used in Triangle show O(nlogn) runtime complexity.

+4
source

Splitting a polygon splits your polygon into convex polygons. Triangulation breaks it into triangles. As far as I understand, triangulation requires that you first split polygons, since splitting a convex polygon into triangles is relatively trivial. Separating a polygon into convex polygons is the hard part. I wrote a program that runs for a class, and if you want, I can dig it out.

Here is my code: https://github.com/meshko/triangulator/tree/master/som

I have not touched 10 years, so beware.

+4
source

More articles:


All Articles