Jak wykryć kolizje między ikoną a kształtem wygenerowanym przez użytkownika?

9

Jak wykryć kolizję między duchem a jakimś kształtem wygenerowanym przez użytkownika.

Na przykład. Na ekranie jest kilka obiektów. Użytkownik bierze palec i rysuje okrąg wokół obiektu (regułą wyboru jest malowanie koła wokół duszka, ale kształty malowania mogą być różne). Muszę wykryć wybrany obiekt, który podobnie jak:

(obrazy demo): pierwotnie opublikowany jako http://i52.tinypic.com/28h0t1g.png

collision-detection Huwell
źródło
Czy możesz wyjaśnić, dlaczego w ostatnim przykładzie wybrano kolor niebieski, a nie czerwony? Czy możesz również wyjaśnić, czy linia musi rzeczywiście dotykać duszka? Trzeci przykład nie dotyka czerwonego pola, ale jest zaznaczony jako wybrany. Piąty przykład jest bardzo podobny, ale nie został wybrany. Jakiej różnicy szukasz między 3 a 5?
Romen

Odpowiedzi:

2

Jeśli kształt jest rysowany głównie za pomocą segmentów linii od użytkownika (lub krzywych Beziera z punktami kontrolnymi), można zaimplementować dość powszechnie stosowany algorytm znany jako Twierdzenie o Osi Oddzielającej . Mówiąc prosto: jeśli istnieje oś (wektor jednostkowy reprezentujący kierunek), na której kształty nie zachodzą na siebie (ich rzutowane wartości nie dają dodatniej różnicy), obiekty nie nakładają się. Używałem tego w przeszłości i działało to jak urok.

Ponury
źródło
1

Jeśli kształt jest rysowany ręcznie, jak w Crayon Physics , możesz trzymać tablicę linii prostych i sprawdzać kolizje z każdą z nich. Pomimo prostych linii możesz używać krzywych Beziera lub czegoś podobnego.

w prawym górnym rogu
źródło
0
  • Utwórz bufor o tym samym rozmiarze co ekran (lub powierzchnia, na której znajdują się Twoje kształty). W każdej pozycji zawiera wartość logiczną, czy jest duszek; następnie sprawdź wszystkie „piksele” kształtu użytkownika, czy na ich pozycji znajduje się duszek (sprawdzając wartość tego boolean). Możesz też utworzyć tam więcej duszków, przechowując ich ID zamiast wartości logicznej; ale tak było w przypadku 1 duszka.
  • Jeśli kształt wygenerowany przez użytkownika może być reprezentowany przez sekwencję linii, możesz sprawdzić, czy każda taka linia przecina duszka. Ponieważ duszek ma kształt prostokąta, a kształt użytkownika jest linią, po prostu poszukaj „przecięcia prostokąta linii” ... (algorytm oddzielania osi jest jednym ze sposobów, aby to zrobić)

Podejścia zależą od wybranych struktur danych, niezależnie od tego, czy są to mapy bitowe, czy wektory.

Pierwsze podejście może obsługiwać dowolne złożone kształty, jest łatwe do wdrożenia, ale zużywa więcej pamięci. W rzeczywistości można zmniejszyć obciążenie pamięci za pomocą kompresji i przyspieszyć ją za pomocą hierarchicznych struktur danych (oktetów) ...

Drugie podejście nie jest tak łatwe do wdrożenia, ale wymaga większej mocy obliczeniowej.

W każdym przypadku zmierzyć, czy ma to znaczenie. Spróbowałbym zrobić pierwszy, ponieważ jest łatwiejszy do wdrożenia. Powodzenia. :)

użytkownik712092
źródło