Schnittfläche 2 Rechtecke: Nun will ich einfach nur wissen, ob sich die beiden Rechtecke schneiden.

Question

Liebe Geo-Gemeinde,

ich habe X-Koordinate, Y-Koordinate, Länge, Breite und Winkel von 2 Rechtecken. Nun will ich einfach nur wissen, ob sich die beiden Rechtecke schneiden. Gibt es dafür eine einfache Formel?

Viele Dank für eurer Hilfe

PeTeR

Comments

Wie meinst du das genau?

Könntest du skizzieren, was du da genau hast als Koordinaten und Winkeln?

Geo? Soll das auf einer Karte in einem Koordinatensystem sein?

---

Hi Lu. Ich glaub er meint das so. Wenn man die Koordinate eines Eckpunktes kennt und den Winkel um den es zu den Koordinaten-Achsen verdreht ist, sowie Breite b und Höhe h, dann sollte eine Beschreibung der Punkte-Menge des Rechtecks möglich sein. Wenn man die hat, kann man schauen ob es Schnittpunkte mit der Punkte-Menge eines anderen Reckecks gibt, das in gleicher Weise beschrieben wird. Kommt das hin?

---

Hi Lu und Johann, erst mal vielen Dank für eure Bemühungen. Johann hat völlig Recht. Ich habe auch mal eine einfache Zeichnung erstellt. Ich kenne die Koordinaten der MITTELPUNKTE beider Rechtecke. Die beiden Rechtecke in der Zeichnung haben einen Winkel von 0 Grad gegenüber der X-Achse. Das ist jedoch der einfache Ausnahmefall. Schwieriger wird es, wenn die beiden Rechtecke in beliebigem Winkel im 2D-Raum liegen können. Vielen Dank für eure Unterstützung PeTeR

---

Ich hab eine vielversprechende Idee. Ich muss aber erstmal ausknobeln wie die Umsetzung aussieht. Es wird also ein wenig dauern. Wenn Du am Abend wieder vorbeischaust, könnte ich es raus haben. Wenn's doch nich geklappt hat schreib ich noch 'nen Kommentar.

lg JR

---

Wenn ich etwas mitmischen darf.

 

Das einfachste was ich hier sehe ist das kurz zeichnerisch zu lösen. Von den Rechtecken ist wohl alles gegeben. Der Mittelpunkt, sowie Länge und Breite und Winkel. Mehr brauchts ja gar nicht.

 

Das Rechnerisch zu lösen ist natürlich auch möglich. Ein Beispiel wäre die Seiten als Geraden aufzufassen und schauen wo sich diese schneiden. Dann überprüfen, ob der Schnittpunkt innerhalb des Rechtecks liegt. Das was mir da aber im Kopf schwebt (vllt gehts auch einfacher) ist aber bei weitem aufwendiger als kurz Blatt und Stift in die Hand zu nehmen ;).

 

Fazit: Den Zeichenaufwand halte ich für eine wenige-Minuten-Aufgabe. Den Rechenaufwand würde ich locker auf über 5 Minuten bezeichnen (ist natürlich gut machbar, aber steht in keiner Relation zur Zeichnung).

 

Grüße

---

Zeichnerische Bearbeitung:

Der Mittelpunkt M ist nach Deiner Aussage bekannt.

Trage diesen auf. Lege Dein Geodreieck in dem wohl auch bekannten Winkel α an. Nun trage die halbe Länge ab (grüne Linie). Am Endpunkt lege im 90°-Winkel die Breite (hier blau) ab.

Damit bist Du dann auch schon so gut wie fertig ;).

 

Das mache nich mit dem zweiten Recheck und schaue ob diese sich schneiden ;).

(Das ganze natürlich im Koordinatensystem)

 

 

---

Hallo Unknown, vielen Dank für deine Antwort. Leider muss ich das Problem mit einem Programmier-Code lösen und benötige deshalb eine Formel.



PeTeR

---

Ah ok, dann warten wir mal, was Johann bringt ;).

Sonst kann ich selbst nochmals schaun.

 

Grüße

---

Also wenn Du eine Idee hast nur heraus damit. :D

Ich wollte niemanden davon abhalten die eigene Lösungsidee zu präsentieren.

---

Hab nur Ansätze und noch nicht fertig gedacht. Das in nen Programmiercode zu übermitteln...

...nach Dir :D.

Answer 1

