Problem :Algorithmus zur Suche in einem 3D-Feld

[Maik_8055db]

Hallo,

ich suche einen Algorithmus, (oder auch c/c++ quellcode) für folgendes Problem:

gegeben ist ein 3D-Raum dessen Punkte mit den Werten FALSE oder TRUE besetzt sind.
wie z.B.

bool raum[256][256][256];

für einen gegeben punkt X in diesem raum,
z.B X= Punkt(4,6,7) (-> nur Ganzzahlen!)
möchte ich nun einen Punkt Y in diesem Raum finden, der folgende Bedingungen erfüllt:

• der Punkt Y hat in diesem Raum den Wert TRUE
• es gibt keinen anderen Punkt der den Wert TRUE hat und näher am
  Punkt X liegt

Anders, ausgedrückt suche ich einen Algorithmus der alle Punkte im Umkreis von X absucht bis er einen Punkt findet der den Wert TRUE hat ,dabei aber immer Punkte die näher liegen, zuerst besucht.

PS: Eine überprüfung aller Punkte, mit nachträglicher Auswahl desjenigen mit geringster Entfernung fällt bei 256^3 Möglichkeiten natürlich aus!

[pumpkin_1768a9]

Moin

bool raum[256][256][256];

für einen gegeben punkt X in diesem raum,
z.B X= Punkt(4,6,7) (-> nur Ganzzahlen!)

also raum[4][6][7] = Wert von X ?

• es gibt keinen anderen Punkt der den Wert TRUE hat und näher
  am
  Punkt X liegt

Definier mal eine Abstandsfunktion. Wenn du „nur“ abs(deltax) + abs(deltay) + abs(deltaz) machts ist es einfach. Wenn du andere Funktionen benutzt wirds komplexer.

PS: Eine überprüfung aller Punkte, mit nachträglicher Auswahl
desjenigen mit geringster Entfernung fällt bei 256^3
Möglichkeiten natürlich aus!

Schliess doch schonmal alle false-Punkte aus der Suchliste aus. Oder, wenn die Daten gut geordenet sind, erzeug erstmal gröbere Raster und mach mit denen eine Vorselektion.

cu

[Maik_8055db]

Hallo pumpkin , danke für deine schnelle Antwort

also raum[4][6][7] = Wert von X ?

ja, genau.

Definier mal eine Abstandsfunktion.

abstand =Länge des Vektores zwischen den Punkt X und Punkt Y
-> wurzel(delta(x)^2+delta(y)^2+delta(z)^2)

Schliess doch schonmal alle false-Punkte aus der Suchliste
aus. Oder, wenn die Daten gut geordenet sind, erzeug erstmal
gröbere Raster und mach mit denen eine Vorselektion.

Wie sollte eine Vorselektion aussehen?
Alles was ich habe ist :

1. bool raum[256][256][256] mit unbekannter Verteilung der
   Wahrheitswerte
2. und den gegebenen Punkt X

Um false-Punkte auszuschliessen müsste ich sie aber erstmal kennen!
D.h ich müsste :

• ALLE Punkte abfragen
• diese in eine Liste packen
• die false-Werte löschen
• die Liste nach Abstand sotieren.

Das funktioniert theoretisch wunderbar, allerdings hätte die Liste 16.78 Millionen Einträge
-> extrem langsam, extrem hoher resourcenaufwand

[pumpkin_1768a9]

Moin

Definier mal eine Abstandsfunktion.

abstand =Länge des Vektores zwischen den Punkt X und Punkt Y
-> wurzel(delta(x)^2+delta(y)^2+delta(z)^2)

Iiiggt… die ist übel. Das kompliziert die Sache ein bisschen.

Wie sollte eine Vorselektion aussehen?
Alles was ich habe ist :

1. bool raum[256][256][256] mit unbekannter Verteilung der
   Wahrheitswerte

Naja, du wirst ja hoffentlich mehr als eine Suche durchführen, es lohnt sich also evtl ein bisschen „Vorarbeit“ zu leisten. Die muss ja nur 1x erbracht werden, alle weiteren Suchen können darauf aufbauen.

So eine spontan-Idee für eine Vorselektion:

bool raum2[256/Faktor][256/Faktor][256/Faktor]

(Faktor so um 4, evtl auch mehrere raum2-Felder mit unterschiedlichen Faktoren)

