I am working in javascript and trying to implement an algorithm that triangulates a polygon (something convex or concave but assumed to be a simple polygon, not self crossing and without holes).
I have found a solution on the web but it is only in pseudocode and I am trying to implement it. ( source of the algorithm : https://sites.cs.ucsb.edu/~suri/cs235/Triangulation.pdf page 19). The first step is to partition the polygon into trapezoids with a plane sweep algorithm, which is described as "At each vertex, extend vertical line until it hits a polygon edge. Each face of this decomposition is a trapezoid; which may degenerate into a triangle."
Considering that my polygon is set of coordinates, how do I know that my line is crossing the polygon ?
I was thinking that I could do something like
but it sounds like overkill since it has a O(n²) complexity and the pseudocode announces O(n*log(n)). And I can't stop when I have found a solution since my polygone might "double back" and there would be multiple points of crossing.
Is there another way to find the points where the line crosses the polygon? (Or a simple way to triangulate the polygon in the first place)
There might be easier ways to solve it, but this might be one approach:
Make use of the Bentley Ottman algorithm for finding intersections in a set of line segments. Since your polygon is not self-intersecting, you can just add your sweep segments and find its intersections in O((n + k) log n) time, where k is the number of intersections. As long as the total number of intersections is O(n) (which will be the case if your polygon is not too crazy shaped), the resulting time complexity should be O(n log n).