I'm sticking this in extension ideas since I'm solving this problem in Java, and could potentially expand it into something more. I am not particularly experienced in Java, but that makes it a learning experience. I decided that I wanted to program a way to split a given concave polygon (for it to be a polygon I am viewing that it means none of its lines cross for now) into multiple convex polygons which join together to make that one concave polygon (but can be used for collision engines).
If I allowed shaped to be cut along the edges (as opposed to just along the vertices), then in Box2D, clipping would occur. This is when two objects catch along an apparently straight line in the joins in collision boxes (since Box2D doesn't have pixel perfect collision). Therefore, I want to cut shapes by their vertices.
Currently my algorithm I have come up for this is something like this. I take a concave polygon. I will use this one as an example:
Once I have this shape I iterate through each of the points, marking it if the angle at it is reflex (more than 180 degrees). For the example shape, this leave me with this:
Next comes a quite complicated part. For each of those points (if there are none I just return the shape), I check how many points I can go in either direction until I either reach a reflex angle, or the angle from that point through the point to the next point is more than 180 degrees. This can be marked on our shape like this (dark blue is point, light blue is points one way and brown is the points the other way).
When I have this, I identify which of these gives me the most points in a shape and chose that one. In the case of the example, there are two choices we can make (the brown on the first and the third), so we chose the first one. We then seperate these points from the shape to make a new shape:
Once we have done this we take the new shape formed and repeat the process.
We count the reflex angles:
We check for both of them:
We pick one and split it.
And then we do the same with the next shape:
Finally, we are left with a shape that has no reflex angles so we end with our shape broken up.
As of speaking, I have written a program to do this in Java, but without any visual interaction (you literally input a list of numbers representing a shape), so next part to work on is displaying an input and an output. So far this project has been very enjoyable.
