Szukasz algorytmu lejka.
Tutaj jesteś prosty
http://digestingduck.blogspot.com.es/2010/03/simple-stupid-funnel-algorithm.html
Zasadniczo algorytm identyfikuje krawędzie jako portale i buduje lejek, który jest testowany względem wierzchołka krawędzi, aby sprawdzić, czy znajdują się w lejku, czy nie.
W kroku A lejek jest budowany z pozycją początkową, a portal przecina żółta linia.
W kroku B sprawdzany jest następny portal, górny wierzchołek znajduje się wewnątrz lejka, więc teraz przechodzi przez niego górna linia lejka. Ale dolny wierzchołek jest poza lejkiem, ponieważ czerwona linia znajduje się pod zieloną linią, więc dolna linia nie przejdzie przez nią, będzie nadal przechodzić przez dolny wierzchołek poprzedniego portalu.
Jak można sprawdzić, lejek będzie mniejszy i mniejszy, aż do kroku F, w którym nie można zbudować lejka, ponieważ czerwona linia stanowi zły lejek, więc górny wierzchołek jest wybierany jako nowy punkt początkowy, a nowy lejek byłby buduj, jeśli punktu końcowego nie ma w tej siatce.
Zdaj sobie sprawę, że ten rodzaj algorytmu pozwala również na proste rozwiązanie problemu z rozmiarem modelu, ponieważ możesz wziąć pod uwagę, że portale są mniejsze o 2x promień twojego modelu.