 # [math] How to create a concave polygon from it's hull using only convex shape

This more a math question than a Rust question, but I don't know where to ask.

I am using ncollide2d to compute the distance between a shape and a point. Unfortunately, ncollide2d can only easily manipulate concave shape. It is possible to create concave shape using the `Compound` struct.

I have an ordered list of points that describe the hull of a (possibly concave) polygon. How do I create this polygon using only triangles and/or convex polygons? The full area of the inside of the hull must be filled with those triangles and polygons.

When searching on internet, I found many algorithm that create the convex hull from an unordered set of points, but it's not what I want since I already have the hull. All I want is to fill the inside of the hull using only convex shape.

Any help (including where to ask) would be welcome.

Usually one would turn it into triangles instead of trying to use more complicated convex pieces. This is called triangulation.

I'm not 100% sure I understand what you're asking here, but creating a convex hull from a concave polygon loses information. You can't take a convex hull and turn it "back" into a concave shape unless you saved the interior points (and the original ordering of vertices) somewhere.

I think this was the right direction. I'm currently testing this: I triangulate all the points of my convex hull, then takes only the triangle that are inside the hull. To detect if the triangle is inside the hull, first I assign a number to each vertex (in the same order than the hull), then for each triangle, if the 3 vertex are increasing order, this means that the triangle is inside.

I want to create a concave shape by assembling concave shape.

Wikipedia describes several algorithms to do this of varying performance and complexity: https://en.wikipedia.org/wiki/Polygon_triangulation

2 Likes

For those interested, this is how I did it.

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.