[DELPHI] Kolizje trójkątów

0

Jak wykryc nachodzenie na siebie trojkatow lub innych wieloboków?

--

Pełen chenci i zapałó :)

0

Ooo. Ten post spodoba się kapustce :)
Zakładam, że masz 3 punkty każdego trójkąta.
Zadanie można chyba sprowadzić do zagadnienia:
Czy dany punkt należy do trójkąta?
Wystarczy wówczas sprawdzić, czy którykolwiek z 3 wierzchołków I trójkąta zawiera się w II trójkącie i na odwrót: czy którykolwiek z 3 wierchołków II zawiera się w pierwszym.
Moim zdaniem najprostszym sposobem sprawdzenia tego, jest poprowadzenie prostej przez dany punkt i sprawdzenie, czy punkty przecięcia się prostej z bokami trójkąta znajdują się po obu stronach naszego punktu. Jeżeli tak, to znaczy, że nasz punkt leży w środku trójkąta (lub dowolnego innego wielokąta wypukłego).

--
Jest jeszcze jeden błąd ... :)
--------Oficjalny kanał----------
Service for programmers w IRC:
Kanał: #4programmers
Serwer: warszawa.ircnet.pl
Sieć: POLNet
Port: 6667

0

Uff dzieki za wyczerpujacom odpowiedz ale jak to zrobic w Delphi??

--

Pełen chenci i zapałó :)

0

Uff dzieki za wyczerpujacom odpowiedz ale jak to zrobic w Delphi??

Trochę prowizoryczne, ale:
Mamy punkty trójkąta I: A, B i C oraz punkt dla którego sprawdzamy D

function CzyWewTroj(A, B, C, D: TPoint): Boolean;
var
x1, x2, x3: Integer;
begin
x1 := (D.y - B.y)(B.x - C.x)/(B.y - C.y) + B.x;
x2 := (D.y - B.y)
(B.x - A.x)/(B.y - A.y) + B.x;
x3 := (D.y - A.y)*(A.x - C.x)/(A.y - C.y) + A.x;
if ((D.x x2))
or ((D.x > x1)and(D.x x1)and(D.x x3)and(D.x

0

a wlasniebo ten tego: mopze ktos wie jak wykryc czy punkt w przestrzeni znajduje się w trójkącie o trzech wierzchołkach znajdującxychsię w przestrzeni? :]

0

a wlasniebo ten tego: mopze ktos wie jak wykryc czy punkt w przestrzeni znajduje się w trójkącie o trzech wierzchołkach znajdującxychsię w przestrzeni? :]

Podobnie. Tylko musisz najpierw sprawdzić, czy punkt znajduje się w płaszczyźnie zawierającej trójkąt.
4 punkty znajdują się w jednej płaszczyźnie jeżeli wyznacznik:
| x1 y1 z1 1|
| x2 y2 z2 1|
| x3 y3 z3 1|
| x4 y4 z4 1|

jest równy 0.

Później tak samo, tylko że prostą musisz poprowadzić przez punkty w przestrzeni.

A tak na marginesie: słyszałem, że piszesz moduł do obsługi przekształceń w przestrzeni. Wykorzystujesz macierze? (to chyba najwygodniejszy sposób)

--
Jest jeszcze jeden błąd ... :)
--------Oficjalny kanał----------
Service for programmers w IRC:
Kanał: #4programmers
Serwer: warszawa.ircnet.pl
Sieć: POLNet
Port: 6667

0

ble macierz czy chodzi ci o te wierzcholki ??? bo ja nie mam zielonego pojecia o macierzy :) co to do cholery jest :)

tak moj modulek bedzie rysowal cosik w 3d ale nic poza tym
moze bedzie nawet udostepnione teksturowanie :) i to wszystko bez wykorzystania opengl ani driectX :] tylko na normalnym canvasie :)
wiec najbardziej bedzie sie liczyc szybkosc procka: jak na razie przestrzeń w poczatkowej fazie testow o ograniczeniu jej do -300-300 wyciaga w porywach 30 fps :]

0

ble macierz czy chodzi ci o te wierzcholki ??? bo ja nie mam zielonego pojecia o macierzy :) co to do cholery jest :)

Macierze - jak dla ciebie to tablice prostokątne o specyficznych właściowściach. Wykorzystuje to zarówno DirectX jak i OpenGL. Zmieniając jedynie 4 liczby w całej tablicy masz obrócony obiekt. Zmieniając inne wartości masz go powiększonego, rozciągniętego i wiele innych przekształceń. Bardzo przydatna rzecz.

--
Jest jeszcze jeden błąd ... :)
--------Oficjalny kanał----------
Service for programmers w IRC:
Kanał: #4programmers
Serwer: warszawa.ircnet.pl
Sieć: POLNet
Port: 6667

0

[niewinnosc]
Witam wszystkich.

"4 punkty znajdują się w jednej płaszczyźnie jeżeli wyznacznik:
| x1 y1 z1 1|
| x2 y2 z2 1|
| x3 y3 z3 1|
| x4 y4 z4 1|
jest równy 0.", Dryobates

