Offene Fragen: Quaderschnitte
Released by matroid on Mo. 04. November 2002 18:24:26 [Statistics]
Written by matroid - 3429 x read [Outline] Printable version Printer-friendly version -  Choose language   
Mathematik

\(\begingroup\)\(\newcommand{\IX}{\mathbb{X}} \newcommand{\IW}{\mathbb{M}} \newcommand{\politician}[1]{\text{Ich habe die Frage nicht verstanden. #1}} \newcommand{\ba}{\begin{aligned}} \newcommand{\ea}{\end{aligned}} \newcommand{\bpm}{\begin{pmatrix}} \newcommand{\epm}{\end{pmatrix}} \newcommand{\bc}{\begin{cases}} \newcommand{\ec}{\end{cases}} \newcommand{\on}{\operatorname} \newcommand{\ds}{\displaystyle}\) 2 Quader im Raum  
Gegeben sind zwei Quader im Raum, in allgemeiner Lage.

Gesucht ist ein Verfahren, mit dem bestimmt werden kann, ob diese beiden Quader sich schneiden oder nicht.

Lösungsvorschläge sind erwünscht, insbesondere solche, das Problem auf effiziente Art lösen.


Die Frage richtet sich an diejenigen unter Euch, die derzeit nicht im Erstemesterstreß versinken.
Zu diesem Thema gab es bereits eine Diskussion im Forum, aber diese noch ohne Ergebnisse.

Viel Spaß beim Tüfteln
wünscht Matroid
der auf gute Vorschläge hofft.

\(\endgroup\)
Get link to this article Get link to this article  Printable version Printer-friendly version -  Choose language     Kommentare zeigen Comments  
pdfFür diesen Artikel gibt es keine pdf-Datei


Arbeitsgruppe Alexandria Dieser Artikel ist im Verzeichnis der Arbeitsgruppe Alexandria eingetragen:
: Mathematik :: Angewandte Mathematik :: Programmierung :: Quaderschnitte :: Sonstige Mathematik :
Quaderschnitte [von matroid]  
 Gegeben sind zwei Quader im Raum, in allgemeiner Lage. Gesucht ist ein Verfahren, mit dem bestimmt werden kann, ob diese beiden Quader sich schneiden oder nicht. Lösungsvorschläge sind erwünscht, insbesondere solche, das Problem auf effiziente Art lösen.
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
 
Aufrufzähler 3429
 
Aufrufstatistik des Artikels
Insgesamt 562 externe Seitenaufrufe zwischen 2012.01 und 2022.06 [Anzeigen]
DomainAnzahlProz
https://google.at20.4%0.4 %
https://google.com386.8%6.8 %
https://google.de13624.2%24.2 %
https://matheplanet.com20.4%0.4 %
http://google.de35162.5%62.5 %
http://int.search.tb.ask.com91.6%1.6 %
http://google.it50.9%0.9 %
https://www.startpage.com30.5%0.5 %
http://google.at30.5%0.5 %
https://www.bing.com30.5%0.5 %
http://search.conduit.com10.2%0.2 %
https://duckduckgo.com10.2%0.2 %
http://suche.web.de10.2%0.2 %
http://google.com20.4%0.4 %
http://google.ch10.2%0.2 %
http://images.google.de10.2%0.2 %
https://startpage.com10.2%0.2 %
http://suche.t-online.de10.2%0.2 %
http://de.ask.com10.2%0.2 %

Häufige Aufrufer in früheren Monaten
Insgesamt 525 häufige Aufrufer [Anzeigen]
DatumAufrufer-URL
2020-2022 (118x)https://google.de/
2013-2018 (99x)http://google.de/url?sa=t&rct=j&q=
2012-2013 (40x)http://google.de/url?sa=t&rct=j&q=schnittvolumen zweier quader
2020-2022 (31x)https://google.com/
201211-11 (22x)http://google.de/url?sa=t&rct=j&q=zylinder quader schnitt
201405-05 (20x)http://google.de/url?sa=t&rct=j&q=durchschnitt von quadern wieder quader
202103-06 (17x)https://google.de
201205-05 (16x)http://google.de/url?sa=t&rct=j&q=zwei quader schneiden sich im raum wenn
201201-01 (14x)http://google.de/url?sa=t&rct=j&q=testen ob quader sich überlappen
201207-07 (14x)http://google.de/url?sa=t&rct=j&q=schnittmenge zweier quader berechnen
201203-03 (12x)http://google.de/url?sa=t&source=web&cd=2&ved=0CCwQFjAB
201303-03 (11x)http://google.de/url?sa=t&rct=j&q=kugel quader schnitte
201307-07 (11x)http://google.de/url?sa=t&rct=j&q=schnittmenge zwei quader
201210-10 (10x)http://google.de/url?sa=t&rct=j&q=zwei quader im raum schneiden
201208-08 (10x)http://google.de/url?sa=t&rct=j&q=schnittpunkt quader quader
201306-06 (9x)http://google.de/url?sa=t&rct=j&q=schnittfläche von zwei quadern berechnen
201202-02 (9x)http://google.de/url?sa=t&rct=j&q=vektorrechnung schnittpunkt zweier quader
201209-09 (9x)http://google.de/url?sa=t&rct=j&q=schnittkörper quader
201204-04 (8x)http://google.de/url?sa=t&rct=j&q=vektoren quadermittelpunkt
201301-01 (8x)http://google.de/url?sa=t&rct=j&q=vertikalschnitt verfahren quader
2016-2017 (6x)http://int.search.tb.ask.com/search/GGmain.jhtml?st=bar&ptb=20ED590C-E610-43E...
201302-02 (6x)http://google.de/url?sa=t&rct=j&q=quaderschnitt
201501-01 (6x)http://google.de/url?sa=t&rct=j&q=durchschnitt zweier quader wieder quader
201305-05 (5x)http://google.de/url?sa=t&rct=j&q=schnittpunkt quader
201411-11 (5x)http://google.it/url?sa=t&rct=j&q=
202010-10 (5x)https://google.com/search?q=durchschnitt eines quaders
201304-04 (4x)http://google.de/url?sa=t&rct=j&q=schnittmenge zweier quader

[Top of page]

"Offene Fragen: Quaderschnitte" | 23 Comments
The authors of the comments are responsible for the content.

Re: Quaderschnitte
von: Fabi am: Mo. 04. November 2002 19:16:07
\(\begingroup\)Mein Vorschlag wäre, dass man für jeden Quader sechs Scharen von Geraden aufstellt, nämlich jeweils alle, die parallel zur Kante einer Seite liegen und auf dieser Seite liegen, also diese Seite in mehr als einem Punkt schneidet.
Dann muss man schauen, ob sich irgendwelche Geraden der Scharen schneiden und wenn ja, ob der Punkt ein Punkt der Geraden ist, der auf beiden Quadern liegt.
Ist zwar sehr aufwendig, vermute ich mal, weil man jede Schar mit jeder anderen des anderen Quaders vergleichen muss (also 36 Geradenschnitte), aber was besseers fällt mir nicht ein.
Gruß
Fabi
\(\endgroup\)
 

Re: Quaderschnitte
von: N-man am: Di. 05. November 2002 00:11:41
\(\begingroup\)Ich schreib mal einen noch nicht zu Ende gedachten Gedanken nieder.
Wenn zwei Quader gegeben sind, heißt man kennt die je acht Koordinaten Eckpunkte der Quader.
Zu jedem Quader kann ich das Maximum und Minimum der x,y,z Komponenten der jeweiligen Eckpunkte angeben. Das sind zwölf Werte.
Kann ich das nicht irgendwie auswerten, im Sinne ... das z-Minimum von Q1 liegt zwischen z-Minimum und z-Maximum von Q2 und gleichzeitig ist das y-Maximum von Q1...
irgendwie so...
Geht das nicht irgendwie?
Müsste halt bloß mal überlegen, welche Fälle auftreten könnten.\(\endgroup\)
 

Re: Quaderschnitte
von: N-man am: Di. 05. November 2002 00:15:23
\(\begingroup\)Hab grad selbst gemerkt, dass mein Gedanke Mist war.\(\endgroup\)
 

Re: Quaderschnitte
von: Ex_Mitglied_40174 am: Di. 05. November 2002 01:47:49
\(\begingroup\)warum mist?

da kann man doch zumindest ganz viele Fälle ausschließen in denen der eine Quader den anderen garantiert nicht schneidet...
oder?

eichi\(\endgroup\)
 

Re: Quaderschnitte
von: buh am: Di. 05. November 2002 11:02:50
\(\begingroup\)Könnte man das Problem nicht eventuell auf Abstände zwischen den Quadermittelpunkten und Abstände zwischen den Achsen durch die Flächenmittelpunkte reduzieren?
So als Idee.

Gruß von buh\(\endgroup\)
 

Re: Quaderschnitte
von: DaMenge am: Di. 05. November 2002 12:23:57
\(\begingroup\)Auch nur so als Idee :
Kann man nicht einfach überprüfen, ob sich die Projektionen den Quader auf die (x1, x2)-Ebene überlappen? Wenn man dies für zwei (oder drei? hmmmm) rechtwinklige Ebenen macht, sollte das ausreichen .. (Ich hab bloß keinen Schimmer von Projektionen)
MFG
DaMenge\(\endgroup\)
 

Re: Quaderschnitte
von: Ex_Mitglied_40174 am: Di. 05. November 2002 13:27:27
\(\begingroup\)Hi, ich hab das mal vor langer Zeit programmieren müssen, aber unter verschäften Bedingungen. Es war so'n komisches Sternartiges Gebilde dabei.

Ich weiss bis heute nicht, ob meine Lösung gut oder schlecht war, aber ich hab das folgendermaßen gemacht:

  • Bestimme, ob die beiden Quader überhaubt in der Nähe liegen. Stülpe 'ne kleinstmögliche Kugel drüber und prüfe, ob sich die Kugeln schneiden (Abstand der Mittelpunkte. Ist das nicht der Fall, ist die Sache eh gelaufen.
  • Okay, du weißt jetzt, die Schnittwahrscheinlichkeit ist relativ hoch :)
    Ich habe jetzt für jeden Eckpunkt abgeprüft, ob er im Inneren des anderen Objektes liegt. Das bekommt man mit ein paar Vergleichen der Koordinaten hin. man muß das allerdings für beide Objekte (Quader) machen und hat somit 16 mal ein paar Vergleiche.
    bei komplexeren Objekten muß man diese dann halt in Teilobjekte zerlegen.
Ich hab das damals mit 3 komplexeren Objekten machen müssen, die sich in einem Würfel bewegen (frei angebbare Startposition und Startgeschwindigkeit) und die gegenseitig und von den Würfelwänden abprallen. War 'ne coole Sache, lief nur etwas zäh auf dem 486er :)
Gruß,
Sammy\(\endgroup\)
 

Re: Quaderschnitte
von: Ex_Mitglied_40174 am: Di. 05. November 2002 13:43:22
\(\begingroup\)Ich würde die Quader zunächst mal dadurch angeben, das ich den Mittelpunkt nehme und dazu drei Ortogonale Vektoren, die die längen der Seiten angeben (genaugenommen, die halbe Länge).

Durch passenden Koordinatenwechsel wird einer der Quadermittelpunkte zum Ursprung, und die drei dazugehörigen Vektoren zu einer Basis. Die sollte man noch normieren.
Bezüglich der 1-Norm wird damit einer der Quader zum Einheitskreis (oder hier Würfel).

Jetzt muß man nur noch die umgerechneten Kanten des anderen Würfels nehmen, also so etwas wie
x1 + k(x2 - x1) und den Betrag minimieren. Das ist linear. Das ist dann aber nicht mehr das Problem, da es stückweise linear ist.

Wenn man irgendwann ein Minimum < 1 erhält, dann schneiden sie sich echt. Bei Minimum = 1 berühren sie sich nur und bei Minimum größer 1 berühren Sie sich nicht.

Muß noch mal im Detail drüber nachdenken, aber so sollte es funktionieren.\(\endgroup\)
 

Re: Quaderschnitte
von: Ex_Mitglied_40174 am: Di. 05. November 2002 16:12:25
\(\begingroup\)Das Thema beschäftigt schon seit Jahren die Experten und ist wohl noch immer nicht "ausgereizt" ...


http://www.mpi-sb.mpg.de/~schoemer/GIBU2000/koltheo.html

\(\endgroup\)
 

Re: Quaderschnitte
von: LutzL am: Mi. 06. November 2002 13:36:18
\(\begingroup\)Hi,

das ist ein relativ einfaches Problem, da die Quader kompakte, konvexe Koerper sind, die durch jeweils sechs Ungleichungen (die die Seitenflaechen und den Halbraum mit dem Quader beschreiben) gegeben ist. Der Schnitt ist damit ein durch 12 Ungleichungen gegebener konvexer Koerper.

Jetzt nimmt man sich noch eine lineare Zielfunktion (z.B. eine Koordinate) und kann mit dem Simplex-Algorithmus oder einem anderen Verfahren der linearen Optimierung (linear Programming) auf Loesungen testen. Ist der Schnitt leer, gibt es keine Loesung, ist er nichtleer, so gibt es einen Minimalpunkt.

Probleme gibt es mit der Rechengenauigkeit, d.h. das Verfahren funktioniert nicht zuverlaessig, wenn sich die Koerper gerade beruehren oder in der Naehe einer solchen Situation sind. Dies ist das allgemeine Problem zu entscheiden, ob eine numerische Null eine wirkliche Null ist und ob eine kleine reelle Zahl wirklich das Vorzeichen ihrer numerischen Naeherung hat.

Ciao Lutz\(\endgroup\)
 

Re: Quaderschnitte
von: FriedrichLaher am: Do. 07. November 2002 12:58:40
\(\begingroup\)schon bevor ich des programmierenden Anonymus's beitrag gelesen hatt,
hatte ich die Schnapsidee festzustellen,
WENN
die umschriebenen (3-Achsen)Elipsoide einander nicht schneiden, liegt bestimmt kein Schnitt vor;
WENN
die eingeschriebenen einander schneiden, dann tuns die Quader sicher.\(\endgroup\)
 

Re: Quaderschnitte
von: FriedrichLaher am: Do. 07. November 2002 13:05:01
\(\begingroup\)für einen Eckpunkt des Quaders B der im Quader A liegt ist der Abstand vom Mittelpunkt des Q. A
geringer als die halbe Diagonale des Q. A !!!\(\endgroup\)
 

Re: Quaderschnitte
von: FriedrichLaher am: Do. 07. November 2002 13:22:19
\(\begingroup\)schade, ist nur Sonderfall. Wenn aber irgenein Kantenpunkt näher als die halbe Diagonallänge kommt
ist's sicher ein Schnitt. Müssen eben maximal 12 Normalenfußpunkte berechnet werden, und für auf Kante liegende der Abstand. \(\endgroup\)
 

Re: Quaderschnitte
von: FriedrichLaher am: Do. 07. November 2002 15:03:25
\(\begingroup\)ach Mist, stimmt auch nicht.\(\endgroup\)
 

Re: Quaderschnitte
von: Chris am: So. 10. November 2002 12:41:48
\(\begingroup\)Hi Tüftler!

Also ich seh kein großes Problem in dieser Aufgabe, eher in der Formulierung.

Hier nur kurz:
vorausgesetzt, die Lagen der beiden Quader sind über irgendwelche Angaben auf EINDEUTIGE WEISE bestimmt, kann jeder Raumpunkt eines Quaders per Parameterdarstellung angegeben werden.

Die Frage nach dem Schnittverhalten der beiden Quader läuft dann auf die Suche nach Schnittpunkten hinaus, ein Gleichungssystem der Form

ep1 + alpha*v1 + beta*v2 + gamma*v3
= ep2 + delta*v4 + epsilon*v5 + lambda*v6

ist zu lösen. (ep1, ep2 sind jeweilige Eckpunkte und sind ermittelbar aus gegebenen Angaben, vi i=1,2,3 sowie vi i=4,5,6 sind jeweils drei zueinander orthogonal Vektoren, die parallel zu den jeweiligen Seiten der Quader sind, alpha-lambda sind Variablen, deren Wertebereiche durch Angabe der Seitenlängen der Quader beschränkt sind (0 bis jew. Seitenlänge).

Über die Gleichung lassen sich alpha-lambda in Verhältnis setzen und somit Schnittpunkte bestimmen (wenn vorhanden).

Hab mir die vorherigen Kommentare nicht alle im einzelnen angeschaut, denke daher, dass dieser Lösungsvorschlag bereits zuvor angegeben wurde.

Ciao, Chris. \(\endgroup\)
 

Re: Quaderschnitte
von: Ex_Mitglied_40174 am: Di. 19. November 2002 12:46:16
\(\begingroup\)die lösung findet sich in den grundlagen zur Computergrafik --> Projektionen von 3d nach 2d \(\endgroup\)
 

Re: Quaderschnitte
von: viertel am: Mi. 05. März 2003 14:57:11
\(\begingroup\)Hallo Matroid,
wenn es nur um die Frage geht, OB sich zwei Quader schneiden (und nicht etwa nach dem Volumen des Schnittkörpers gefragt wird), dann geht das ganz einfach:
Teste jede der 6 Flächen des einen Quaders, ob sie von einer der 12 Kanten des Anderen durchstoßen wird (nicht in der Verlängerung, sondern "in echt"). Sobald ein Hit gefunden ist ==> Schnitt.
Wenn kein Treffer, dann die Rollen der beiden Quader vertauschen und alles nochmal. Wenn dann immer noch kein Durchstoßpunkt zu finden ist, dann schneiden sich die beiden Quader nicht.
Daß das Ganze mit viel linearer Algebra und lin. Gleichungssystemen abgeht ist klar. Als Denk- und Rechenhilfe kann man zu Beginn einer Testserie ja so transformieren, daß eine Ecke des ersten Quaders im Ursprung liegt und die 3 an dieser Ecke anliegenden Kanten auf den Achsen des Koordinatensystems liegen. Dann laufen die "Durchstoßtests" einfacher ab.
Gruß
Dietmar das 1/4\(\endgroup\)
 

Re: Quaderschnitte
von: Ende am: Do. 06. März 2003 17:14:02
\(\begingroup\)Hast Du den Fall bedacht, dass ein Quader vollstaendig in einem anderen enthalten ist? Gilt das als Schnitt?

Gruss, E. 😉\(\endgroup\)
 

Re: Quaderschnitte
von: viertel am: Do. 06. März 2003 17:41:48
\(\begingroup\)Hallo Ende,
hast recht. Der Sonderfall ist mir entgangen, wobei die Frage, ob das als Schnitt gilt, offen bleibt (kann wohl nur Matroid beantworten). Aber der ist nach der Transformation wenigstens einfach durch Koordinatenvergleiche zu überprüfen.

@Matroid: ist eigentlich nur die theoretische Lösung oder auch eine praktische Umsetzung von Interesse?

Gruß
Dietmar\(\endgroup\)
 

Re: Quaderschnitte
von: matroid am: Fr. 07. März 2003 00:19:26
\(\begingroup\)Ja, ich habe die Kommentare gelesen, aber bin im Moment ohne Zeit.
Darum nur ganz kurz: Ja, es ist eine praktische Lösung gefragt.

Viele Grüße
Matroid\(\endgroup\)
 

Re: Quaderschnitte
von: viertel am: Fr. 04. April 2003 00:38:54
\(\begingroup\)Praktische Lösung heißt:
- Programm?
- Algorithmus (s.o.)?
- DLL?
- ...?

Gruß
Dietmar\(\endgroup\)
 

Re: Quaderschnitte
von: Ex_Mitglied_40174 am: So. 27. April 2003 21:57:07
\(\begingroup\)wieso kann man denn nich einfach die kanten verlängern? dann sieht man doch ob sich die dinger schneiden oder nich?

naja. vielleicht auch nich. bin kein mathe-ass... :'(\(\endgroup\)
 

Re: Quaderschnitte
von: Ex_Mitglied_40174 am: Mo. 08. September 2003 12:49:08
\(\begingroup\)Musste sowas mal im Rahmen eines Volumenmodellierers programmieren. Ein genereller Algorithmus sieht in etwa so aus:

1. Bestimme einen beide Körper umschreibenden Quader (dessen Kanten mit dem Standardkoordinatensystem aligniert sind).
2. Teile diesen Quader anhand der drei Flächen durch den Quadermittelpunkt in acht Teile.
3. Für jedes Quaderteil, prüfe ob beide Körper darinliegen.
4. Falls 3.=ja, dann Lösung=ja. Hier kann man dann auch iterativ weitermachen, wenn der Schnittkörper berechnet werden sollte.

Dieser Algorithmus funktioniert ähnlich auch zur generellen Schnittpunktberechnung von Objekten wie Linien, Ellipsen, Splines, etc.\(\endgroup\)
 

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2022 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]