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 ?
[Algorytmy] Znalezienie odcinków przecinających się
-
- Użytkownik
- Posty: 26
- Rejestracja: 6 lut 2012, o 16:13
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 10 razy
[Algorytmy] Znalezienie odcinków przecinających się
Ostatnio zmieniony 20 sie 2013, o 16:36 przez Afish, łącznie zmieniany 2 razy.
Powód: Nieczytelny zapis - brak LaTeX-a. Proszę zapoznaj się z instrukcją: http://matematyka.pl/latex.htm .
Powód: Nieczytelny zapis - brak LaTeX-a. Proszę zapoznaj się z instrukcją: http://matematyka.pl/latex.htm .
-
- Użytkownik
- Posty: 1406
- Rejestracja: 6 maja 2012, o 22:46
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 107 razy
- Pomógł: 145 razy
[Algorytmy] Znalezienie odcinków przecinających się
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
- Użytkownik
- Posty: 1897
- Rejestracja: 14 kwie 2013, o 10:58
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 2 razy
- Pomógł: 512 razy
[Algorytmy] Znalezienie odcinków przecinających się
Tzn. na tych odcinkach?Ser Cubus pisze: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)
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