Mixing
How to remove self intersection in concave polygons?
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
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?
algorithms polygons
edited Jul 25 at 12:37
David K
48.1k340107
asked Jul 25 at 11:33
James T.
32
add a comment |Â
up vote
0
down vote
favorite
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?
algorithms polygons
edited Jul 25 at 12:37
David K
48.1k340107
asked Jul 25 at 11:33
James T.
32
"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?
– David K
Jul 25 at 12:31
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).
– James T.
Jul 25 at 14:08
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
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?
algorithms polygons
edited Jul 25 at 12:37
David K
48.1k340107
asked Jul 25 at 11:33
James T.
32
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?
algorithms polygons
edited Jul 25 at 12:37
David K
48.1k340107
asked Jul 25 at 11:33
James T.
32
edited Jul 25 at 12:37
David K
48.1k340107
edited Jul 25 at 12:37
David K
48.1k340107
edited Jul 25 at 12:37
David K
48.1k340107
48.1k340107
asked Jul 25 at 11:33
James T.
32
asked Jul 25 at 11:33
James T.
32
asked Jul 25 at 11:33
James T.
32
32
"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?
– David K
Jul 25 at 12:31
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).
– James T.
Jul 25 at 14:08
add a comment |Â
"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?
– David K
Jul 25 at 12:31
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).
– James T.
Jul 25 at 14:08
"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?
– David K
Jul 25 at 12:31
"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?
– David K
Jul 25 at 12:31
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).
– James T.
Jul 25 at 14:08
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).
– James T.
Jul 25 at 14:08
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
0
down vote
accepted
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$.
answered Jul 25 at 12:35
David K
48.1k340107
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.
– James T.
Jul 25 at 14:48
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.
– James T.
Jul 25 at 15:22
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
accepted
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$.
answered Jul 25 at 12:35
David K
48.1k340107
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.
– James T.
Jul 25 at 14:48
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.
– James T.
Jul 25 at 15:22
add a comment |Â
up vote
0
down vote
accepted
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$.
answered Jul 25 at 12:35
David K
48.1k340107
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.
– James T.
Jul 25 at 14:48
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.
– James T.
Jul 25 at 15:22
add a comment |Â
up vote
0
down vote
accepted
up vote
0
down vote
accepted
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$.
answered Jul 25 at 12:35
David K
48.1k340107
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$.
answered Jul 25 at 12:35
David K
48.1k340107
answered Jul 25 at 12:35
David K
48.1k340107
answered Jul 25 at 12:35
David K
48.1k340107
answered Jul 25 at 12:35
David K
48.1k340107
48.1k340107
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.
– James T.
Jul 25 at 14:48
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.
– James T.
Jul 25 at 15:22
add a comment |Â
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.
– James T.
Jul 25 at 14:48
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.
– James T.
Jul 25 at 15:22
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.
– James T.
Jul 25 at 14:48
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.
– James T.
Jul 25 at 14:48
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.
– James T.
Jul 25 at 15:22
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.
– James T.
Jul 25 at 15:22
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2862339%2fhow-to-remove-self-intersection-in-concave-polygons%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
"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?
– David K
Jul 25 at 12:31
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).
– James T.
Jul 25 at 14:08