Pracując z algorytmem lejka pokazanym na kaczce fermentacyjnej nie jestem pewien, jak działa wykrywanie lejka.
Czy ktoś może mi wyjaśnić tę metodę w jasny sposób lub zasugerować alternatywny sposób wykrywania lejka i jeśli strony lejka pokrywają się?
Odpowiedzi:
Algorytm zaczyna się od znalezionej wcześniej ścieżki, w tym przypadku listy trójkątów:
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.
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).
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).
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).
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.