Ich suche nach guten Algorithmen für das folgende Problem: Wenn ich bei einem 3D-Raster von Voxeln (die entweder leer oder gefüllt sein können) zwei nicht benachbarte Voxel auswähle, möchte ich wissen, ob sie durch miteinander verbunden sind andere Voxel.
Zum Beispiel (um die Situation in 2D zu veranschaulichen), wobei # ein gefülltes Quadrat ist:
1 2 3
a # # #
b # #
c # # #Wenn ich a3 und c3 auswähle, möchte ich so schnell wie möglich feststellen, ob sie verbunden sind. wenn es einen Pfad zwischen a3 und c3 durch gefüllte Pixel gibt. (Die reale Situation ist natürlich in einem 3D-Voxelgitter.)
Ich habe mir Floodfill-Algorithmen und Pfadfindungsalgorithmen angesehen, bin mir aber nicht sicher, welche ich wählen soll. Beide erledigen unnötige Arbeit: Flood Fill versucht, alle Voxel zu füllen, dies ist jedoch nicht erforderlich. Pfadfindungsalgorithmen befassen sich normalerweise mit dem Finden des kürzesten Pfades, was ebenfalls nicht erforderlich ist. Ich muss nur wissen , ob es ist ein Weg.
Welchen Algorithmus soll ich verwenden?
Bearbeiten: Basierend auf den Kommentaren sollte ich Folgendes hinzufügen: Der Inhalt der Voxel ist nicht im Voraus bekannt, und der Algorithmus wird benötigt, um zu erkennen, ob das Entfernen (Entleeren) eines Voxels dazu führen würde, dass die Gruppe der Voxel bricht in zwei oder mehr kleinere Gruppen.
quelle
c3->c2->b2->a2->a3?Antworten:
Ein * würde gut funktionieren. Das Finden von Pfaden ist das, was Sie wollen. Das Finden des kürzesten Pfades ist genauso schnell (oder schneller) wie das Finden eines Pfades überhaupt. In dieser Situation ist A * wahrscheinlich am besten geeignet, wenn Sie einen Start- und einen Endpunkt haben. Dies bedeutet, dass Sie die zusätzliche Heuristik haben, um die Suche zu beschleunigen.
Bei A * ist normalerweise der erste Pfad, den Sie finden, der kürzeste, sodass keine zusätzliche Arbeit geleistet wird, nachdem bereits ein Pfad gefunden wurde.
Weitere Optimierungen finden Sie in meiner Antwort hier .
quelle
Wenn Sie bereit sind, eine Vorverarbeitung durchzuführen und die Speicherkosten zu verbrauchen, gibt die Partitionierung von Voxeln in verbundene Gruppen zur Erstellungszeit eine offensichtliche Antwort auf "Gibt es überhaupt einen Pfad". Es gibt einen Pfad zwischen zwei Voxeln, wenn sie sich in derselben Gruppe befinden. Das Problem dabei ist natürlich, dass Sie Gruppeninformationen irgendwo speichern müssen, und das hängt von Ihrem Datenlayout ab. Wenn Sie eine einfache Liste speichern, können Sie diese einfach in mehrere Listen aufteilen, eine für jede räumlich verbundene Gruppe. Wenn Sie in einer Art BVH organisieren, können Sie wahrscheinlich einigermaßen gute Wirkungsgrade erzielen, wenn Sie sagen können, dass "alle Voxel in diesem Knoten und darunter zur Gruppe X gehören".
Alternativ können Sie eine räumliche Vorpartitionierung durchführen und für jede verbundene Gruppe einen kleineren Satz von Hub-Voxeln speichern. Dann können Sie den Pfad von Ihren Quell- und Ziel-Voxeln zum nächstgelegenen Hub-Voxel finden, was für die Berechnung des Pfads viel kürzer / billiger sein sollte. Wenn Sie einen Pfad von einem Voxel zu einem Hub-Voxel finden, ist das Voxel Teil der Gruppe des Hub-Voxels. Mit der intelligenten Auswahl dieser Hub-Voxel können Sie die Anzahl der Pfadüberquerungen minimieren. Beispielsweise könnte eine Kugel nur ein Nabenvoxel in ihrer Mitte haben, aber eine lange dünne Gruppe könnte alle X Voxel entlang ihrer Länge ein Nabenvoxel haben. Wenn sich Ihre Quell- und Zielvoxel an einem Ende der Länge befinden, müssen sie höchstens X Voxel verwenden, um einen Hub zu finden, und obwohl sich zwischen dem Anfang und dem Ende der Länge möglicherweise eine große Anzahl von Voxeln befindet,
Es hängt alles davon ab, wie pathologisch Ihre Voxelgruppen sind: Wenn Sie eine große Anzahl kleiner, nicht verbundener Gruppen erwarten, wird der Anstieg der Speicherkosten den Leistungseinbruch der Pfadfindung massiv überwiegen. Wenn Sie relativ wenige verbundene Gruppen mit ungeraden Topologien erwarten, ist die naive Pfadfindung möglicherweise sehr teuer, und die Speicherkosten und die minimale Pfadfindung sind eine viel billigere Option.
quelle
Ich bin mit Voxeln nicht sehr vertraut, aber ich würde mir vorstellen, dass Sie mit einem Best-First-Suchalgorithmus wie A * eine recht gute Leistung erzielen können. Das Problem bei der Verwendung von A * in diesem Fall besteht darin, dass die normalerweise verwendete Heuristik darauf ausgelegt ist, das Finden des kürzesten Pfades und nicht nur eines beliebigen Pfads so schnell wie möglich zu priorisieren.
Möglicherweise haben Sie etwas Glück, wenn Sie eine alternative Heuristik verwenden, die weniger Knoten erweitert, z
f (p) = g (p) + w (p) · h (p)
Dabei ist w> = 1. Sie verringern den Wert von 'w', je näher Sie dem Ziel kommen, und geben den Pfadkosten 'g' eine höhere Priorität, je näher Sie dem gesuchten Voxel kommen.
Ich hoffe das hilft!
quelle