Autor Wątek: Jak sprawdzić, czy odcinek przecina półprostą  (Przeczytany 2785 razy)

Offline _MtZ_

  • Użytkownik

# Sierpień 28, 2007, 17:05:14
Sprawdzenie czy dwa odcinki się przecinają, albo czy odcinek przecina prostą jest łatwe
(http://ux1.math.us.edu.pl/~szyjewski/FAQ/geo_anal/wewnatrz.htm) ale pojęcia nie mam jak sprawdzić czy odcinek przecina półprostą.
Chodzi mi o coś takiego:


Macie jakieś propozycje?

//Edit:
Zapomniałem dodać co jest dane:
- współżędne punktów A,B,C
- wektor kierunkowy półprostej

Oczywiście równania prostych w których zawierają się odcinek i półprosta jest łatwo policzyć więc one też są dane.
« Ostatnia zmiana: Wrzesień 29, 2007, 22:10:59 wysłana przez _MtZ_ »

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline KrystianD

  • Użytkownik
    • http://krystiand.net

# Sierpień 28, 2007, 17:19:28
Nie wiem jak się to robi profesjonalnie, ale ja bym to zrobił tak:
Potraktował półprostą jako odcinek o końcach C i D(C+kierunek)
Znalazł punkt przecięcia poprzez wyszukanie wartości t0 dla odcinka AB i t1 dla odcinka CD
Sprawdził czy t0 zawiera się w przedziale 0..1 i a t1 w 0..+INF :)

Ta stronka może się przydać
http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline2d/
Tam t0 to ua a t1 to ub
« Ostatnia zmiana: Sierpień 28, 2007, 17:22:51 wysłana przez Krystian D. »

bies

  • Gość
# Sierpień 28, 2007, 17:26:08
1) Sprawdź czy odcinek przecina prostą zawierającą półprostą.
2) Jeśli nie to półprostej też nie przecina.
3) Jeśli tak policz punkt przecięcia (X).
4) Sprawdź czy X leży na półprostej.

+/- optymalizacje.

Offline _MtZ_

  • Użytkownik

# Sierpień 28, 2007, 17:38:49
Tylko troche szkoda mi czasu na liczenie miejsca przecięcia skoro muszę tylko wiedzieć czy przecięcie nastąpiło. Poszperam jeszcze w necie troche a jeśli sie nie da inaczej to zrobie jak radzicie.
Jednak wciąż jestem otwarty na pomysły :)

Offline Xion

  • Redaktor
    • xion.log

# Sierpień 28, 2007, 18:15:59
1) Sprawdź czy przypadkiem odcinek nie leży w całości po jednej ze stron płaszczyzny wyznaczonej przez prostą która zawiera twoją półprostą. (Czyli czy nie zachodzi środkowy przypadek). W tym celu weź dowolny punkt półprostej C' != C i sprawdż czy cross(C-C', C-A).z i cross(C-C', C-B).z mają ten sam znak. Jeśli tak, to zachodzi wspomniany przypadek.
2) Jeśli nie, to weź prostą prostopadłą do półprostej, przechodzącą przez punkt C. W sposób podobny jak w 1) sprawdź, czy któryś z punktów leży po tej samej stronie tej prostej prostopadłej, co twoja półprosta. Jeżeli żaden nie leży, to mamy przypadek trzeci. Jeżeli leżą oba, to pierwszy (przecięcie).
3) W przypadku gdy jeden leży po stronie z połprostą, a drugi po stronie bez półprostej, mamy przypadek problematyczny i póki co nie wiem jak go ugryźć ;]

Offline _MtZ_

  • Użytkownik

# Sierpień 28, 2007, 18:21:24
Pogłówkowałem troche i udało sie to rozwiązać. Działam wg. algorytmu:
1. Sprawdzam, czy odcinek przecina prostą na której leży półprosta(odsyłam do linku który podałem w 1 poscie)
2. Jeśli nie to zwróć false.
3. Sprawdzam po której stronie odcinka leży punkt w którym jest zaczepiony wektor(dodatniej(1), ujemnej(-1), czy punkt leży na odcinku(0) ). Zapisuję wynik w zmiennej(np: s)
4. Jeśli s==0 zwróć true.
5. Rzutuję wektor na normalną odcinka(jak na rysunku) metodą DotProduct(). Wynik zapisuję w zmiennej(np: d )

Obrazek: http://www.wrzuta.pl/obraz/pDOYLtBQXx/rozwiazanie
Teraz mamy wszystkie potrzebne dane.
Jeśli:
- ((s>0)&&(d>0)) zwróć  false;
- ((s>0)&&(d<0)) zwróć  true;

- ((s<0)&&(d<0)) zwróć  false;
- ((s<0)&&(d>0)) zwróć  true;

Lub w 2 warunkach:
Jeśli (s*d>0): zwróć false;
Inaczej: zwróć true;


Chyba będzie działać :)
Edit:: poprawiłem literówki

// Edit 2: Algorytm po kilku poprawkach działa bez zarzutu. Jeśli chcecie to wrzuce kod źródłowy.
« Ostatnia zmiana: Sierpień 29, 2007, 01:11:08 wysłana przez _MtZ_ »