1

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

  1. take the horinzontal x coordinate of my vertex as x1
  2. take each pair of sucessive vertices (x2, y2, x3, y3)
  3. test if they are on each side of the line (x2 < x1 and x1 < x3 or the opposite)
  4. if yes calculate the equation for the line between them
  5. use this equation to calculate y1

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)

Louri
  • 25
  • 6
  • Does [this](https://stackoverflow.com/questions/66066287/how-to-find-the-intersect-points-in-a-polygon-object) help? – kelsny Sep 29 '22 at 18:38
  • I don't think it helps. From my understanding, the answer you linked is using the same method than the one I am trying to replace, except they have two sets of finite lines instead of one set of finite lines and one set of infinite vertical lines defined by a point. Thank you anyway – Louri Sep 29 '22 at 19:05
  • 1
    On page 23 of the referenced `Triangulation.pdf`, the first step involves sorting the vertices of the polygon from left to right. Thus, a binary search can be used to find the polygon line segments that are crossed by the vertical line. A binary search is O( log n )... – Trentium Oct 02 '22 at 17:42

1 Answers1

0

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).

Berthur
  • 4,300
  • 2
  • 14
  • 28