How to create a concave polygon from an ordered list of points?

[robinmoussu]

I would like to test the distance between a point and a (possibly concave) polygon. If the point is inside the polygon, I'm expecting to get a distance of 0.

I have an ordered list of points that describe a hull of a (possibly concave) polygon. I was expecting that creating the concave polygon would be as simple as creating a polyline or a convex polygon (by providing this list of point to the constructor of a shape), but I didn't found an easy way to do it. What is currently the best way to do it?

#228 seems dead, hence why I created a new issue.

[sebcrozet]

Hi!

As you figured out, ncollide does not have any easy way of constructing a concave polygon. You could use a Polyline and use point-projection to obtain the distance, but you won't get 0 if the point is inside of the polygon described by the polyline.

So you basically have two choices:

1. Decompose your concave polygon into a set of convex polygons and put these on a Compound shape. However convex decomposition is not a trivial task.
2. Or use a Polyline, compute the distance after checking if the point is inside of the polygon. To check that the point is inside on the polygon, you can use the winding number algorithm (which is not implemented in ncollide yet).

[robinmoussu]

I played with the idea of decomposing a concave polygon into a set of convex polygon a bit, and I have a POC. I am not sure that I will have time to clean-it this week-end, by I will do I PR it a few days.

I used space to triangulate the points of the concave hull, then filtered the triangle that are inside the hull (triangle inside the hull have their vertex in the same order than the hull).