Autor Wątek: Kolizja dwóch wielokątów wypukłych.  (Przeczytany 2027 razy)

Offline C'mons

  • Użytkownik

# Kwiecień 01, 2011, 18:31:15
Jak sprawdzić czy nachodzą na siebie 2 wielokąty wypukłe o dowolnej liczbie wierzchołków?

Sam mam taki pomysł:
1. Sprawdź czy któryś z wierzchołków wielokąta A zawiera się w wielokącie B. ( Jeśli tak, zakończ informując o kolizji. )
2. Sprawdź czy któryś z wierzchołków wielokąta B zawiera się w wielokącie A. ( Jeśli tak, zakończ informując o kolizji. )
3. Sprawdź czy któraś z par odcinków wielokątów przecina się. ( Jeśli tak, zakończ informując o kolizji. )
4. Zakończ informując że nie wystąpiła kolizja wielokątów.

Ale nie jestem pewien co do jego skuteczności i czy nie można by jakoś szybciej?

Offline Mr. Spam

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

Offline nembutal

  • Użytkownik

# Kwiecień 01, 2011, 18:52:22
Ten twój algorytm jest skrajnie nieoptymalny :D
Nie wiem czy istnieje szybszy sposób niż method of separating axes.

Offline Reg

  • Administrator
    • Adam Sawicki - Home Page

# Kwiecień 01, 2011, 23:47:06
Do sprawdzania kolizji figur wypukłych najlepszy jest SAT - Separating Axis Theorem.

Z kolei do niego najlepszy tutorial jest tutaj:
http://www.metanetsoftware.com/technique/tutorialA.html
Zawiera interaktywne aplety Flash :)

Offline Dab

  • Redaktor
    • blog

  • +1
# Kwiecień 02, 2011, 00:41:02
Cytuj
Do sprawdzania kolizji figur wypukłych najlepszy jest Box2D

Fixed. ;)

Offline koirat

  • Użytkownik

# Maj 30, 2012, 23:30:38
Dopisze się tu, bo nie chce zakładać nowego wątku w tej dziedzinie.

W SAT robimy projekcję wierzchołków na prostą prostopadłą do aktualnie badanego boku.

Teraz mam pytanie czy traktujecie to dosłownie, jako projekcję na tą prostą, czy transformujecie wierzchołki badanych figur poprzez obrót w taki sposób iż prosta na którą rzutujemy staje się jedną z osi głównych (OX bądź OY).

Sam zastanawiam się nad tą drugą metodą, projekcja na taką losową prostą wydaje mi się problematyczna choćby z tego powodu iż istnieje potrzeba zaimplementowania specjalnych rozwiązań gdy prosta ta okaże się być pionowa.


Offline raver

  • Użytkownik
    • Moja strona domowa.

# Maj 31, 2012, 01:38:06
dp = (a.x*b.x + a.y*b.y)

proj.x = ( dp / (b.x*b.x + b.y*b.y) ) * b.x;
proj.y = ( dp / (b.x*b.x + b.y*b.y) ) * b.y;

Nie widzę tu żadnego problemu z pionowymi prostymi :).

Offline koirat

  • Użytkownik

# Maj 31, 2012, 11:59:13
Czy wiesz jak działa SAT ?
A jak już piszesz jakiś wzór to prosił bym cię o opisanie skąd co się bierze.

Offline raver

  • Użytkownik
    • Moja strona domowa.

  • +1
# Maj 31, 2012, 13:48:22
Czy wiesz jak działa SAT ?
Hm... kiedyś zdaję się napisałem pseudo silnik fizyczny na SATcie właśnie, wiec coś tam o tym słyszałem :).

Wzór jest z linka zamieszczonego powyżej przez Rega. Jest na rzutowanie wektora A na wektor B. Nie mam pojęcia skąd się wziął, ale wyprowadzenie nie byłoby pewnie zbyt trudne.

Offline Kos

  • Użytkownik
    • kos.gd

  • +3
# Maj 31, 2012, 13:57:40
@Koirat, hint: Prosta w 2D to nie tylko y=ax+b, ale też np. Ax+By+C=0, wtedy nie ma żadnych anomalii z pionowymi.