Jeder Punkt (X,Y,Z) in raum2 entspricht einem Raumbereich (Würfel) der Grösse Faktor x Faktor x Faktor um den Punkt (X x Faktor,Y x Faktor,Z x Faktor). Wenn in diesem Würfel ein true-Punkt vorkommt ist raum2 auch true, sonst false.

Wenn du auf Koordinaten etwas mit raum2 = false triffst kann du dir den Würfel in raum schonmal schenken.

Ausserdem kannst du das ganze ein bisschen anders speichern. Kodier die bool-Werte in int’s oder long’s rein. Du könntest dann (bei long) z.B. 64 bool-werte in einem Befehl testen (wert == 0 => alle false). Testen eines einzelnen bool-werte dauert auch nicht so viel länger (1x AND-verknüpfen und mit 0 vergleichen). (Ob long oder int schneller wären hängt von der CPU ab. Ich schätz mal beim P4 ist int schneller, beim Athlon64 long)

Das würde ziemlich sicher was bringen, da es den RAM erheblich entlastet. (Von ±67MB runter auf ±2MB) Damit wird dann die Cache-hit-rate höher, was bei Athlon und P4 unheimlich hilft.

Bei der Suche selbst würde ich vom dem gegebenen Punkt ausgehen und Würfel um den Punkt herrum „abgrasen“. Wenn man den ersten findet => erste Distanz berrechen. Danach darf man aber nicht sofort aufhören, da es (bei der Distanz-funktion) immernoch Punkte geben kann die noch näher dran sind. Man müsste dann solange weitermachen bis alle Punkte, die näher als der erste gefunde liegen, mit durchsucht wurden. Dabei durchsucht man allerdings auch „unnütze“ Punkte, muss also nachher genauer sortieren.

Bei der Suche kann man mit raum2 und long-koodierung bestimmt ordentliche Zeiten rausschlagen. Die 2 Vorarbeiten lohnen sich aber nur wenn mehrere Suchen durchgeführt werden sollen.

cu

[Maik_8055db]

-> wurzel(delta(x)^2+delta(y)^2+delta(z)^2)

Iiiggt… die ist übel. Das kompliziert die Sache ein
bisschen.

Nunja, das lässt sich nun mal nicht ändern

Wie sollte eine Vorselektion aussehen?
Alles was ich habe ist :

1. bool raum[256][256][256] mit unbekannter Verteilung der
   Wahrheitswerte

Naja, du wirst ja hoffentlich mehr als eine Suche durchführen,

Ja, einige 10000x

es lohnt sich also evtl ein bisschen „Vorarbeit“ zu leisten.
Die muss ja nur 1x erbracht werden, alle weiteren Suchen
können darauf aufbauen.

So eine spontan-Idee für eine Vorselektion:
bool raum2[256/Faktor][256/Faktor][256/Faktor]

Coole Idee! Das könnte sich lohnen.

…Ich schätz mal beim P4 ist int schneller, beim Athlon64 long)…

…Das würde ziemlich sicher was bringen, da es den RAM erheblich
entlastet. (Von ±67MB runter auf ±2MB) Damit wird dann die
Cache-hit-rate höher, was bei Athlon und P4 unheimlich hilft.

Gibts im Nezt ne Seite wo man sowas mal genauer nachlesen könnte?

Bei der Suche selbst würde ich vom dem gegebenen Punkt
ausgehen und Würfel um den Punkt herrum „abgrasen“. Wenn man
den ersten findet => erste Distanz berrechen. Danach darf
man aber nicht sofort aufhören, da es (bei der
Distanz-funktion) immernoch Punkte geben kann die noch näher
dran sind. Man müsste dann solange weitermachen bis alle
Punkte, die näher als der erste gefunde liegen, mit durchsucht
wurden. Dabei durchsucht man allerdings auch „unnütze“ Punkte,
muss also nachher genauer sortieren.

Ja, so werd ichs machen. Danke für deine Hilfe!
Was meinst du mit unnütze Punkte?

[Peter_TOO]

Hallo Fragewurm,

ich suche einen Algorithmus, (oder auch c/c++ quellcode) für
folgendes Problem:

gegeben ist ein 3D-Raum dessen Punkte mit den Werten FALSE
oder TRUE besetzt sind.
wie z.B.

bool raum[256][256][256];

Wieso kannst du die TRUE-Punkte (oder die FALSE-Punkte, je nachdem was weniger häuffig auftritt) nicht in einer verketteten Liste speichern ?
Im Prinzip kannst du eine 3fach doppelt verkettete Liste machen und die Elemente noch jeweils nach der jeweiligen Achse sortieren. Dadurch ist der nächste Punkt einer der 6 Nachbarn des Elements.

