Jak działa prosty głupi algorytm lejkowy?

Odpowiedzi:

18

Algorytm zaczyna się od znalezionej wcześniej ścieżki, w tym przypadku listy trójkątów:

ścieżka

Kod na dole posta na blogu Mikko tworzy tablicę portali, która jest listą segmentów linii reprezentujących segmenty linii między wielobokami ścieżki. Są to „portale”, przez które musi przejść wygładzona ścieżka (lub krawędzie wielokąta z „prześledźmy punkty środkowe krawędzi wielokąta”). Pamiętaj, że lista portali zaczyna się i kończy zdegenerowanymi segmentami linii w punktach początkowym i bramkowym.

Ta lista portali jest pokazana jako żółte segmenty linii przerywanej na jego zdjęciach.

portale

Algorytm rozpoczyna się od szerokiego lejka i przechodzi przez iteracyjne przesuwanie boków lejka do przodu wzdłuż punktów bocznych portalu (punktów końcowych segmentów linii), o ile to zacieśnia lejek (AD).

algorytm

Oznacza to, że każdy ruch do przodu powinien przesuwać krawędzie lejka do wewnątrz, można to sprawdzić za pomocą iloczynu wektorów reprezentujących starą stronę i potencjalną nową stronę ( P × Q na obrazku poniżej; patrz także triarea2kod Mikko). Jeśli ruch do przodu w stronę nie dokręciłby ścieżki, nie aktualizujemy tej strony dla bieżącej iteracji portali (E).

poruszać się do wewnątrz

Innym przypadkiem, którym należy się zająć, jest degeneracja lejka do odcinka linii. Aby to uwzględnić, algorytm sprawdza, czy jedna ze stron znajduje się po „niewłaściwej” stronie, używając ponownie iloczynu krzyżowego, tym razem wektorów wykonanych przez wierzchołek lejka oraz odpowiednio punkty końcowe po prawej i lewej stronie ( R × S w zdjęcie poniżej).

zdegenerowany lejek

W takim przypadku wektor z wierzchołka lejka i prawidłowy boczny punkt końcowy jest dodawany do wygładzonej ścieżki ( R na zdjęciu powyżej), a algorytm jest ponownie uruchamiany z punktem końcowym jako nowym wierzchołkiem (FG), chyba że: oczywiście, jeśli jest to punkt bramkowy.

Eric
źródło
2
@Rolfcore Czy odpowiedź jest jasna? Jeśli nie, które części wymagają poprawy?
Eric
Myślę, że po prostu zapomniał przyjąć odpowiedź, ta jest bardzo dobra i powinna zostać poważnie oceniona ^^.
GameDeveloper
Może, tonly gotcha, jest to, że w ruchu F nie mówisz, że nie zaczynamy od zera, ponieważ istnieje szansa, że ​​ciasny róg skierowany na południe umożliwi ciasny lejek, więc musimy poczekać, aż boczne boki faktycznie zawiodą test i nie tylko jeden. Robimy to w G zamiast w F .. i tak dobre wyjaśnienie :)
GameDeveloper