Abstand zwischen geom. Körpern < Numerik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:56 Di 15.04.2014 | | Autor: | MrMuffin |
Hallo zusammen,
ich versuche derzeit einen "rechengünstigen" Algorithmus in Matlab zu implementieren, der das folgende machen soll:
Gegeben seien zwei beliebige Figuren in [mm] \IR^3, [/mm] z.B. ein Kaktus und ein Stift. Wie kann ich möglichst einfach den Abstand beider Körper zu einander bestimmen?
Was möglich wäre, wäre es die Figuren durch Punktewolken zu repräsentieren und dann durch eine for-Schleife nach dem geringsten euklidischen Abstand zu suchen. Das kann allerdings in sehr großer Rechenzeit ausarten.
Mir stellt sich da zwangsläufig die Frage, wie Programme wie AutoCAD oder CATIA das bewerkstelligen? Dort kann man die kompliziertesten Geometrien konstruieren und dennoch ist das Programm in der Lage instantan den kürzesten Abstand zwischen beliebigen Körpern anzugeben.
Hat jemand eine Idee, wie ich mein Problem anpacken könnte?
Oder kann mir jemand sagen, wie solche "Abstandsprobleme" in der Fachwelt bezeichnet werden, sodass ich mich evtl einlesen kann?
Vielen Dank!
|
|
| |
|
Hallo,
das ist eine ziemlich komplizierte und technische Frage. CAD-Systeme wie die von dir angesprochenen speichern ja alle Objekte letztendlich irgendwie als Vektoren. Runde Linien bzw. Flächen werden durch Interpolationspolynome, sog. Splines bzw. Nurbs realisiert, von denen man sicherlich in jedem Punkt den Normalenvektor kennt (also: die Software 'kennt ihn'). Von da bis zu einem Algorithmus zur Abstandsberechnung zwischen zwei im Prinzip beliebigen Objekten ist es nicht mehr sehr weit, wenn ich auch keine genaueren Details kenne.
Ob man das in Matlab einfach so umsetzen kann, da habe ich so meine Zweifel, aber auch das kenne ich nicht so gut.
Von daher stelle ich mal auf 'teilweise beantwortet'.
Gruß, Diophant
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:41 Di 15.04.2014 | | Autor: | DieAcht |
Hallo MrMuffin,
> Hallo zusammen,
> ich versuche derzeit einen "rechengünstigen" Algorithmus
> in Matlab zu implementieren, der das folgende machen soll:
>
> Gegeben seien zwei beliebige Figuren in [mm]\IR^3,[/mm] z.B. ein
> Kaktus und ein Stift. Wie kann ich möglichst einfach den
> Abstand beider Körper zu einander bestimmen?
>
> Was möglich wäre, wäre es die Figuren durch Punktewolken
> zu repräsentieren und dann durch eine for-Schleife nach
> dem geringsten euklidischen Abstand zu suchen. Das kann
> allerdings in sehr großer Rechenzeit ausarten.
Das ist im Grunde die least squares Methode.
> Mir stellt sich da zwangsläufig die Frage, wie Programme
> wie AutoCAD oder CATIA das bewerkstelligen? Dort kann man
> die kompliziertesten Geometrien konstruieren und dennoch
> ist das Programm in der Lage instantan den kürzesten
> Abstand zwischen beliebigen Körpern anzugeben.
>
> Hat jemand eine Idee, wie ich mein Problem anpacken
> könnte?
Eine Anwendung von least squares wäre das Gauß-Newton-
Verfahren, wobei das auch sehr teuer wird. Ich denke,
dass man mit Levenberg-Marquardt gut fährt, wobei die
Konvergenz sogar lokal quadratisch ist.
Etwas wirklich "schnelleres" fällt mir gerade nicht ein.
> Oder kann mir jemand sagen, wie solche "Abstandsprobleme"
> in der Fachwelt bezeichnet werden, sodass ich mich evtl
> einlesen kann?
Das sind im Grunde genau diese drei Algorithmen, die in
gewisser Weise zusammenhängen. Soweit ich mich erinnere
sind die Wikipedia-Artikel dazu nicht schlecht.
Viele Algorithmen sind auch in Matlab schon implementiert,
sodass du das nicht selbst schreiben musst. Ansonsten gibt
es diese auch bestimmt alle im Netz, wobei die Algorithmen
nicht wirklich schwierig zu implementieren sind.
> Vielen Dank!
Viel Glück!
edit: Das Thema gehört auch eher in die Numerik. 
Gruß
DieAcht
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:07 Di 15.04.2014 | | Autor: | MrMuffin |
Vielen Dank Diophant, vielen Dank DieAcht!
Ich werde mich sowohl bezüglich der Interpolationspolynome als auch des Levenberg-Marquardt-Algorithmus schlau machen!
@Die Acht:
Ich dachte mir zwar, dass es in die Numerik gehört, allerdings hatte ich die leise Hoffnung, dass man derartige Probleme evtl geometrisch leichter in den Griff bekommt :P
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:15 Di 15.04.2014 | | Autor: | Diophant |
Hallo nochmal,
> Ich dachte mir zwar, dass es in die Numerik gehört,
> allerdings hatte ich die leise Hoffnung, dass man derartige
> Probleme evtl geometrisch leichter in den Griff bekommt :P
das ist ja auch eine berechtigte und interessante Frage. Letztendlich sind Computer halt dumme Maschinen, die insbesondere niemals in der Lage sein werden, einen kontinuierlichen Vorgang bzw. ein Zahlenkontinuum als solchen/solches zu behandeln. Wenn also nur eine Zeichnung in AutoCAD auf dem Bildschirm dargestellt wird, dann ist das Numerik pur. 
Gruß, Diophant
|
|
|
|