Zdecydowanie najlepszy sposób ! Równanie jest proste, ale odnoszę wrażenie że metoda dochodzenia do niego wymaga komentarza. Dlaczego punkty leżą na jednej płaszczyźnie kiedy wyznacznik=0 ? Dlaczego ten sposób jest prawidłowy ?

(niezainteresowanych całą sprawą odsyłam do drugiej części posta)

Wpierw trzeba odpowiedzieć sobie na pytanie - W jakich okolicznościach wyznacznik jest równy 0? Otóż wyznacznik jest równy 0 wtedy, gdy jeden z jego wierszy jest kombinacją liniową pozostałych.

Metodę zasugerowaną przez Dryobatesa można sprowadzić do następującej procedury:

  1. każdemu (z czterech) punktów (należących do R3 przypisujemy wektor (o początku w środku układu współrzędnych, a końcu w danym punkcie).
  2. następnie dopisujemy naszym wektorom czwarty wymiar t (przypisujemy t=1 dla każdego z nich), wektory leżą teraz w przestrzeni R4.
  3. sprawdzamy czy tak zmodyfikowane wektory tworzą bazę przestrzeni R4.

Co to znaczy że wektory tworzą bazę pewnej przestrzeni? To znaczy ze każdy wektor należący do tej przestrzeni jest kombinacją liniową wektorów tworzących bazę.

Kiedy wektory tworzą bazę? kiedy są niezależne liniowo, czyli żaden z nich nie jest kombinacją liniową pozostałych, czyli wtedy gdy odpowiedni wyznacznik jest różny od 0.

Dochodzimy teraz do sedna: jeżeli wektory nie tworzą bazy przestrzeni R4 (czyli ich wyznacznik jest równy 0), oznacza to że leżą na jednej płaszczyźnie (bądź też na jednej prostej w szczególnym wypadku), gdyż tylko przy takim ich ułożeniu nie można sprowadzić każdego wektora R4 do kombinacji liniowej naszych wektorów.

Czemu to wszystko napisałem?
Bo jestem kapustką.

(a mówiąc poważnie: chciałem pokazać że ten prosty wzór wynika z całego subtelnego toku rozumowania, przy czym pewne elementy pominąłem na rzecz czytelności).

Przechodzę teraz do głównego tematu.

Jak sprawdzić czy wieloboki na siebie zachodzą ? Uprośćmy nasz problem do dwóch trójkątów, określonych za pomocą współrzędnych wierzchołków na płaszczyźnie.

Znamy więc współrzędne wierzchołków. Jak - czytelniku - byś sprawdził czy opisane przez nie trójkąty na siebie zachodzą ? Osobiście narysował bym układ wsp. naniósł punkty, połączył je odcinkami i ... i od razu widać czy na siebie nachodzą.

Aż ciężko uwierzyć, że komputery nie są w stanie "zobaczyć" rzeczy tak oczywistej.

Narzuca się następująca metoda (to nie jest jeszcze algorytm):

  1. konstruujemy funkcję f(p,a,b,c), która stwierdza czy punkt p leży wewnątrz trójkąta a,b,c i stosownie do tego f() zwraca wartość true/false.
  2. posługując się powyższą funkcją f() sprawdzamy:
    czy którykolwiek z wierzchołków trójkąta 1 nie leży wewnątrz trójkąta 2.
    czy którykolwiek z wierzchołków trójkąta 2 nie leży wewnątrz trójkąta 1.

Jeżeli w jakimkolwiek momencie okaże się że f() zwróciło true, przerywamy procedurę i mówimy "trójkąty nachodzą na siebie". W przeciwnym wypadku po sprawdzeniu wszystkich wierzchołków mówimy "trójkąty nie nachodzą na siebie".

"Po sprawdzeniu wszystkich wierzchołków". Ile ich jest ? Dla dwóch trójkątów 23=6, dla dwóch czterokątów 24=8, ogólnie dla n-wierzchołków będziemy wywoływać procedurę f() w najgorszym przypadku 2n-razy. (obliczeniowo najgorszy przypadek to wtedy gdy dane wielokąty nie zachodzą na siebie).

2n razy - nie jest źle. Prawdę mówiąc to znakomicie (moja matematyczka by powiedziała "to bardzo przewspaniale"). 2n razy wywołujemy funkcję f(). A czym jest funkcja f() dla dowolnego wielokąta ? Jak działa funkcja f() ?

Dryobates rozpisał przykład takiej funkcji dla dwóch trójkątów, niemniej post nie został poprawnie wyświetlony.

Myślę że możemy nasze dalsze
rozważania sprowadzić do następującego problemu:

Dane wejściowe: współrzędne punktów p,a1,a2,...,an na płaszczyźnie.
Wynik: funkcja f(p,a1,a2,...,an), taka że jej wartość
= true, gdy punkt p leży wewnątrz wielokąta rozpiętego na punktach a1,a2,...,an.
= false w przeciwnym wypadku.

Jak zwykle proszę o rozpisywanie algorytmów w pseudojęzyku, (a nie implementacji), ewentualnie o nadsyłanie pomysłów i spostrzeżeń.

Pozdrawiam.
[niewinnosc]

1 użytkowników online, w tym zalogowanych: 0, gości: 1