I have been trying to create an algorithm that can reliably detect and then remove self intersections in concave polygons.
Currently, I loop through each side and check it against every other side to see if there is an intersect. By using this method, I am able to detect all of the sides that intersect with one another and I get the coordinates for the intersection point.
But this is where I run into problems. Pictures A and B are of the same polygon, but the vertices are in a different order.
My algorithm starts from side 1 and compares it against all other sides and then moves on to side 2 and repeats the process until it has checked all sides. When it encounters an intersection, the algorithm leaves the last vertex of the first side and the first vertex of the last side and then it removes all of the vertices in between them. Finally, it adds a new vertex on the intersect point.
This method works perfectly as long as the first vertex of the polygon is not within the area that is supposed to be removed. For example, as seen in the Polygon B image, sides 2-3 and 5-6 (i.e. the second and fifth sides) intersect. The algorithm would leave vertices 2 and 6 untouched, but everything that is larger than 2 and smaller than 6 is removed. However, if the first vertex of the polygon is within this area, as seen in the Polygon A image, the algorithm breaks. With Polygon A, sides 1-2 and 8-9 intersect, which would cause the algorithm to delete almost the entire polygon.
Visually, this is a simple task and I know what vertices should be deleted in both cases. However, I have absolutely no idea on how to detect if the first vertex of the polygon is within that area.
Does someone have an idea on how I could accomplish that? Or better yet, is there some better and completely different method that I should be using to tackle this matter?
Best Answer
Start iterating from the vertex with minimim coordinate values $x$ and $y$. You need only a single vertex of the convex hull to start from and this is it.