Page 1 of 1

confusing polygon problem

Posted: Fri Dec 08, 2023 3:17 pm
by milo_goat
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.

Re: confusing polygon problem

Posted: Sat Dec 09, 2023 1:06 pm
by dusoft
Do you need to clip (simplify) polygons?

If so, check these:
https://github.com/spoonless/luapoly
https://github.com/Ark223/ClipperLua

Or triangulation:
https://github.com/Yonaba/delaunay

Re: confusing polygon problem

Posted: Sat Dec 09, 2023 1:11 pm
by dusoft
Also I have found this old thread that provides good explanations:
viewtopic.php?t=93913