So, hier mal eine Beschreibung deines Problems mit Hilfe der analytischen Geometrie. Ich poste mal alles was ich aufgeschrieben habe, auch wenn sich vieles wiederholt. Vielleicht ist es so aber besser nachvollziehbar...

Bild 1: Vektoren, Rechteck im Koordinatensystem

 

Bild 2: Geradengleichungen zur Beschreibung der Seiten des Rechtecks

 

Bild 3: Geraden zur Beschreibung der Seiten des Rechtecks mit normiertem Richtungsvektor

 

Bild 4: Im Koordinatensystem gedrehtes Rechteck

 

Bild 5: Gedrehte normierte Geraden, Drehung mittels Drehmatrix

 

Bild 6: Zur Drehung verwendete Drehmatrix

 

Ich denke mit diesen Gleichungen kannst Du die Seiten gut beschreiben. Du müsstest eben 16 Fälle prüfen, also bei jeder Seite des einen Rechtecks schauen ob sie irgendeine Seite, des anderen Rechtecks schneidet. Dazu kannst Du die Geradengleichungen gleichsetzen und schauen ob die Lösungen innerhalb des Wertebereichs von t_i (i=1; 2; 3; 4) liegt.

Wie ich grad seh hat das Reinhard ja auch schon alles (mit Worten) beschrieben. Ich denke die Gleichungen, die ich Dir aufgeschrieben habe, sollten sich auch programmiertechnisch umsetzen lassen. Ich hab das ganze mal testweise von Matlab plotten lassen und den Winkel alpha varriiert. Das hat gut funktioniert. Mit Matlab sollte man die Beschreibung auch in C-Code portieren können (hab ich allerdings noch nicht ausprobiert).

 

lg JR

Comments

Ok. Mir ist grad eingefallen, dass man die Reihenfolge von Drehung und Verschiebung des Rechtecks vielleicht noch vertauschen sollte.

Ich mach das mal, dauert aber noch eine Weile. --> 22.00Uhr

---

