Estoy trabajando en javascript y tratando de implementar un algoritmo que triangula un polígono (algo convexo o cóncavo pero que se supone que es un polígono simple, no autocruzado y sin agujeros).

He encontrado una solución en la web, pero solo está en pseudocódigo y estoy tratando de implementarla. (Fuente del algoritmo: https://sites.cs.ucsb.edu/~suri/cs235/Triangulation.pdf página 19). El primer paso es dividir el polígono en trapecios con un algoritmo de barrido plano , que se describe como "En cada vértice, extienda la línea vertical hasta que toque el borde de un polígono. Cada cara de esta descomposición es un trapezoide, que puede degenerar en un triángulo".

Teniendo en cuenta que mi polígono es un conjunto de coordenadas, ¿cómo sé que mi línea cruza el polígono?

Estaba pensando que podría hacer algo como

1. toma la coordenada x horinzontal de mi vértice como x1
2. tomar cada par de vértices sucesivos (x2, y2, x3, y3)
3. prueba si están en cada lado de la línea (x2 < x1 y x1 < x3 o al contrario)
4. en caso afirmativo, calcule la ecuación para la línea entre ellos
5. usa esta ecuación para calcular y1

pero suena exagerado ya que tiene una complejidad O(n²) y el pseudocódigo anuncia O(n*log(n)). Y no puedo detenerme cuando encontré una solución, ya que mi polígono podría "doblarse" y habría múltiples puntos de cruce.

¿Hay otra forma de encontrar los puntos donde la línea cruza el polígono? (O una forma simple de triangular el polígono en primer lugar)