Abstandsberechnung

XZ59

Hallo,

ich brauche Algorithemn zur Abstandsberechnung (NICHT Kollisionserkennung) um in einem virtuellen Raum (erzeugt aus 3d Scannerdaten) einen roboter fahren zu lassen und seine Bahn zu planen.

eine der Fragestellungen ist: welches ist der beste algorithmus um dies zu bewältigen, daher wäre es super, wenn ihr mir euch bekannte Algorithmen bzw. Links zu deren Bibliotheken schicken könnten.

Danke

Abstandsberechnung: Pythagoras. Geht halt einfach nicht viel anders. Beim Vergleichen von Abständen natürlich nur mit den Quadraten rechnen und nicht die Wurzel ziehen. Bei geschickter Raumunterteilung kannst du Abstände auch vorberechnen und zur Laufzeit nur noch schätzen.

Wegfindung: Es gibt eine Menge Algorithmen zur Wegfindung, zum Beispiel A*. Zu diesem Thema findest im Internet nicht wenig, für A* ist vor allem auch http://theory.stanford.edu/~amitp/GameProgramming/ zu empfehlen. Zunächst mal benötigst du eine sinnvolle Darstellung der möglichen Wege als Graph, denn praktisch jeder Algorithmus zur Wegfindung basiert auf Graphen. Du hast zum Beispiel die Möglichkeit, den Raum in ein 3D-Gitter zu unterteilen und die Mittelpunkte der Quader als Knoten zu verwenden. Alternativ kannst du auch beliebig fein aufgelöste Bounding Volumes um die Hindernisse legen und an den Eckpunkten mit zusätzlichem Sicherheitsabstand Knoten setzen.

XZ59

das eine Abstandsberechnung mit Pythagoras zwischen 2 Punkten im 3D geht is klar.

aber angenommen ich habe einen Punkt und eine gerade ... auch klar
ein Dreieck und einen Punkt
ein Dreieck und eine Gerade
ein Rechteck und ein Punkt
Rechteck, Gerade
Rechteck + Dreieck
AABB, OBB, Convexe Hülle etc

das sing geometrische Figuren/Körper mit denen ich arbeiten will/muss

Danke für den Hinweis mit A*, aber mir geht es nur um die Abstandsbrechnung, wollte es jedoch im größeren Rahmen erklären, damit jedem klar ist worum es geht.

Für die Probleme, die du aufzählst, gibt es allesamt fertige Algorithmen. Da würde ich mir keine Sekunde den Kopf darüber zerbrechen. Hast du nicht mal eine Suchmaschine deiner Wahl bemüht?
http://www.google.de/search?hs=V7p&hl=de&client=firefox-a&rls=org.mozilla%3Ade%3Aofficial&q=geometric+algorithms+distance&btnG=Suche&meta=
liefert schon ziemlich am Anfang etwas sehr brauchbares
http://softsurfer.com/algorithms.htm

XZ59

Vielen Dank, genau das habe ich gesucht, doch leider habe ich wohl zu speziell gesucht (nach OBB, AABB etc).

Vielen Dank für eure Antworten.

XZ59

Nachdem ich vergeblich nach ein paar Algorithmen gesucht habe hier nochmals die Frage:

ich brauch Algorithmen zu folgenden Abstandsbestimmungen (in 3D):

- Dreieck und Streck
- Dreieck und Dreieck
- Punkt und Rechteck
- Strecke und Rechteck
- Dreieck und Rechteck
- Rechteck und Rechteck

Vielen Dank
Paper, die die Algorithmen beschreiben sind auch sehr willkommen

Gast25250

XZ59 schrieb:

Nachdem ich vergeblich nach ein paar Algorithmen gesucht habe hier nochmals die Frage:

ich brauch Algorithmen zu folgenden Abstandsbestimmungen (in 3D):

- Dreieck und Streck
- Dreieck und Dreieck
- Punkt und Rechteck
- Strecke und Rechteck
- Dreieck und Rechteck
- Rechteck und Rechteck

Vielen Dank
Paper, die die Algorithmen beschreiben sind auch sehr willkommen

- Dreieck und Streck: Abstand aller drei Punkte mit Linie vergleichen
- Dreieck und Dreieck: Drei Punkte des einen mit Dreieck vergleichen. Dazu: Punkte auf die Ebene des Dreiecks projizieren (trivial) Baryzentrische Koordinaten berechnen (trivial) -> Wissen ob inside/outside. Wenn Outside, Abstand zwischen Kanten und Punkten berechnen. Wenn inside Abstand zwischen proj. und Punkten Berechnen.
- Punkt und Rechteck: analog zu oben, projektion...
- Strecke und Rechteck: kniffelig, Strecke zu Gerade machen, minimalen Abstand berechnen, d.h. Strecke-Ebene ableiten, Nullstelle bestimmen, voila
- Dreieck und Rechteck s.o.
- Rechteck und Rechteck s.o.