Hallo Reinhard und Johann, ganz, ganz herzlichen Dank für eure Antworten!!!!!!! Speziell an Johann: deine Lösung ist der absolute Wahnsinn!!!!!!!!! Ich befürchte jedoch, dass ich das nicht programmieren kann. Mach` dir bitte keine weitere Mühe mehr dazu!!!!

LG

PeTeR

---

Naja, in welcher Programmiersprache schreibst Du denn das?

---

Donnerwetter, was für ein(e)  Mühe/Fleiß bei der Lösung; ganz großen Respekt !!!

---

Ich wollte das in Excel-VBA programmieren - aber ich befürchte, dass Vektoren mein mathem. Verständnis übersteigen. Ich werde deine Lösung auf jeden Fall mit einem "Techniker" analysieren und dann die weitere Vorgehensweise entscheiden. Ich bin echt beeindruckt von deinen Fähigkeiten. Nochmals vielen Dank für die große Mühe, die du dir gemacht hast!!!!!!!!!!! Du hast mir sehr geholfen!!!!!

LG PeTeR

---

Also ich werd das nochmal ein wenig umschreiben. Ist keine große Sache. Dann kannst Du das Rechteck beliebig rotieren und verschieben in Deinem Koordinatensystem. Das was ich schon aufgeschrieben hab ist zwar nicht falsch, kommt Deiner Frage aber nicht so ganz entgegen.

---

Hallo Johann, ich bin fassungslos über deine Hilfsbereitschaft!!!!!!!

LG PeTeR

---

Bild 7: Umgeschriebene Gleichungen, Richtungsvektoren normiert

 

Bild 8: Erklärung, Zeichnung

---

So. Ich hab Dir die Vektorgleichung mal als normale Gleichungen aufgeschrieben. Jetzt sind x und y Komponente von einem Parameter abhängig.

Nehmen wir g₁(t₁): Die x-Komponente ist g_x(t₁) und die y-Komponente g_y(t₁), beide von t₁ abhängig, so wie eine normale Geradengleichung.

Um das besser zu verstehen zeichnest Du Dir das vielleicht mal kurz auf für

h = 4;
b = 8;
alpha = 30°;
sin(30°) = 1/2;
cos(1/2) = sqrt(3)/2
x_R = 5;
y_R = 6;

0 ≤ t₁ ≤ h;

t1	gx(t1)	gy(t1)
0	2.54	2.27
1	2.04	3.13
2	1.54	4.00
3	1.04	4.87
4	0.54	5.73

Du berechnest also die x und die y Koordinaten in abhängigkeit von t1 und nicht y in Abhängigkeit von x so wie sonst. Ansonsten gehst Du aber genauso vor, das heißt Du hast die Werte für x und y und kannst so den Punkt in ein x-y-Koordinatensystem einzeichnen.

Nun zur Lösung deines Problems: Du kannst nun jedes beliebige Rechteck beschreiben mit Hilfe der Parameter, die oben stehen (h, b, etc.) mit jeder beliebigen Orientierung α. Dazu gehört ein Satz von vier Geradengleichungen mit jeweils einer Gleichung für die x und die y Komponente abhängig von dem Parameter t_i.

Wenn Du nun wissen willst ob zwei Seiten g1 und g5 sich schneiden machst Du Folgendes:

Gleichung die Seite g1 beschreibt:
g_1x = t₁ *v_1x +u_1x;  
g_1y = t₁ *v_1y +u_1y; 
 

Gleichungen die g5 beschreiben:
g_5x = t₅ *v _5x +u_5x ;
g_5y = t₅ *v_5y +u_5y; 

Nun setzt Du g_1x = g  _5x     und g _1y  = g_5y  : 
t₁ *v_1x  +u_1x  =  t ₅ *v _5x +u_5x; 
t₁ *v_1y  +u_1y  =  t ₅  *v_5y +u_5y; 

Du hast also zwei lineare Gleichungssysteme mit zwei Unbekannten t₁ und t₅. Da die Restlichen Faktoren und Glieder bekannt sind (musst h, α, usw. einsetzen, siehe auch Bild 9 wie v1x usw. berechnet werden bzw. sich zusammensetzen) kannst Du nun t₁ und t₅ bestimmen. Falls Du nicht weißt wie das geht frag am besten nochmal.

Wenn die Geraden sich schneiden erhältst Du Werte für t₁ und t₅ (musst natürlich auch die spezialfälle bedenken, wenn sie z.B. identisch sind), dann schaust Du ob die errechneten Werte auch im Wertebereich liegen, also bei t₁: 0 ≤ t₁ ≤ h.

 

Ich denke jetzt hab ich das soweit erklärt wie ich das erklären wollte und es auch programmierbar sein sollte. Wenn Du Fragen hast, dann schreib bitte einen Kommentar. Bedenke bitte auch, dass ich zwar alles nochmal geprüft habe und auch stimmen sollte, aber es kann natürlich trotzdem noch ein Fehler irgendwo sein. Wenn Du was entdeckst oder Dir etwas komisch vorkommt, dann schreib bitte auch einen Kommentar.

 

lg JR
 

---

Hallo Johann, du bist der absolute Wahnsinn - das ist genial!!!! Deine Hilfsbereitschaft und Mühe sind echt phänomenal! Jetzt werde ich mal versuchen, das Ganze in VBA-Code zu packen. Nochmals TAUSEND DANK

VG PeTeR

Answer 2

"Gibt es dafür eine einfache Formel?"

Was du brauchst ist keine Formel sondern einen Algorithmus. Also eine (Rechen)vorschrift um das Problem zu lösen.

 

Die Idee von Johann Ribert ist schon sehr gut:

a) Bestimme die 4 Eckpunkte des jeweiligen Rechtecks. Dazu addierst du, ausgehend vom Mittelpunkt, einmal die halbe Breite zum X-Wert dazu, einmal ziehst du Sie ab. Dann das gleiche mit Höhe und Y-Wert. Wenn der Winkel ≠ 0 ist musst du den noch rotieren. Wie das geht kann ich ad-hoc nicht sagen. (Jedenfalls hast du jetzt die 4 Eckpunkte des Rechtecks.) Das gleiche auch für das 2. Rechteck durchführen.

b) aus zwei benachtbarten Punkten bestimme die Geradengleichung, mit t als freien Parameter. Bestimme auch den Definitionsbereich für t. D.h. du hast jetzt 4-Gerade pro Rechteck.

c) Vergleiche jede Gerade des 1. Rechtecks mit Jeder des 2. Rechtecks. (Sind also 16 Vergleiche). Berechne ob es einen Schnittpunkt gibt und die dazugehörenden t's. Liegen beide t's im Definitionsbereich der entsprechenden Gerade schneiden die sich und damit schneiden sich die Rechtecke.
 

Vielleicht gibt es aber auch andere, einfachere, Ansätze.