\(\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}\) 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.
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.
\(\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\)
\(\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\)
\(\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.
\(\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\)
\(\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\)
\(\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\)
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.
\(\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\)
\(\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\)
\(\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\)
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
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.
\(\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\)
\(\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?
\(\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\)
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
Printer-friendly version
Get link to this article
Comments
Für diesen Artikel gibt es keine pdf-Datei
Dieser Artikel ist im Verzeichnis der 
