3
$\begingroup$

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.

Polygon B - first vertex outside of the intersect area

Polygon A - first vertex inside of the intersect area

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?

$\endgroup$
  • $\begingroup$ "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." So for Polygon B, you leave vertices 3 and 5, delete 4, and put a new vertex X at the intersection of 23 and 56? Where is X in the new polygon: before 3, after 5, between 3 and 5, or did you actually finally delete 3 and 5 when you inserted the new vertex? $\endgroup$ – David K Jul 25 '18 at 12:31
  • $\begingroup$ I may have phrased that poorly. At the intersection of 23 and 56, the first vertex in this intersection, for the algorithm, is 2, which it leaves as is. It then deletes all of the vertices between 2 and 6, and then adds the new vertex X as the new vertex 3. Finally, it reassigns each subsequent remaining vertices a new number so that there are no gaps, i.e. old vertex 6 becomes 4, etc. All vertices after an intersection are reassigned a value in the following way: newValue = oldValue - deletedVertices + 1 ( where "+ 1" is the newly added vertex X). $\endgroup$ – James T. Jul 25 '18 at 14:08
  • $\begingroup$ For figure B push point 4 below edge (8-9) so that edge (8-9) was intersected by (3-4) and (4-5) and you will see described algorithm won't work as expected. $\endgroup$ – Anton Petrov Feb 6 at 12:35
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I feel like an idiot now. I had previously implemented the answer concerning using an algorithm to map the convex hull into my algorithm, but this may be the simplest and most effective solution to my question. $\endgroup$ – James T. Feb 8 at 11:51
  • $\begingroup$ I like this answer better than mine too. To minimize both $x$ and $y$ at the same point you would need the figure to have a point in the lower left corner of its own bounding box, which doesn't always happen. But you can pick one axis (either $x$ or $y$) and minimize that coordinate. If you find the minimum value of $x$ and there are multiple points there, then pick the one with minimum $y$ in that set of points. That should work. $\endgroup$ – David K Feb 8 at 23:11
1
$\begingroup$

You could find the convex hull of the polygon, then require the algorithm to start searching from a vertex that is on the convex hull. That would guarantee that you do not start the search at vertex $1$ in figure $A$.

$\endgroup$
  • $\begingroup$ The problem does not only appear if the search starts at vertex 1, but it appears if vertex 1 is among the vertices that the algorithm tries to remove. Your suggestion about the convex hull may still prove useful. I will see if I can find a vertex on the hull of the polygon, set it as the polygon's new first vertex and then reassign a new value for all other vertices. $\endgroup$ – James T. Jul 25 '18 at 14:48
  • $\begingroup$ Alright, this addition fixed the algorithm. I added a function for finding the convex hull of the polygon. I then checked all of the polygon's vertices against the vertices of the convex hull's vertices. Once a common vertex is found, the loop stops and the algorithm now reshuffles the polygon's vertices into a new clockwise order starting from the common vertex. This way, as David K suggested, vertex 1 cant be inside the removable area. $\endgroup$ – James T. Jul 25 '18 at 15:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.