Algorytm sprawdzający, czy dwa woksele są ze sobą połączone

Szukam dobrych algorytmów dla następującego problemu: Biorąc pod uwagę siatkę 3D wokseli (które mogą być puste lub wypełnione), jeśli wybiorę dwa niesąsiadujące woksele, chcę wiedzieć, czy są one połączone ze sobą przez inne woksele.

Na przykład (aby zilustrować sytuację w 2D), gdzie # to wypełniony kwadrat:

  1 2 3
a # # #
b # #
c # # #

Jeśli wybiorę a3 i c3, chcę jak najszybciej ustalić, czy są one połączone; jeśli istnieje ścieżka między a3 i c3 przez wypełnione piksele. (Rzeczywista sytuacja jest oczywiście w siatce wokseli 3D).

Patrzyłem na algorytmy wypełniania zalewów i algorytmy wyszukiwania ścieżek, ale nie jestem pewien, który wybrać. Oba wykonują niepotrzebną pracę: funkcja Flood próbuje wypełnić wszystkie woksele, ale nie jest to konieczne. Algorytmy ustalania ścieżki zwykle dotyczą znalezienia najkrótszej ścieżki, co również nie jest konieczne. Muszę tylko wiedzieć, czy tam jest ścieżka.

Jakiego algorytmu powinienem używać?

Edycja: na podstawie komentarzy, myślę, że powinienem dodać: zawartość wokseli nie jest z góry znana, a także algorytm jest potrzebny do wykrycia, czy usunięcie (opróżnienie) woksela spowodowałoby pęknięcie grupy wokseli na dwie lub więcej mniejszych grup.

* Działałoby dobrze. Szukanie ścieżki jest tym, czego chcesz, znalezienie najkrótszej ścieżki jest równie szybkie (lub szybsze) niż znalezienie jakiejkolwiek ścieżki. W tej sytuacji A * jest najbardziej odpowiedni, biorąc pod uwagę punkt początkowy i końcowy. oznacza to, że masz dodatkową heurystykę, aby przyspieszyć wyszukiwanie.

W przypadku A * zazwyczaj pierwsza znaleziona ścieżka jest najkrótsza, więc nie wykonuje dodatkowej pracy po znalezieniu ścieżki.

Dla niektórych optymalizacji sprawdź moją odpowiedź tutaj .

Jeśli jesteś przygotowany na wstępne przetwarzanie i zjedzenie kosztów przechowywania, wówczas dzielenie wokseli na połączone grupy w czasie kompilacji daje oczywistą odpowiedź na pytanie „czy w ogóle istnieje ścieżka”. Istnieje ścieżka między dwoma wokselami, jeśli należą do tej samej grupy. Problem polega na tym, że musisz gdzieś przechowywać informacje o grupie, a to zależy od układu danych. Jeśli przechowujesz prostą listę, możesz po prostu podzielić ją na wiele list, po jednej dla każdej grupy powiązanej przestrzennie. Jeśli organizujesz się w jakimś BVH, prawdopodobnie możesz uzyskać dość dobrą wydajność, jeśli możesz powiedzieć, że „wszystkie woksele w tym węźle i poniżej należą do grupy X”.

Alternatywnie, możesz zrobić przestrzenne wstępne partycjonowanie i przechowywać mniejszy zestaw wokseli „hub” dla każdej połączonej grupy. Następnie możesz znaleźć ścieżkę ze źródła i wokseli docelowych do najbliższego woksela piasty, który powinien być znacznie krótszy / tańszy w obliczeniu ścieżki. Jeśli możesz znaleźć ścieżkę od woksela do woksela hub, wtedy woksel jest częścią grupy wokseli hub. Dzięki inteligentnemu wyborowi tych wokseli piasty możesz zminimalizować liczbę przejść ścieżek. Np. Kula może mieć w środku tylko jeden woksel piasty, ale długa cienka grupa może mieć woksel piasty co X wokseli na swojej długości. Jeśli woksele źródłowe i docelowe znajdują się na dowolnym końcu długości, muszą znaleźć się w najwyżej X wokselach, aby znaleźć piastę, i chociaż może istnieć ogromna liczba wokseli między początkiem a końcem długości,

Wszystko zależy od tego, jak patologiczne są twoje grupy wokselowe: jeśli spodziewasz się dużej liczby małych, niepowiązanych grup, wzrost kosztów przechowywania będzie znacznie przewyższał wydajność samego wyszukiwania ścieżek. Jeśli oczekujesz stosunkowo niewielu połączonych grup, ale o dziwnych topologiach, wówczas naiwne wyszukiwanie ścieżek może być niezwykle kosztowne, a koszt przechowywania i minimalne wyszukiwanie ścieżek jest znacznie tańszą opcją.

Nie znam się dobrze na wokselach, ale wyobrażam sobie, że można uzyskać całkiem niezłą wydajność dzięki zastosowaniu algorytmu najlepszego wyszukiwania, takiego jak A *. Problem z użyciem A * w tym przypadku polega na tym, że heurystyczny, którego normalnie by się użył, ma na celu ustalenie priorytetu znalezienia najkrótszej ścieżki, a nie tylko „dowolnej ścieżki” tak szybko, jak to możliwe.

Możesz mieć trochę szczęścia, używając alternatywnej heurystyki, która rozszerza mniej węzłów, takich jak

f (p) = g (p) + w (p) * h (p)

gdzie w> = 1. zmniejszasz wartość „w” im bardziej zbliżasz się do celu, tym samym nadając wyższy priorytet kosztowi ścieżki „g”, im bardziej zbliżasz się do woksela, którego szukasz.

Mam nadzieję, że to pomoże!