MfG Peter(TOO)

[Maik_8055db]

Dadurch ist der nächste Punkt einer der 6
Nachbarn des Elements.

Funktioniert so nicht, da ich nicht nur in den 3 Hauptrichtungen suchen will.

[Peter_TOO]

Hallo fragewurm,

Dadurch ist der nächste Punkt einer der 6
Nachbarn des Elements.

Funktioniert so nicht, da ich nicht nur in den 3
Hauptrichtungen suchen will.

Kannst du mir das mal erklären ??

MfG Peter(TOO)

[pumpkin_1768a9]

Moin

-> wurzel(delta(x)^2+delta(y)^2+delta(z)^2)

Nunja, das lässt sich nun mal nicht ändern

Lass beim suchen wenigestens die Wurzel weg, die zu Berechnen dauert ewig im Vergleich zu ^2 und Additionen. (Das Resultat ist eh das gleiche, die Reihenfolge bleibt ja erhalten. Nur eben vor der Ausgabe der minimal-Distanz die Wurzel zeihen)

Gibts im Nezt ne Seite wo man sowas mal genauer nachlesen
könnte?

So spontan fällt mir keine ein, das ist ja auch eingentlich realitv banal. nur int raum[256/32][256][256] und ein paar Zugriff-funktionen…

Was meinst du mit unnütze Punkte?

Eigentlich erzeugt deine Distanzfunktion eine „Kugel“ um den gegebenen Punkt. Man müssste also nur solange die Kugel vergrössern bis man auf einen true-Punkt stöst. Nun kann man aber schlecht kugelformen rund um einen Punkt fehlerfrei durchsuchen. Deshalb der Vorschlag mit dem Würfel.

Wenn man nun einen ersten true-Punkt in dem Würfel hat kennt man ja eigentlich schon eine Kugel in der alle möglichen Punkte drinliegen. Trotzdem muss man den Würfel so weit vergrössern bis diese erste „Näherungs“-Kugel komplett im Würfel drin ist (Weil man sonst u.U. den falschen Punkt erwischt). Dabei gibts an den Ecken reichlich Verschnitt. Die Punkte sind eigentlich unnütz und müssen nicht durchsucht werden. ABER den Durchsuchungsraum über deine Distanzfunktion einzugrenzen kostete viel mehr Zeit als die zusätzlichen Tests der unnützen Punkte und das spätere Filtern des Resultats.

cu

[Maik_8055db]

Wenn ich dich richtig verstanden habe, stellt jede Node aus der Liste einen „1“ Punkt im Raum dar.

Jede Node hat 6 Zeiger.
Zeiger 1 zeigt in positiver X Richtung zur nächsten „1“ Node
Zeiger 2 zeigt in positiver Y Richtung zur nächsten „1“ Node
Zeiger 3 zeigt in positiver Z Richtung zur nächsten „1“ Node
Zeiger 4-6 zeigen analog zur vorherigen Node.

Problem : Ich möchte auch schräge Verbindungen mit einbeziehen

Beispiel :

gegebener Raum :

1000000001
0010000000
1000000000

Verkettung mit deiner Liste :

1--------1
| 1?
1

Was machst du mit der einzelnen „1“?

Maik

[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]

[Moriarty_3ffffd]

Octree
Hallo,

hier fällt mir die Octree-Datenstruktur ein. Unterteile den Gesamtraum in 8 gleichgroße Sub-Würfel, jeden dieser Subwürfel wieder in 8 gleichgroße Subsub-Würfel, solange, bis die Subwürfel gerade die Größe 1 haben. Jeder Würfel zeigt entweder auf a) Subwürfel, b) leer oder c) auf einen Dateninhalt. So erhält man einen Baum, der sich verzweigt, und dessen Blätter die Würfelchen der Größe 1 sind.

Zum Durchsuchen der Struktur fängst Du bei den Blättern an, bis Du was findest, wenn nicht, gehst du eine Ebene höher, und dann rekursiv wieder nach unten in die Nachbarknoten.
Wenn Du die Würfel alle geschickt in einer Liste sortierst, kannst Du den Suchaufwand noch veringern.

Alles in allem nicht trivial, aber auch nicht so schwierig. Das hängt davon ab, wie weit Deine Programmierkenntnisse reichen. Vielleicht schilderst Du mal das Problem „an sich“ ?

