www.vorhilfe.de
- Förderverein -
Der Förderverein.

Gemeinnütziger Verein zur Finanzierung des Projekts Vorhilfe.de.
Hallo Gast!einloggen | registrieren ]
Startseite · Mitglieder · Impressum
Forenbaum
^ Forenbaum
Status VH e.V.
  Status Vereinsforum

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Suchen
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Uni-Numerik" - Abstand zwischen geom. Körpern
Abstand zwischen geom. Körpern < Numerik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Uni-Numerik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Abstand zwischen geom. Körpern: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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!

        
Bezug
Abstand zwischen geom. Körpern: Antwort
Status: (Antwort) fertig Status 
Datum: 11:09 Di 15.04.2014
Autor: Diophant

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

Bezug
        
Bezug
Abstand zwischen geom. Körpern: Antwort
Status: (Antwort) fertig Status 
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

Bezug
        
Bezug
Abstand zwischen geom. Körpern: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
                
Bezug
Abstand zwischen geom. Körpern: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Uni-Numerik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
ev.vorhilfe.de
[ Startseite | Mitglieder | Impressum ]