0

Hey so i was told in a previous answer that to make concave shapes out of multiple convex ones i do the following:

If you don't have a convex hull, perform a package wrapping algorithm to get a convex border that encompasses all your points (again quite fast). en.wikipedia.org/wiki/Gift_wrapping_algorithm

Choose a point that is on the boarder as a starter point for the algorithm.

Now, itterate through the following points that are on your shape, but aren't on the convex border. When one is found, create a new shape with the vertices from the starter point to the found non-border point. Finally set the starter point to be the the found off-border point

Recursion is now your friend: do the exact same process on each new sub-shape you make.

I'm confused on one thing though. What do you do when two vertices in a row are off-border? After reaching the first one you connect the starter point to it, but then you immediatly run into another off-border point after you start itterating again, leaving you with only 2 vertices to work with: the starter point and new off-border point. What am i missing?

To illustrate my problem, here's a shape pertaining to this issue: It would be great if someone could draw all over it and walk through the steps of the algorithm using this. And using point 1 as the starting point.

enter image description here

Thanks!

Community
  • 1
  • 1
Griffin
  • 2,399
  • 7
  • 48
  • 83
  • Do you mean that you want to create a convex shape from a concave one, not the other way around?? – Darren Engwirda Jul 14 '11 at 08:27
  • Or are you trying to triangulate the polygon?? i.e. form a concave polygon from multiple (convex) triangles?? – Darren Engwirda Jul 14 '11 at 08:33
  • @Darren: not quite, I think. If a polygon is convex but has more than three vertices, then the described algorithm leaves it alone, and the questioner's description is "convex pieces", not specifically triangles. Triangulating would provide *a* solution, but for shapes that are convex to begin with, or that have large convex subsets of vertices, it will split it into a lot more polygons than the requirements demand. – Steve Jessop Jul 14 '11 at 09:08
  • The previous answer is plain wrong, that's all. The proposed algorithm won't work. Google "polygon partitioning", or look it up in "Computational Geometry in C" by Joseph O'Rourke. – n. m. could be an AI Jul 14 '11 at 10:11

1 Answers1

0

Assuming you really want to take a convex polygon (as you've illustrated) and decompose it into convex parts without introducing new vertices, the usual approach is called "ear clipping" and is described in this Wikipedia article, Polygon triangulation. In this approach the convex pieces are triangles, which are necessarily convex.

This problem has been discussed in connection with the CGAL computational geometry software here in Stackoverflow, C++ 2D tessellation library.

Community
  • 1
  • 1
hardmath
  • 8,753
  • 2
  • 37
  • 65