[Algorytmy] Znalezienie odcinków przecinających się

[taktofon]

Niech ktoś mi powie co mu wyszło z tego zadania:

Dany jest zbiór odcinków na płaszczyźnie :
\(\displaystyle{ \{a = [ (3,1), (7,6)], b = [ (0,2), (2,2)], c =[ (1,5), (6,1)], d =[ (1,5), (6,1)], e=[ (0,1), (7,2)],\}}\)
Zastosuj algorytm na sprawdzanie czy w zbiorze istnieje para przecinających się odcinków.
Podaj wszystkie stany „miotły" od początku działania algorytmu aż do znalezienia pierwszej
pary przecinających się odcinków.

Czy to będzie para \(\displaystyle{ (e,a)}\) czy \(\displaystyle{ (e,c)}\) i dlaczego ?

[Ser Cubus]

wyzanczaj kolejno równania prostych przechodzących przez 2 punkty i sprawdz czy maja pkt przeciecia, następnie sprawdź czy te punkty należą do twojej 'dziedziny' (tzn. czy są na tych prostych)

[mdd]

wyzanczaj kolejno równania prostych przechodzących przez 2 punkty i sprawdz czy maja pkt przeciecia, następnie sprawdź czy te punkty należą do twojej 'dziedziny' (tzn. czy są na tych prostych)

Tzn. na tych odcinkach?

Początkowo sobie pomyślałem, że może byłoby warto najpierw sprawdzić czy "przedziały określoności" odcinków zachodzą na siebie, tzn. czy mają część wspólną... po to by już nie liczyć współrzędnych punktu przecięcia prostych wyznaczonych przez odcinki w przypadku gdy część wspólna tych przedziałów jest pusta... ale chyba nie ma sensu rozgałęziać tak algorytmu (?).

Czy ten problem i jego rozwiązanie ma jakieś konkretne zastosowanie praktyczne?
Może da się jakoś wykombinować jakiś szybszy algorytm

[taktofon]

To da się zrobić tzw. miotłą

[Ser Cubus]

tzn?

[mdd]

Tutaj coś znalazłem: