# Many triangles to few polygons

## Recommended Posts

Hi guys. I recently stumbled upon this problem: I have a list of triangles that is: 1. in indexed form 2. given as a list of independent triangles How do I compute(efficiently) a minimal(or near to minimal) set of convex polygons from the initial list(s) of triangles?

##### Share on other sites
oh boy. I assume it's 2D.

I think the first step would be to construct the neighbour information (topology) between all triangles. What triangles neighbour a triangle, what edge belong to which triangle(s).

Then, start from point, with an edge that has no neighbour (only belongs to one triangle). This edge is an edge on the 'border' of the map, preferably not a edge that belongs to an internal concave loop (imagine a ring, you should select a point on the outer edge of the ring, not the inner edge, basically, an edge with a 'convex' point).

Then follow the edges, taking the path of the most convex one. At some point, you will loop back to a point of your search, hopefully, it will be the very first one. That loop should then be convex. if it is not, then your map has some overlapping triangles, and that's bad.

Now it's done, you can remove that portion from your map, (sever the edge and triangle links), and start your search again.

That's also assuming there are no weirdness in your map, and it's nice and topologically correct.

You can detect some dodgy cases when you start building your topology. For example, if you find an edge belonging to three triangles, than there is something wrong with your data. Or if vertices overlap, ect...

##### Share on other sites
Are the triangles joined? This sounds like the convex hull problem

http://www.cs.princeton.edu/~ah/alg_anim/version1/ConvexHull.html

##### Share on other sites
Quote:
 Original post by gpuloveHi guys. I recently stumbled upon this problem:I have a list of triangles that is:1. in indexed form2. given as a list of independent trianglesHow do I compute(efficiently) a minimal(or near to minimal) set of convex polygons from the initial list(s) of triangles?

I assume you have a 2D problem. Otherwise, you will need to define what you mean by "minimal set of convex polygons".

First, you need to identify the connected components of the triangles. Each component consists of triangles that share an edge with some other triangle. This is fairly easy code to write, using STL, and produces a disjoint set of meshes. Second, for each mesh component, locate the boundary edges of the mesh. This gives you a simple polygon. Third, apply a convex decomposition of this polygon. Search on Keil and Snoeyink for a paper on such an algorithm (uses dynamic programming); this is a nontrival problem. If you want nearly optimal, search on Hertel and Melhorn.

##### Share on other sites
Thanks for the replies guys!

## Create an account or sign in to comment

You need to be a member in order to leave a comment

## Create an account

Sign up for a new account in our community. It's easy!

Register a new account

• ### Forum Statistics

• Total Topics
628366
• Total Posts
2982274

• 10
• 9
• 13
• 24
• 11