confusing polygon problem
Posted: Fri Dec 08, 2023 3:17 pm
I'm working with a generated polygon but the way it is generated means the vertices are jumbled, I need an algorithm to either : rearrange the vertices to make it non-overlapping, or an algorithm to make the polygon convex (even if it means removing vertices that fall inside of the polygon.
I have tried reprogramming the process of generating the polygon but I could not feasibly make it work but here are specifications to fix it if you would like to try it this way (which would probably be the more efficient method and my preferred one) :
vertices are generated from a line between a point and a shape's vertices, the direction from the point to the vertice is stored along with its position, after all of these have been stored the function loops through them and finds the intersection between the furthest positive screen border (ie the line hits the top of the screen at time 1.1 and the right side of the screen at time 2.3 it'll store the intersection of the right side), the order that the vertices are stored in means that if the table goes : [reverse order of vertices sorted from leftmost to rightmost] + [intersection of original order of vertices to screen border] then the polygon will be correct (almost never the case normally) but the problem is that finding the leftmost vertice is very difficult from my attempts
rules for leftmost vertice : the direction of the vertice is in radians, the whole of the shape can be in any direction (meaning the leftmost vertice isnt just the vertice with the lowest direction since it could be [5.5, 0.4, 1.3, 2.4] ordered from leftmost to rightmost), the shape being checked is always convex so there is always 2 vertices that are pi radians (180 degrees) or more from each other without any vertice between the 2 and the one of them is guaranteed to be the leftmost vertice.
I have tried reprogramming the process of generating the polygon but I could not feasibly make it work but here are specifications to fix it if you would like to try it this way (which would probably be the more efficient method and my preferred one) :
vertices are generated from a line between a point and a shape's vertices, the direction from the point to the vertice is stored along with its position, after all of these have been stored the function loops through them and finds the intersection between the furthest positive screen border (ie the line hits the top of the screen at time 1.1 and the right side of the screen at time 2.3 it'll store the intersection of the right side), the order that the vertices are stored in means that if the table goes : [reverse order of vertices sorted from leftmost to rightmost] + [intersection of original order of vertices to screen border] then the polygon will be correct (almost never the case normally) but the problem is that finding the leftmost vertice is very difficult from my attempts
rules for leftmost vertice : the direction of the vertice is in radians, the whole of the shape can be in any direction (meaning the leftmost vertice isnt just the vertice with the lowest direction since it could be [5.5, 0.4, 1.3, 2.4] ordered from leftmost to rightmost), the shape being checked is always convex so there is always 2 vertices that are pi radians (180 degrees) or more from each other without any vertice between the 2 and the one of them is guaranteed to be the leftmost vertice.