![Page 1: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/1.jpg)
Vera Sacristan
Geometria Computacional
Facultat d’Informatica de Barcelona
Universitat Politecnica de Catalunya
INTERSECCIO DE SEGMENTS
![Page 2: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/2.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
![Page 3: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/3.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Problema
Entrada: n segments del pla, si = (pi, qi), i = 1 . . . n.Sortida: Les k = O(n2) interseccions de parells de segments, (x, y, i, j).
![Page 4: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/4.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Problema
Entrada: n segments del pla, si = (pi, qi), i = 1 . . . n.Sortida: Les k = O(n2) interseccions de parells de segments, (x, y, i, j).
Algunes aplicacions (a mes de les que ja coneixeu)
Sistemes d’informacio geograficaDetectar les interseccions entre els elements de les capes d’informacio (ciutats, carreteres,serveis,...)
Visualitzacio realistaEliminar les parts ocultes d’una escena
![Page 5: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/5.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Problema
Entrada: n segments del pla, si = (pi, qi), i = 1 . . . n.Sortida: Les k = O(n2) interseccions de parells de segments, (x, y, i, j).
Solucio per forca bruta
Comprovar la interseccio dels(n2
)parells de segments. Aquest algorisme te cost Θ(n2).
![Page 6: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/6.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Problema
Entrada: n segments del pla, si = (pi, qi), i = 1 . . . n.Sortida: Les k = O(n2) interseccions de parells de segments, (x, y, i, j).
Solucio per forca bruta
Comprovar la interseccio dels(n2
)parells de segments. Aquest algorisme te cost Θ(n2).
Complexitat del problema
El problema te complexitat Ω(n2), perque hi ha configu-racions de segments que tenen aquest nombre de talls.
![Page 7: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/7.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Problema
Entrada: n segments del pla, si = (pi, qi), i = 1 . . . n.Sortida: Les k = O(n2) interseccions de parells de segments, (x, y, i, j).
Solucio per forca bruta
Comprovar la interseccio dels(n2
)parells de segments. Aquest algorisme te cost Θ(n2).
Complexitat del problema
El problema te complexitat Ω(n2), perque hi ha configu-racions de segments que tenen aquest nombre de talls.
![Page 8: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/8.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Problema
Entrada: n segments del pla, si = (pi, qi), i = 1 . . . n.Sortida: Les k = O(n2) interseccions de parells de segments, (x, y, i, j).
Solucio per forca bruta
Comprovar la interseccio dels(n2
)parells de segments. Aquest algorisme te cost Θ(n2).
Complexitat del problema
El problema te complexitat Ω(n2), perque hi ha configu-racions de segments que tenen aquest nombre de talls.
Ara be, existeixen conjunts de n segments amb un nom-bre d’interseccions substancialment inferior a
(n2
).
![Page 9: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/9.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Problema
Entrada: n segments del pla, si = (pi, qi), i = 1 . . . n.Sortida: Les k = O(n2) interseccions de parells de segments, (x, y, i, j).
Solucio per forca bruta
Comprovar la interseccio dels(n2
)parells de segments. Aquest algorisme te cost Θ(n2).
Complexitat del problema
El problema te complexitat Ω(n2), perque hi ha configu-racions de segments que tenen aquest nombre de talls.
Ara be, existeixen conjunts de n segments amb un nom-bre d’interseccions substancialment inferior a
(n2
).
Solucio output-sensitive
Algorisme el cost del qual depen del nombre d’intersec-cions a reportar.
![Page 10: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/10.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Problema
Entrada: n segments del pla, si = (pi, qi), i = 1 . . . n.Sortida: Les k = O(n2) interseccions de parells de segments, (x, y, i, j).
![Page 11: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/11.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Problema
Entrada: n segments del pla, si = (pi, qi), i = 1 . . . n.Sortida: Les k = O(n2) interseccions de parells de segments, (x, y, i, j).
Observacio 1
Si dos segments tenen projeccions disjuntes sobre una recta donada, aleshores son disjunts.
![Page 12: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/12.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Problema
Entrada: n segments del pla, si = (pi, qi), i = 1 . . . n.Sortida: Les k = O(n2) interseccions de parells de segments, (x, y, i, j).
Observacio 1
Si dos segments tenen projeccions disjuntes sobre una recta donada, aleshores son disjunts.
![Page 13: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/13.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Problema
Entrada: n segments del pla, si = (pi, qi), i = 1 . . . n.Sortida: Les k = O(n2) interseccions de parells de segments, (x, y, i, j).
Observacio 1
Si dos segments tenen projeccions disjuntes sobre una recta donada, aleshores son disjunts.
Observacio 2
En escombrar el conjunt de segments amb una recta, dos segments que es tallen han deser consecutius a la recta d’escombrat just abans de tallar-se.
![Page 14: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/14.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Problema
Entrada: n segments del pla, si = (pi, qi), i = 1 . . . n.Sortida: Les k = O(n2) interseccions de parells de segments, (x, y, i, j).
Observacio 1
Si dos segments tenen projeccions disjuntes sobre una recta donada, aleshores son disjunts.
Observacio 2
En escombrar el conjunt de segments amb una recta, dos segments que es tallen han deser consecutius a la recta d’escombrat just abans de tallar-se.
![Page 15: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/15.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Problema
Entrada: n segments del pla, si = (pi, qi), i = 1 . . . n.Sortida: Les k = O(n2) interseccions de parells de segments, (x, y, i, j).
Observacio 1
Si dos segments tenen projeccions disjuntes sobre una recta donada, aleshores son disjunts.
Observacio 2
En escombrar el conjunt de segments amb una recta, dos segments que es tallen han deser consecutius a la recta d’escombrat just abans de tallar-se.
![Page 16: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/16.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Problema
Entrada: n segments del pla, si = (pi, qi), i = 1 . . . n.Sortida: Les k = O(n2) interseccions de parells de segments, (x, y, i, j).
Observacio 1
Si dos segments tenen projeccions disjuntes sobre una recta donada, aleshores son disjunts.
Observacio 2
En escombrar el conjunt de segments amb una recta, dos segments que es tallen han deser consecutius a la recta d’escombrat just abans de tallar-se.
![Page 17: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/17.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Problema
Entrada: n segments del pla, si = (pi, qi), i = 1 . . . n.Sortida: Les k = O(n2) interseccions de parells de segments, (x, y, i, j).
Observacio 1
Si dos segments tenen projeccions disjuntes sobre una recta donada, aleshores son disjunts.
Observacio 2
En escombrar el conjunt de segments amb una recta, dos segments que es tallen han deser consecutius a la recta d’escombrat just abans de tallar-se.
![Page 18: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/18.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Algorisme de Bentley-Ottman
Es tracta d’un algorisme d’escombrat.
![Page 19: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/19.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Algorisme de Bentley-Ottman
Es tracta d’un algorisme d’escombrat.
Hipotesis (que despres eliminarem)
1. No hi ha abscisses repetides, es a dir: no hi ha segments verticals, i dos extremsdels segments, dos punts de tall entre segments o un extrem i un punt de tall maino coincideixen sobre una mateixa vertical.
2. En cada punt d’interseccio, sols es tallen dos segments.
![Page 20: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/20.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Algorisme de Bentley-Ottman
Es tracta d’un algorisme d’escombrat.
Hipotesis (que despres eliminarem)
1. No hi ha abscisses repetides, es a dir: no hi ha segments verticals, i dos extremsdels segments, dos punts de tall entre segments o un extrem i un punt de tall maino coincideixen sobre una mateixa vertical.
2. En cada punt d’interseccio, sols es tallen dos segments.
Esdeveniments
• Tots els extrems dels segments (coneguts a priori)
• Tots els punts d’interseccion entre segments (que es van descobrint a mida queavanca l’escombrat)
![Page 21: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/21.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Algorisme de Bentley-Ottman
Es tracta d’un algorisme d’escombrat.
Hipotesis (que despres eliminarem)
1. No hi ha abscisses repetides, es a dir: no hi ha segments verticals, i dos extremsdels segments, dos punts de tall entre segments o un extrem i un punt de tall maino coincideixen sobre una mateixa vertical.
2. En cada punt d’interseccio, sols es tallen dos segments.
Esdeveniments
• Tots els extrems dels segments (coneguts a priori)
• Tots els punts d’interseccion entre segments (que es van descobrint a mida queavanca l’escombrat)
Recta d’escombrat
Relacio dels segments interceptats, en ordre vertical, de dalt a baix.
![Page 22: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/22.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Algorisme de Bentley-Ottman
![Page 23: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/23.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Algorisme de Bentley-Ottman
Entrada: n segments del pla, si = (pi, qi), i = 1 . . . n.Sortida: Les k = O(n2) interseccions de parells de segments, (x, y, i, j).
![Page 24: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/24.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Algorisme de Bentley-Ottman
Inicialitzacio:- Ordenar els 2n extrems per abscissa i guardar la informacio a E.- La recta R comenca buida.
Entrada: n segments del pla, si = (pi, qi), i = 1 . . . n.Sortida: Les k = O(n2) interseccions de parells de segments, (x, y, i, j).
![Page 25: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/25.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
AvencMentre E 6= ∅ fer:
1. p = minE
2. Si p = inici(s), aleshores:
• Insertar s a R
• Si s− i s es tallen a la dreta de p, insertar el punt de tall a E i reportar-lo (si cal).Idem per a s+
3. Si p = final(s), aleshores:
• Si s− i s+ es tallen a la dreta de p, insertar el punt de tall a E i reportar-lo (si cal).
• Esborrar s de R
4. Si p = s1 ∩ s2 amb s1 <R s2, aleshores:
• Si s−1 i s2 es tallen a la dreta de p, insertar el punt de tall a E i reportar-lo (si cal).Idem per a s+
2 i s1.
• Intercanviar l’ordre de s1 i s2 a R
5. Esborrar p de E
![Page 26: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/26.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
1
2
4
5
3
6
![Page 27: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/27.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
1
2
4
5
3
6
![Page 28: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/28.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
p1 p4 p2 p5 q4p3 q3 q2 p6 q6 q5 q1
1
2
4
5
3
6
![Page 29: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/29.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
p1 p4 p2 p5 q4p3 q3 q2 p6 q6 q5 q1
1
2
4
5
3
6
![Page 30: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/30.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
p1 p4 p2 p5 q4p3 q3 q2 p6 q6 q5 q1
1
2
4
5
3
6
![Page 31: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/31.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
p1 p4 p2 p5 q4p3 q3 q2 p6 q6 q5 q1
s1 1
2
4
5
3
6
![Page 32: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/32.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
p4 p2 p5 q4p3 q3 q2 p6 q6 q5 q1
s1 1
2
4
5
3
6
![Page 33: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/33.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
p4 p2 p5 q4p3 q3 q2 p6 q6 q5 q1
s1
s4
1
2
4
5
3
6
![Page 34: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/34.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
p4 p2 p5 q4p3 q3 q2 p6 q6 q5 q1
s1
s4
1
2
4
5
3
6
![Page 35: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/35.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
p4 p2 p5 q4p3 q3 q2 p6 q6 q5 q1
s1
s4
1
2
4
5
3
6
![Page 36: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/36.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
p2 p5 q4p3 q3 q2 p6 q6 q5 q1
s1
s4
1
2
4
5
3
6
![Page 37: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/37.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
p2 p5 q4p3 q3 q2 p6 q6 q5 q1
s1
s4
1
2
4
5
3
6
s2
![Page 38: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/38.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
p2 p5 q4p3 q3 q2 p6 q6 q5 q1
s1
s4
1
2
4
5
3
6
s2
![Page 39: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/39.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
p2 p5 q4p3 q3 q2 p6 q6 q5 q1
s1
s4
1
2
4
5
3
6
s2
r12
r12
![Page 40: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/40.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
p2 p5 q4p3 q3 q2 p6 q6 q5 q1
s1
s4
1
2
4
5
3
6
s2
r12
r12
![Page 41: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/41.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
p2 p5 q4p3 q3 q2 p6 q6 q5 q1
s1
s4
1
2
4
5
3
6
s2
r12
r12
![Page 42: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/42.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
p5 q4p3 q3 q2 p6 q6 q5 q1
s1
s4
1
2
4
5
3
6
s2
r12
r12
![Page 43: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/43.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
p5 q4p3 q3 q2 p6 q6 q5 q1
s1
s4
1
2
4
5
3
6
s2
r12
s3
r12
![Page 44: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/44.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
p5 q4p3 q3 q2 p6 q6 q5 q1
s1
s4
1
2
4
5
3
6
s2
r12
s3
r12
![Page 45: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/45.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
p5 q4p3 q3 q2 p6 q6 q5 q1
s1
s4
1
2
4
5
3
6
s2
r12
s3
r12
r13
r13
![Page 46: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/46.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
p5 q4p3 q3 q2 p6 q6 q5 q1
s1
s4
1
2
4
5
3
6
s2
r12
s3
r12
r13
r13
![Page 47: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/47.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
p5 q4p3 q3 q2 p6 q6 q5 q1
s1
s4
1
2
4
5
3
6
s2
r12
s3
r23
r12r23
r13
r13
![Page 48: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/48.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
p5 q4p3 q3 q2 p6 q6 q5 q1
s1
s4
1
2
4
5
3
6
s2
r12
s3
r23
r12r23
r13
r13
![Page 49: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/49.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
p5 q4 q3 q2 p6 q6 q5 q1
s1
s4
1
2
4
5
3
6
s2
r12
s3
r23
r12r23
r13
r13
![Page 50: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/50.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
p5 q4 q3 q2 p6 q6 q5 q1
s1
s4
1
2
4
5
3
6
s2
r12
s3
r23
s5
r12r23
r13
r13
![Page 51: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/51.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
p5 q4 q3 q2 p6 q6 q5 q1
s1
s4
1
2
4
5
3
6
s2
r12
s3
r23
s5
r12r23
r13
r13
![Page 52: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/52.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
p5 q4 q3 q2 p6 q6 q5 q1
s1
s4
1
2
4
5
3
6
s2
r12
s3
r23
s5
r12r23
r13
r13
![Page 53: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/53.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
q4 q3 q2 p6 q6 q5 q1
s1
s4
1
2
4
5
3
6
s2
r12
s3
r23
s5
r12r23
r13
r13
![Page 54: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/54.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
q4 q3 q2 p6 q6 q5 q1
s1
s4
1
2
4
5
3
6
s2
r12
s3
r23
s5
r12r23
r13
r13
![Page 55: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/55.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
q4 q3 q2 p6 q6 q5 q1
s1 1
2
4
5
3
6
s2
r12
s3
r23
s5
r12r23
r13
r13
![Page 56: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/56.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
q4 q3 q2 p6 q6 q5 q1
s1 1
2
4
5
3
6
s2
r12
s3
r23
s5
r12r23
r13
r13
![Page 57: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/57.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
q3 q2 p6 q6 q5 q1
s1 1
2
4
5
3
6
s2
r12
s3
r23
s5
r12r23
r13
r13
![Page 58: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/58.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
q3 q2 p6 q6 q5 q1
s1 1
2
4
5
3
6
r12r23
s2
s3
s5
r12r23
r13
r13
![Page 59: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/59.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
q3 q2 p6 q6 q5 q1
s1 1
2
4
5
3
6
r12r23
s2
s3
s5
r12r23
r13
r13
![Page 60: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/60.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
q3 q2 p6 q6 q5 q1
s1 1
2
4
5
3
6
r12r23
s2
s3
s5
r12r23
r13
r13
![Page 61: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/61.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
q3 q2 p6 q6 q5 q1
s1 1
2
4
5
3
6
r12r23
s2
s3
s5
r12r23
r13
r13
![Page 62: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/62.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
q3 q2 p6 q6 q5 q1
s1 1
2
4
5
3
6
r12r23
s2
s3
s5
r12r23
r13
r13
![Page 63: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/63.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
q3 q2 p6 q6 q5 q1
s1 1
2
4
5
3
6
r12
s2
s3
s5
r12r23
r13
r13
![Page 64: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/64.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
q3 q2 p6 q6 q5 q1
1
2
4
5
3
6
r12
s5
s2
s1
s3
r12r23
r13
r13
![Page 65: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/65.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
q3 q2 p6 q6 q5 q1
1
2
4
5
3
6
r12
s5
s2
s1
s3
r12r23
r13
r13
![Page 66: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/66.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
q3 q2 p6 q6 q5 q1
1
2
4
5
3
6
r12
s5
s2
s1
s3
r12r23
r13
r13
![Page 67: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/67.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
q3 q2 p6 q6 q5 q1
1
2
4
5
3
6
r12
s5
s2
s1
s3
r12r23
r13
r13
![Page 68: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/68.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
q3 q2 p6 q6 q5 q1
1
2
4
5
3
6
s5
s2
s1
s3
r12r23
r13
r13
![Page 69: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/69.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
q3 q2 p6 q6 q5 q1
1
2
4
5
3
6
s5
r12r23
r13
r13
s2
s3
s1
![Page 70: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/70.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
q3 q2 p6 q6 q5 q1
1
2
4
5
3
6
s5
r12r23
r13
r13
s2
s3
s1
![Page 71: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/71.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
q3 q2 p6 q6 q5 q1
1
2
4
5
3
6
s5
r12r23
r13
r13
s2
s3
s1
![Page 72: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/72.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
q3 q2 p6 q6 q5 q1
1
2
4
5
3
6
s5
r15
r12r23 r15
r13
r13
s2
s3
s1
![Page 73: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/73.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
q3 q2 p6 q6 q5 q1
1
2
4
5
3
6
s5
r15
r12r23 r15
r13
r13
s2
s3
s1
![Page 74: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/74.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
q3 q2 p6 q6 q5 q1
1
2
4
5
3
6
s5
r15
r12r23 r15r13
s2
s3
s1
![Page 75: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/75.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
q3 q2 p6 q6 q5 q1
1
2
4
5
3
6
s5
r12r23 r15r13
s2
s3
s1
![Page 76: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/76.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
q3 q2 p6 q6 q5 q1
1
2
4
5
3
6
s5
r12r23 r15r13
s2
s1
![Page 77: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/77.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
q3 q2 p6 q6 q5 q1
1
2
4
5
3
6
s5
r12r23 r15r13
s2
s1
![Page 78: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/78.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
q3 q2 p6 q6 q5 q1
1
2
4
5
3
6
s5
r12r23 r15r13
s2
s1
![Page 79: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/79.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
q2 p6 q6 q5 q1
1
2
4
5
3
6
s5
r15
r12r23 r15r13
s2
s1
![Page 80: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/80.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
q2 p6 q6 q5 q1
1
2
4
5
3
6
s5
r15
r12r23 r15r13
s2
s1
![Page 81: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/81.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
q2 p6 q6 q5 q1
1
2
4
5
3
6
s5
r15
r12r23 r15r13
s1
![Page 82: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/82.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
p6 q6 q5 q1
1
2
4
5
3
6
s5
r15
r12r23 r15r13
s1
![Page 83: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/83.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
p6 q6 q5 q1
1
2
4
5
3
6
s5
r15
s6
r12r23 r15r13
s1
![Page 84: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/84.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
p6 q6 q5 q1
1
2
4
5
3
6
s5
r15
s6
r12r23 r15r13
s1
![Page 85: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/85.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
p6 q6 q5 q1
1
2
4
5
3
6
s5
r15
s6
r12r23 r15r13
s1
![Page 86: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/86.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
p6 q6 q5 q1
1
2
4
5
3
6
s5
r15
s6
r56
r12r23 r15r56r13
s1
![Page 87: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/87.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
p6 q6 q5 q1
1
2
4
5
3
6
s5
r15
s6
r56
r12r23 r15r56r13
s1
![Page 88: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/88.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
q6 q5 q1
1
2
4
5
3
6
s5
r15
s6
r56
r12r23 r15r56r13
s1
![Page 89: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/89.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
q6 q5 q1
1
2
4
5
3
6
r15r56
s6
s1
s5
r12r23 r15r56r13
![Page 90: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/90.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
q6 q5 q1
1
2
4
5
3
6
r15r56
s6
s1
s5
r12r23 r15r56r13
![Page 91: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/91.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
q6 q5 q1
1
2
4
5
3
6
r15r56
s6
s1
s5
r12r23 r15r56r13
![Page 92: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/92.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
q6 q5 q1
1
2
4
5
3
6
r15r56
s6
s1
s5
r12r23 r15r56r13
![Page 93: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/93.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
q6 q5 q1
1
2
4
5
3
6
r15
s6
s1
s5
r12r23 r15r56r13
![Page 94: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/94.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
q6 q5 q1
1
2
4
5
3
6
r15
s6
s1
s5
r12r23 r15r56r13
![Page 95: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/95.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
q6 q5 q1
1
2
4
5
3
6
r15
r12r23 r15r56r13
s1
s5
![Page 96: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/96.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
q5 q1
1
2
4
5
3
6
r15
r12r23 r15r56r13
s1
s5
![Page 97: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/97.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
q5 q1
1
2
4
5
3
6
r15
r12r23 r15r56r13
s5
s1
![Page 98: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/98.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
q5 q1
1
2
4
5
3
6
r15
r12r23 r15r56r13
s5
s1
![Page 99: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/99.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
q5 q1
1
2
4
5
3
6
r12r23 r15r56r13
s5
s1
![Page 100: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/100.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
q5 q1
1
2
4
5
3
6
r12r23 r15r56r13
s5
s1
![Page 101: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/101.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
q5 q1
1
2
4
5
3
6
r12r23 r15r56r13
s1
![Page 102: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/102.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
q1
1
2
4
5
3
6
r12r23 r15r56r13
s1
![Page 103: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/103.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
q1
1
2
4
5
3
6
r12r23 r15r56r13
s1
![Page 104: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/104.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Simulacio de l’algorisme de Bentley-Ottman
1
2
4
5
3
6
r12r23 r15r56r13
![Page 105: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/105.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Algorisme de Bentley-Ottman
![Page 106: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/106.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Algorisme de Bentley-Ottman
Correccio
• L’algorisme troba totes les interseccions (gracies a l’Observacio 2)
• L’algorisme no troba cap falsa interseccio (ja que els talls es comproven)
![Page 107: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/107.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Algorisme de Bentley-Ottman
Correccio
• L’algorisme troba totes les interseccions (gracies a l’Observacio 2)
• L’algorisme no troba cap falsa interseccio (ja que els talls es comproven)
Gestio dels casos degenerats
• Per manegar el cas que diversos punts puguin tenir la mateixa abscissa, sols cal quela cua d’esdeveniments, E, emmagatzemi els punts en ordre lexicografic, i no solsper ordre d’abscissa.
• L’algorisme pot detectar, trivialment, si dos o mes segments es tallen en mes d’unpunt (es a dir, es tallen en un segment), donat que s’atura als seus extrems.
• Una petita modificacio permet tambe resoldre el cas que tres o mes segments estallen en un mateix punt: sols cal invertir el seu ordre a la recta d’escombrat en elmoment que l’algorisme s’atura al punt de tall.
![Page 108: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/108.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Algorisme de Bentley-Ottman
Estructures de dades
![Page 109: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/109.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Algorisme de Bentley-Ottman
Estructures de dades
Recta d’escombrat, R:
Ha de mantenir l’ordre total dels segments interceptats i suportar:
• insertar(s)
• esborrar(s)
• transposar(s1, s2)
• anterior(s)
• posterior(s)
Un diccionari (arbre binari equilibrat) permet fer cadascuna d’aquestes operacions entemps O(log n)
![Page 110: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/110.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Algorisme de Bentley-Ottman
Estructures de dades
Cua d’esdeveniments, E:
Ha de mantenir l’ordre total dels esdeveniments i suportar:
• mınim (reportar i extreure)
• insertar(p)
• memberQ(p)
Una cua de prioritat (arbre binari equilibrat) permet fer cadascuna d’aquestes operacionsen temps O(log n)
![Page 111: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/111.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Algorisme de Bentley-Ottman
Complexitat (temps)
![Page 112: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/112.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Algorisme de Bentley-Ottman
Complexitat (temps)
Inicialitzacio: O(n log n)
Avenc (es fa 2n + k cops):1. O(log n)2. 3. 4. O(log n)5. O(log n)
Total: O((n + k) log n)
![Page 113: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/113.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Algorisme de Bentley-Ottman
Complexitat (temps)
Inicialitzacio: O(n log n)
Avenc (es fa 2n + k cops):1. O(log n)2. 3. 4. O(log n)5. O(log n)
Total: O((n + k) log n)
Els comptes anteriors corresponen al cas no degenerat.En el cas que els punts de tall, vi, puguin correspondre a mes de dos segments, el cost total del’avenc de l’algorisme es O((
∑ki=1 grau(vi)) log n). Ara be, si es consideren els punts vi com a
vertexs del graf:
k∑i=1
grau(vi) ≤ 2a = O(a) = O(v) = O(2n + k) = O(n + k).
![Page 114: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/114.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Algorisme de Bentley-Ottman
Complexitat (espai)
![Page 115: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/115.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Algorisme de Bentley-Ottman
Complexitat (espai)
En cada pas de l’algorisme, la recta d’escombrat emmagatzema, com a molt, n segments.
![Page 116: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/116.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Algorisme de Bentley-Ottman
Complexitat (espai)
En cada pas de l’algorisme, la recta d’escombrat emmagatzema, com a molt, n segments.
En la formulacio exposada fins aquı, la cual d’esdeveniments emmagatzema, en algun momentde l’algorisme, tots els punts de tall, que son k = O(n2).
![Page 117: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/117.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
Algorisme de Bentley-Ottman
Complexitat (espai)
En cada pas de l’algorisme, la recta d’escombrat emmagatzema, com a molt, n segments.
En la formulacio exposada fins aquı, la cual d’esdeveniments emmagatzema, en algun momentde l’algorisme, tots els punts de tall, que son k = O(n2).
Tanmateix, una petita modificacio permet que la cua d’esdevaniment emmagatzemi, en cadapas de l’algorisme, com a molt 2n-1 esdeveniments. Aixo es pot aconseguir si, a cada pas, solses guarden a E les interseccions dels segments que son adjacents a R, els quals s’esborren quandeixen de ser-ho.
![Page 118: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/118.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
El problema de decisio
![Page 119: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/119.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
El problema de decisio
Entrada: n segments del pla, si = (pi, qi), i = 1 . . . n.Sortida: Si/No hi ha interseccio entre alguns dels segments, i reportar un testimoni
![Page 120: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/120.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
El problema de decisio
Entrada: n segments del pla, si = (pi, qi), i = 1 . . . n.Sortida: Si/No hi ha interseccio entre alguns dels segments, i reportar un testimoni
L’Algorisme de Bentley-Ottman resol aquest problema en temps O(n log n).
Solucio
![Page 121: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/121.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
El problema de decisio
Entrada: n segments del pla, si = (pi, qi), i = 1 . . . n.Sortida: Si/No hi ha interseccio entre alguns dels segments, i reportar un testimoni
L’Algorisme de Bentley-Ottman resol aquest problema en temps O(n log n).
Solucio
Fita inferior
El problema de decisio es Ω(n log n).
![Page 122: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/122.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
El problema de decisio
Entrada: n segments del pla, si = (pi, qi), i = 1 . . . n.Sortida: Si/No hi ha interseccio entre alguns dels segments, i reportar un testimoni
L’Algorisme de Bentley-Ottman resol aquest problema en temps O(n log n).
Solucio
Fita inferior
El problema de decisio es Ω(n log n).
Aixo es demostra per reduccio del problema d’unicitat sobre enters:
Donats x1, . . . , xn ∈ N, es construeixen pi = (xi, 0), qi = (xi, 1) i si = (pi, qi).Els segments es tallen si, i nomes si, els nombres originals tenien repeticions.
Si no us agrada la degeneracio dels segments, considereu els punts seguents:pi = (xi − 1
2i , 0) i qi = (xi + 12i , 1).
![Page 123: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/123.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
El problema de reportar totes les interseccions
![Page 124: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/124.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
El problema de reportar totes les interseccions
Corol.lari
El problema de reportar totes les interseccions es Ω(k + n log n), ja que
• Reportar requereix Ω(k)
• Decidir requereix Ω(n log n)
![Page 125: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/125.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
El problema de reportar totes les interseccions
Corol.lari
El problema de reportar totes les interseccions es Ω(k + n log n), ja que
• Reportar requereix Ω(k)
• Decidir requereix Ω(n log n)
Algorisme optim
Existeix un algorisme de Chazelle i Edelsbrunner que resol aquest problema en tempsΘ(k + n log n).
![Page 126: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/126.jpg)
INTERSECCIO DE SEGMENTS
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
El problema de reportar totes les interseccions
Corol.lari
El problema de reportar totes les interseccions es Ω(k + n log n), ja que
• Reportar requereix Ω(k)
• Decidir requereix Ω(n log n)
Algorisme optim
Existeix un algorisme de Chazelle i Edelsbrunner que resol aquest problema en tempsΘ(k + n log n).
Consequencies
• El problema de decidir si un polıgon es simple es pot resoldre en temps O(n log n).
• El problema de decidir si dos polıgons simples es tallen es pot resoldre en tempsO(n log n).
![Page 127: Universitat Polit`ecnica de Catalunya Facultat d’Inform](https://reader036.vdocumento.com/reader036/viewer/2022071315/62cd8d801bdf911a5d53e558/html5/thumbnails/127.jpg)
INTERSECCIO DE SEGMENTS
PER SABER-NE MES
Geometria Computacional, Facultat d’Informatica de Barcelona, UPC
• F. Preparata, M. Shamos, Computational Geometry: An introduction (revised ed.),Springer, 1993.
• M. de Berg, O. Cheong, M. van Kreveld, M. Overmars: Computational Geometry:Alhorithms and Applications, Springer.
• J-D. Boissonnat, M. Yvinec, Algorithmic Geometry, Cambridge University Press,1998.