Geometria obliczeniowa –

przecinanie się odcinków

• Łukasz Gos
• Kamil Kasprzyk
• Grupa 312A

Jak liczyć przecinanie się odcinków

• Jeżeli mamy punkty: A=(x1,y1), B=(x2,y2), C=(x3,y3) i D=(x4,y4)
• Gdy chcemy sprawdzić czy odcinki |AB| i |CD| przecinają się

musimy sprawdzić czy oba końce danego odcinka leżą po
przeciwnych stronach danego odcinka

• W tym celu musi zachodzić pewna nierówność:

sign[det(A,B,C)] <> sign[det(A,B,D)]
Która oznacza, że punkty C i D leżą po przeciwnych stronach
odcinka |AB|

• Dla pewniejszego wyniku należy sprawdzić 2 nierówności:

sign[det(A,B,C)] <> sign[det(A,B,D)]
sign[det(C, D, A)] <> sign[det(C, D, B)]

Geometryczne podejście do nakładania się:

• mamy daną sieć złożoną z odcinków tworzącą zbiory
• dla dwóch zbiorów obliczyć wszystkie przecięcia pomiędzy

odcinkami z jednego zbioru i odcinkami drugiego zbioru

• odcinki zdefiniowane są jako domknięte, czyli koniec jednego

docinka, leżący na drugim odcinku, liczy się jako przecięcie

• odcinki z obydwu zbiorów umieszczamy w jednym i wyznaczamy

ich przecięcia

Sposoby obliczania przecięć:

• algorytm siłowy
• algorytm zamiatania

Algorytm siłowy:

• dla każdej pary odcinków ze
zbioru obliczamy możliwość
przecięcia

Wady tej metody to:
• wolny czas wykonywania
O(n

2

)

• gdy każda para odcinków
przecina się algorytm wymaga
czasu Ω(n

2

)

Algorytm zamiatania:

• Stosowany by
zoptymalizować czas szukania
przecinanych odcinków

Zasada działania:

• Mamy dany zbiór odcinków
S:={s

1

, s

2

,…, s

n

}

Krok 1:
Próba wyeliminowania par
odcinków leżących daleko od
siebie:

• przedział odcinka definiujemy
jako rzut prostopadły na oś y

• gdy przedziały par odcinków
nie zachodzą na siebie
traktujemy je jako oddalone
daleko od siebie bez możliwości
przecinania

• sprawdzamy więc tylko pary
odcinków których przedziały
zachodzą na siebie

Krok 2:

• używamy tzw. miotły (prostej
poziomej) która przesuwa się w dół

• stanem miotły jest zbiór odcinków
przecinających ją

• aktualizacja stanu zmienia się
jedynie w pewnych sytuacjach
nazywanych punktami zdarzeń (są
nimi końce odcinków)

• tylko w punktach zdarzeń algorytm
aktualizuje stan miotły i wykonuje
testy przecięć

• odcinki usuwane ze stanu gdy
punkt zdarzeń jest dolnym punktem
końcowym odcinka

W dalszym ciągu jednak możliwe są
układy dla których sprawdzamy
kwadratową liczbę par podczas gdy
jest niewielka liczba punktów
przecięcia np. wszystkie docinki
przecinają oś x.

Krok 3:

• Porządkujemy odcinki od lewej
do prawej

• sprawdzamy tylko 2 odcinki
bezpośrednio po lewej i po prawej
od punktu zdarzeń

• w chwili przecięcia zmienia się
porządek odcinków, przez co
należy sprawdzić nowe pary
docinków

• stan miotły zmienia się w
punktach zdarzeń jak również w
punktach przecięcia

Założenie jest poprawne jeśli przyjmiemy że:

• nie bierzemy pod uwagę odcinków poziomych

• żadne trzy docinki nie krzyżują się w jednym punkcie

Przykład zmiany sprawdzania stanu spowodowanej wykryciem
nowego odcinka przecinającego:

• s

i

i s

k

sąsiadują ze sobą na miotle

• między nimi pojawia się nowy odcinek s

j

• należy sprawdzić w związku z tym przecięcia s

j

z s

i

i s

k

Struktury danych wykorzystywane przez

algorytm zamiatania:

• kolejka zdarzeń (przechowuje zdarzenia)

Do obsługi kolejki zdarzeń wykorzystywany jest algorytm który
dodaje i usuwa zdarzenia z niej. Jeśli 2 odcinki maja jednakową
współrzędną y to zwrócony z kolejki zdarzeń będzie zwracany ten
z mniejsza współrzędną x

• zrównoważone drzewo wyszukiwań binarnych

Przechowuje informacje o odcinkach które w danej chwili
przecinają miotłę

Algorytm FindIntersections

• Jest to algorytm wykorzystujący struktury:

- kolejki zdarzeń
- zrównoważone drzewo wyszukiwań binarnych

• Jego zadaniem jest wykrycie przecinających się odcinków
• Algorytm ten poprawnie oblicza wszystkie punkty przecięcia i

odcinki które je zawierają

• Czas działania algorytmu dla zbioru S, zawierającego n odcinków

na płaszczyźnie wynosi O(n log n + I log n), gdzie I jest liczbą
punktów przecięcia odcinków z S