Gruß
Moriarty

[Wizard_of_War]

Ungefähr so könnte es gehen:
Das Programm geht zuerst einen Schritt in alle Richtungen nach unten, und fängt dann bei z an hochzuzählen bis es einen schritt weiter ist als das festgelegte Feld von dem aus du losgehst.
Dann geht y hoch, dann x,
Anschliessend geht das Programm noch einen schritt runter und zählt auch noch ein feld weiter hoch usw.
Ich hoffe es ist verständlich.

Punkt a,b,c, ist dein Punkt den du festlegst.

boolean gefunden = false;
 int a = 5, b = 5, c = 5;
 int i1=1;
 while (!gefunden){
 for(int x=a-i1; xb-i1)&&(y**a-i1)&&(x  
Jetzt musst du nur noch die Abbruchbedingungen festlegen.  
Wichtig: Punkte die an Ecken gefunden werden sind eventuell weiter weg als Punkte, die noch nicht gefunden wurden.  
Von daher ist es etwas schwierig die Abbruchbedingungen zu formulieren.  
Ach ja nochwas, du musst noch festlegen wie groß i1 werden darf damit du innerhalb des 256er Feldes bleibst...  
  
Ich hoffe es hilft dir, Gruß   
Wizard of War**  

[bolo_6f7a6a]

Ist das Problem noch aktuell? Wie hast Du es geloest?

Es handelt sich hier um ein klassisches kuerzeste Wege Problem.

Kuerzeste Wege Algorithmus z.B. von Dijkstra verwenden (Asymtotischer Rechenzeitaufwand O(n^2), in Deinem Beispiel n=256^3) und den Raum als gerichteten Graphen darstellen. Jeder Knoten des Graphen ist ein Punkt im Raum. Die Kanten entsprechen den Verbindungen zu den direkten Nachbarpunkten im Raum (zwischen einem im Wuerfel zueinander benachbarten Knotenpaar existieren immer zwei zueinander entgegengesetzt gerichtete Kanten), die Gewichte ergeben sich aus den Abstaenden zwischen den Punkten im Raum (schon diskutiert).

[pumpkin_1768a9]

Moin

Ist das Problem noch aktuell? Wie hast Du es geloest?

Weiss ich nicht, frag den Ursprungsposter.

cu

[Yelve_Yakut]

• der Punkt Y hat in diesem Raum den Wert TRUE
• es gibt keinen anderen Punkt der den Wert TRUE hat und näher
  am
  Punkt X liegt

Anders, ausgedrückt suche ich einen Algorithmus der alle
Punkte im Umkreis von X absucht bis er einen Punkt findet der
den Wert TRUE hat ,dabei aber immer Punkte die näher liegen,
zuerst besucht.

Also wenn sich der Raum oft verändert dann: BFS-Traversierung um den Knoten X

Wenn sich der Raum nicht bzw. wenig ändert und genug Speicher zur Verfügung steht dann lohnt es sich vielleicht alle Lösungen zu finden: Generiere einen Untergraph des Raumes der nur die True-Elemente enthält. Zu jedem Knoten aus dem Raum suchst du dann den nächsten Nachbarn und setzt ne Kante zu ihm den du mit der Entfernung Markierst. Mag ineffizient erscheinen aber wenn sich dein Raum nur selten und wenig ändert kann sich das lohnen, da du in diesen Graphen neue True-Elemente (falls bekannt!) relativ leicht hinzufügen kannst.

Gruss, Yelve

[Yelve_Yakut]

Ups. Sorry hab voreilig gepostet. Der klassische BFS kommt natürlich nicht in frage.

[Maik_8055db]

Das Problem ist gelöst, hab mich grösstenteils an Lösung von pumpkin gehalten. Dijkstra wäre deutlich langsamer.

Trotzdem danke
Maik

[bolo_6f7a6a]

Das Problem ist gelöst, hab mich grösstenteils an Lösung von
pumpkin gehalten. Dijkstra wäre deutlich langsamer.

Trotzdem danke
Maik

Wenn dem so waere, ist es wohl nobelpreisverdaechtigt. Poste mal Deine Loesung.

Hat man fuer Dijkstras kuerzesten-Wege-Algorithmus fuer einen positiv gewichteten Graphen G(V,E), O(|V|^2) eigentlich die worst-case-Effizienz nachgewiesen?