Geometría Computacional: Triangulación: Polígonos Y-Monótonos
Polígonos Y-Monótonos
Eje y
Cadena
izquierda
End Vertex
Start Vertex
Cualquier línea perpendicular a el eje Y intersecta al polígono solo dos veces.
Las cadenas nunca van hacia arriba cuando pasan por los vértices regulares empezando por el inicio y terminando en el fin.
En general un polígono monónoto se define con respecto a una línea.
Geometría Computacional
Cadena
derecha
Regular Vertex
Triangulanción de un Polígono Y-MonótonoGeometría Computacional
Usar la técnica de algoritmo Greddy (glotón) recorriendo los vértices en orden descendente por el eje Y.
Si desde el vértice actual no se puede trazar una diagonal, se adiciona a una pila S.
Para verificar si se puede trazar una diagonal se chequea con los dos vértices en el tope de la pila S.
Cuando se pueda trazar una diagonal se trazan todas aquellas que sean posibles sacando vértices de la pila S.
En la pila S siempre deben quedar al menos dos vértices para chequear con el próximo vértice.
Geometría Computacional
Próximo en la cadena contraria
t
s
r
q
uj
q
r
s
t
uj-1
S
uj-1
Geometría Computacional
Próximo en la cadena contraria
t
s
r
q
uj
uj-1
Pop
q
r
s
t
uj-1
S
Geometría Computacional
Próximo en la cadena contraria
t
s
r
q
uj
uj-1
Pop
q
r
s
t
S
t
Geometría Computacional
Próximo en la cadena contraria
t
s
r
q
uj
uj-1
Pop
q
r
s
S
Geometría Computacional
Próximo en la cadena contraria
t
s
r
q
uj
uj-1
Pop
q
r
s
S
Geometría Computacional
Próximo en la cadena contraria
t
s
r
q
uj
uj-1
Pop
q
r
s
S
Geometría Computacional
Próximo en la cadena contraria
t
s
r
q
uj
uj-1
Pop
q
r
S
Geometría Computacional
Próximo en la cadena contraria
t
s
r
q
uj
uj-1
Pop
q
r
S
Geometría Computacional
Próximo en la cadena contraria
t
s
r
q
uj
uj-1
Pop
q
S
Geometría Computacional
Próximo en la cadena contraria
t
s
r
q
uj
uj-1
Pop
q
S
Geometría Computacional
Próximo en la cadena contraria
t
s
r
q
uj
uj-1
Pop
S
Geometría Computacional
Próximo en la cadena contraria
t
s
r
q
uj
uj-1
Pop
S
Push
Geometría Computacional
Próximo en la cadena contraria
t
s
r
q
uj
uj-1
Pop
Push
uj-1
S
Geometría Computacional
Próximo en la cadena contraria
t
s
r
q
uj
uj-1
Pop
Push
uj-1
S
Geometría Computacional
Próximo en la cadena contraria
t
s
r
q
uj
uj-1
Pop
Push
uj-1
S
uj
Geometría Computacional
Cambio de giro en la misma cadena
uj-1
t
s
r
q
uj
q
r
s
t
uj-1
S
Geometría Computacional
Cambio de giro en la misma cadena
uj-1
t
s
r
q
uj
q
r
s
t
uj-1
S
Pop
Geometría Computacional
Cambio de giro en la misma cadena
uj-1
t
s
r
q
uj
q
r
s
t
S
Pop
Geometría Computacional
Cambio de giro en la misma cadena
uj-1
t
s
r
q
uj
q
r
s
t
S
Pop
Geometría Computacional
Cambio de giro en la misma cadena
uj-1
t
s
r
q
uj
q
r
s
S
Pop
Geometría Computacional
Cambio de giro en la misma cadena
uj-1
t
s
r
q
uj
q
r
s
S
Pop
Geometría Computacional
Cambio de giro en la misma cadena
uj-1
t
s
r
q
uj
q
r
s
S
Pop
Geometría Computacional
Cambio de giro en la misma cadena
uj-1
t
s
r
q
uj
q
r
S
Pop
Geometría Computacional
Cambio de giro en la misma cadena
uj-1
t
s
r
q
uj
q
r
S
Pop
Geometría Computacional
Cambio de giro en la misma cadena
uj-1
t
s
r
q
uj
q
S
Pop
Geometría Computacional
Cambio de giro en la misma cadena
uj-1
t
s
r
q
uj
q
S
Pop
Geometría Computacional
Cambio de giro en la misma cadena
uj-1
t
s
r
q
uj
q
S
Pop
Push
Geometría Computacional
Cambio de giro en la misma cadena
uj-1
t
s
r
q
uj
q
S
Pop
Push
r
Geometría Computacional
Cambio de giro en la misma cadena
uj-1
t
s
r
q
uj
q
S
Pop
Push
r
Geometría Computacional
Cambio de giro en la misma cadena
uj-1
t
s
r
q
uj
q
S
Pop
Push
r
uj
TriangulateMonotonePolygon(P)
Input: A y-monotone polygon P sotored in a DCEL D.
Output: A triangulation of P stored in D.
1. Merge all vertices of P into one sequence sorted on decreasing
y coordinate.
2. Initialize an empty stack S and push u1 and u2 onto it.
3. for j ← 3 to n – 1
4. if uj and Top(S) are on different chains
5. then v = Pop(S)
6. while !IsEmpty(S)
7. insert into D a diagonal from uj to v
8. v = Pop(S)
9. Push(S, uj-1)
10. else v = Pop(S)
11. while !IsEmpty(S) and Top(S) is visible from uj12. v = Pop(S)
13. insert into D a diagonal from uj to v
14. Push(S, v)
15. Push(S, uj)
16. Add diagonals from un to all stack vertices except the first
and the last one.
Geometría Computacional
Polígonos Y-Monótonos
Geometría Computacional
u1
u2
u2
u3
u3
u4
u3
u5u6
u7
u8
u9
u5
u10
u11
u7
u11
u12
S
Polígonos Y-Monótonos
Geometría Computacional
u1
u2
S
Polígonos Y-Monótonos
Geometría Computacional
u1
u2
S
u3
Polígonos Y-Monótonos
Geometría Computacional
u1
u2
S
u3
Polígonos Y-Monótonos
Geometría Computacional
u1
S
u3
Polígonos Y-Monótonos
Geometría Computacional
u1
S
u3
Polígonos Y-Monótonos
Geometría Computacional
S
u3 u2
Push
Polígonos Y-Monótonos
Geometría Computacional
S
u3
u2
Push
Polígonos Y-Monótonos
Geometría Computacional
u4
S
u3
u2
Polígonos Y-Monótonos
Geometría Computacional
u4
S
u3
u2
Polígonos Y-Monótonos
Geometría Computacional
u4
S
u2
Polígonos Y-Monótonos
Geometría Computacional
u4
S
u2
Polígonos Y-Monótonos
Geometría Computacional
u4
S
Polígonos Y-Monótonos
Geometría Computacional
u4
S
u3
Push
Polígonos Y-Monótonos
Geometría Computacional
u4
S
u3
Push
Polígonos Y-Monótonos
Geometría Computacional
u4
S
u3u5
Polígonos Y-Monótonos
Geometría Computacional
S
u3u5
Polígonos Y-Monótonos
Geometría Computacional
S
u5
Polígonos Y-Monótonos
Geometría Computacional
S
u5 u3
Push
Polígonos Y-Monótonos
Geometría Computacional
S
u5
u3
Push
Polígonos Y-Monótonos
Geometría Computacional
S
u5
u3u6
Polígonos Y-Monótonos
Geometría Computacional
S
u5
u3u6
Polígonos Y-Monótonos
Geometría Computacional
S
u3u6
Polígonos Y-Monótonos
Geometría Computacional
S
u6
Polígonos Y-Monótonos
Geometría Computacional
S
u5
Push
u6
Polígonos Y-Monótonos
Geometría Computacional
S
u5
Push
u6
Polígonos Y-Monótonos
Geometría Computacional
S
u5
u6
u7
Polígonos Y-Monótonos
Geometría Computacional
S
u5
u6
u7
Push
Polígonos Y-Monótonos
Geometría Computacional
S
u5
u6
u7
u8
Polígonos Y-Monótonos
Geometría Computacional
S
u5
u6
u7
u8
Push
Polígonos Y-Monótonos
Geometría Computacional
S
u5
u6
u7
u8
u9
Polígonos Y-Monótonos
Geometría Computacional
S
u5
u6
u7
u8
u9
Push
Polígonos Y-Monótonos
Geometría Computacional
S
u5
u6
u7
u8
u9
u10
Polígonos Y-Monótonos
Geometría Computacional
S
u5
u6
u7
u8
u9
u10
Polígonos Y-Monótonos
Geometría Computacional
S
u5
u6
u7
u8
u10
Polígonos Y-Monótonos
Geometría Computacional
S
u5
u6
u7
u10
Polígonos Y-Monótonos
Geometría Computacional
S
u5
u6
u7
u10
Polígonos Y-Monótonos
Geometría Computacional
S
u5
u6
u10
Polígonos Y-Monótonos
Geometría Computacional
S
u5
u6
u10
Push
u7
Polígonos Y-Monótonos
Geometría Computacional
S
u5
u6
u10
Push
u7
Polígonos Y-Monótonos
Geometría Computacional
S
u5
u6
u10
u7
u11
Polígonos Y-Monótonos
Geometría Computacional
S
u5
u6
u10
u7
u11
Push
Polígonos Y-Monótonos
Geometría Computacional
S
u5
u6
u10
u7
u11
u12
Polígonos Y-Monótonos
Geometría Computacional
S
u5
u6
u10
u7
u11
u12
Polígonos Y-Monótonos
Geometría Computacional
S
u5
u6
u10
u7
u12
Polígonos Y-Monótonos
Geometría Computacional
S
u5
u6
u7
u12
Polígonos Y-Monótonos
Geometría Computacional
S
u5
u6
u7
u12
Polígonos Y-Monótonos
Geometría Computacional
S
u5
u6
u12
Polígonos Y-Monótonos
Geometría Computacional
S
u5u12
Polígonos Y-Monótonos
Geometría Computacional
S
u5u12
Polígonos Y-Monótonos
Geometría Computacional
S
u12
Polígonos Y-Monótonos
Geometría Computacional
S
u12
S
u11
Push
Polígonos Y-Monótonos
Geometría Computacional
S
u12
S
u11
Push
Triangulación de un Polígono Y-Monótono
Como se parte del polígono representado en una DCEL, mezclar los vértices de forma ordenada toma un tiempo O(n).
Realizando un análisis amortizado de las operaciones se obtiene que el tiempo total del algoritmo es O(n).
Geometría Computacional