Jak obliczyć najkrótszą ścieżkę w środowiskach euklidesowych z wielokątami niewypukłymi?

10

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

Zauważ, że jeśli punkt początkowy, punkt końcowy lub inny wielokąt nie leży w przestrzeni między niewypukłym wielokątem a jego wypukłym kadłubem, możesz zastąpić niewypukły wielokąt złożonym kadłubem. Łatwo to zobaczyć, po prostu rysując niewypukły wielokąt i jego wypukły kadłub, a następnie rozważając, które najkrótsze ścieżki przechodzą przez różnicę.

— MSalters

3

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ć.

3

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.

Znajdowanie najkrótszych ścieżek
Znajdowanie kolizji

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.

— Gorki
źródło