Czy ktoś może zasugerować dokumenty lub algorytmy dotyczące obliczania najkrótszych ścieżek w przestrzeniach euklidesowych z niewypukłym wielokątem jako przeszkodą?
path-finding
aneuryzm
źródło
źródło
Odpowiedzi:
Najprostszym podejściem jest przekształcenie wielokątów wypukłych w wiele wielokątów wypukłych, a następnie wykonanie normalnej kolizji wypukłej i znalezienie ścieżki (za pomocą A * lub D * lub cokolwiek innego). Pierwszy proces jest często nazywany triangulacją w geometrii obliczeniowej i istnieje kilka typowych sposobów, aby to zrobić.
źródło
To może nie być dokładna odpowiedź na twoje pytanie, ale mogę zasugerować ci podejście do tego problemu.
W rzeczywistości twój problem to dwa problemy razem.
Drugi problem jest osadzony w pierwszym. W pierwszej kolejności mogę zalecić zrozumienie ślepego wyszukiwania. Oto bardzo prosta prezentacja na ten temat: Wyszukiwanie w ciemno
Jeśli czytasz dokument dotyczący budowania przestrzeni stanu, musisz wygenerować punkty stanu, które muszą być zgodne z prawem, co oznacza, że stany te mogą znajdować się na najkrótszej ścieżce, aby nie kolidowały z żadnymi obiektami w Twojej przestrzeni. Odtąd możesz kontynuować algorytmy kolizji euklidesowej. Po zbudowaniu przestrzeni stanów i drzewa wyszukiwania ograniczonego kolizjami możesz wybrać jeden z najkrótszych algorytmów ścieżki lub jeden z własnych lub zmodyfikowany hybrydowy.
źródło