Kollision zweier Rechtecke, Schnittpunkte bestimmen

C.B.

Aktives Mitglied
Hallo,

ich habe eine Methode erstellt, die überprüft ob zwei Rechtecke kollidieren.
Nun möchte ich noch die Schnittpunkt der beiden Rechtecke herausfinden also x und y Wert der Schnittpunkte im Koordinatensystem.

Habt Ihr einen Tipp oder Idee wie das es umsetze? Es müsste ja dann immer zwei oder vier Schnittpunkte geben, je nach Kollision.

Vielen Dank.

Das wäre meine Kollisionsmethode:

Java:
public class Collison {
    
    static boolean collison(float xKoordinateA, float yKoordinateA, float BreiteA,
            float HoeheA, float xKoordinateB, float yKoordinateB, float BreiteB,
            float HoeheB) {       
        
        if(xKoordinateA<=xKoordinateB+BreiteB &&
           xKoordinateA+BreiteA>=xKoordinateB &&
           yKoordinateA<=yKoordinateB+HoeheB &&
           yKoordinateA+HoeheA>=yKoordinateB){
            return true;
        }
        
        return false;
    }


    

    public static void main(String[] args) {
        
        System.out.println(collison(2,3,7,7,2,3,4,5));       
        
    
    }

}
 
1. Variablennamen werden klein beschrieben (breiteA, breiteB, ...)
2. Du hast noch veregssen, dass eines der Rechtecke auch das andere umschleßen kann - ganz ohne Schnittpunkte.
3. Es gibt für die Schnittpunkte 2 mögliche x-Werte (x1Min, x1Max,x2Min,x2Max). Diese findest du, in dem du alle 4 möglichen X-Werte aufsteigend sortierst und die mittleren beiden verwendest.
(Anm. Im foglenden red ich von X1 - X4, der Indes in einer Liste wäre natürlich um 1 niedriger.)
Gehören X2 und X3 zum selben Rechteck, so liegt dieses in X komplett innerhalb des anderen, es gibt keinen Schnittpunkte
Gehört X2 zum selben Rechteck wie X1, gibt es keine X-Werte für postentielle Schnittpunkte.
Sind X2 und X3 gleich, so liegt die linke Linie des einen Rechtecks auf der rechten Linie des anderen, es gibt einen X-Wert für Schnittpunkte.
Selbiges in Y
Damit eine Kombination aus X und Y ein Schnittpunkte ist, muss sie auf jeden Fall auf beiden Rechtecken liegen.


Du kannst auch einfach alle möglichen Kombinationen aus X und Y erstellen (16 an der Zahl) und prüfen, ob sie auf beiden Rechtecken liegen. das mag sogar effizienter sein, auf jeden Fall aber einfacher umzusetzen.
 
ps: Es kann laut deiner Kollisionserkennung auch nur einen "Schnittpunkt" geben, nämlich wenn 2 Eckpuntke genau übereinander liegen.

Die Ergebnisliste hat also eine Länge von 0 ()nicht überlappend oder komplett umschließend), 1 (Ecken berühren sich), 2 (Normalfall bei Überschneidung, oder Überlappung zweier Seitenkanten) oder 4 (falls die Rechtecke genau übereinander liegen) Schnittpunkten
 
1. Variablennamen werden klein beschrieben (breiteA, breiteB, ...)
2. Du hast noch veregssen, dass eines der Rechtecke auch das andere umschleßen kann - ganz ohne Schnittpunkte.
3. Es gibt für die Schnittpunkte 2 mögliche x-Werte (x1Min, x1Max,x2Min,x2Max). Diese findest du, in dem du alle 4 möglichen X-Werte aufsteigend sortierst und die mittleren beiden verwendest.
(Anm. Im foglenden red ich von X1 - X4, der Indes in einer Liste wäre natürlich um 1 niedriger.)
Gehören X2 und X3 zum selben Rechteck, so liegt dieses in X komplett innerhalb des anderen, es gibt keinen Schnittpunkte
Gehört X2 zum selben Rechteck wie X1, gibt es keine X-Werte für postentielle Schnittpunkte.
Sind X2 und X3 gleich, so liegt die linke Linie des einen Rechtecks auf der rechten Linie des anderen, es gibt einen X-Wert für Schnittpunkte.
Selbiges in Y
Damit eine Kombination aus X und Y ein Schnittpunkte ist, muss sie auf jeden Fall auf beiden Rechtecken liegen.


Du kannst auch einfach alle möglichen Kombinationen aus X und Y erstellen (16 an der Zahl) und prüfen, ob sie auf beiden Rechtecken liegen. das mag sogar effizienter sein, auf jeden Fall aber einfacher umzusetzen.
Vielen Dank für die ausführliche Beschreibung. Ich versuche es umzusetzen🙂
 
ps: Es kann laut deiner Kollisionserkennung auch nur einen "Schnittpunkt" geben, nämlich wenn 2 Eckpuntke genau übereinander liegen.

Die Ergebnisliste hat also eine Länge von 0 ()nicht überlappend oder komplett umschließend), 1 (Ecken berühren sich), 2 (Normalfall bei Überschneidung, oder Überlappung zweier Seitenkanten) oder 4 (falls die Rechtecke genau übereinander liegen) Schnittpunkten
Das mit den Ecken ist ein guter Hinweis. Hab ich das abgedeckt mit meinem Code? Bin ich mir grad nicht sicher, werde ich nochmal prüfen.
 
Das mit den Ecken ist ein guter Hinweis. Hab ich das abgedeckt mit meinem Code? Bin ich mir grad nicht sicher, werde ich nochmal prüfen.
Einfach mal testen 🙂
Aber ja, der Code würde das erkennen. Bei dem Kommentar ging's nur um die mögliche Anzahl an Ergebnissen.


Fang mal damit an zu testen, ob ein Punkt auf einem Rechteck liegt. Verwende dafür am Besten gleich die passenden Klassen: Rectangle2D.Double und Point2D.Double, damit hast du 2 Variablen anstatt 6 double Variablen

Auf lange Sicht (nicht jetzt mit direkten Aufrufen) wirst du dir noch überlegen müssen, wie du Rechenfehler beim Erstellen des Rectangles oder des Points umgehst.

Den ersten Teil von dem, was ich oben geschrieben hab, würde ich nicht als Anleitung bezeichnen, sondern eher als Überlegung, in welche Richtung man arbeiten könnte.
 
Ich hab jetzt die zweite Prüfung eingebaut, ob sich die Rechtecke umschließen. Nun möchte ich die Kombinationen überprüfen ob die Kombinationen von Rechteck A auch auf dem Rechteck B liegen. Ich komme nur auf 8 Kombinationen anstatt 16. (siehe Kommentare im Code) Welche Kombinationen habe ich vergessen? Und wie überprüfe ich nun ob Sie auf den anderen Rechteck liegen?

Wäre es z.B. möglich wenn ich sage:

x3<=x1<=x4 && x3<=x2<=x4

Wieviele solche Bedingungen muss ich aufstellen?

Vielen Dank und Grüße


Java:
public class Collison {
    
    static boolean collison(float xKoordinateA, float yKoordinateA, float breiteA,
            float hoeheA, float xKoordinateB, float yKoordinateB, float breiteB,
            float hoeheB) {       
        
        //Alle vier Bedingungen müssen für eine Kollison erfüllt sein
        if(xKoordinateA<=xKoordinateB+breiteB &&
           xKoordinateA+breiteA>=xKoordinateB &&
           yKoordinateA<=yKoordinateB+hoeheB &&
           yKoordinateA+hoeheA>=yKoordinateB){
            return true;
        }
        
        //Komplette Umschließung der Rechtecke
        //Eines der Rechtecke kann auch das andere umschließen
        if(xKoordinateA==xKoordinateB && yKoordinateA==yKoordinateB
                && breiteA==breiteB && hoeheA == hoeheB) {
            return true;
        }
        
        return false;
    }
    
    
    //Schnittpunkte bestimmen
    //Alle möglichen Kombinationen aus X und Y erstellen
    //und prüfen, ob sie auf beiden Rechtecken liegen
    
    public void schnittpunkte(float xKoordinateA, float yKoordinateA, float breiteA,
            float hoeheA, float xKoordinateB, float yKoordinateB, float breiteB,
            float hoeheB) {
    
            //xMax und xMin sind nicht die Schnittpunkte sondern die Punkte dazwischen
            //X-Koordinaten Rechteck A:
            float x1=xKoordinateA;
            float x2=xKoordinateA+breiteA;
            
            //Y-Koordinaten Rechteck A:
            float y1=yKoordinateA;
            float y2=yKoordinateA-hoeheA;
            
            //X-Koordinaten Rechteck B:
            float x3=xKoordinateB;
            float x4=xKoordinateB+breiteB;
            
            //Y-Koordinaten Rechteck B:
            float y3=yKoordinateB;
            float y4=yKoordinateB-hoeheB;

            //Kombinationen Rechteck A:
            
            //x1 & y1
            //x1 & y2
            //x2 & y1
            //x2 & y2
            
            //Kombinationen Rechteck B:
            //x3 & y3
            //x3 & y4
            //x4 & y3
            //x4 & y4
                

    }
 
Ich hab jetzt die zweite Prüfung eingebaut, ob sich die Rechtecke umschließen.
Brauchst Du nicht, das wird von Deiner Prüfung bereits abgefangen.

Code:
(la,oa)             (ra,oa)
+---------------------+
|  (lb,ob)  A (rb,ob) |
|  +--------------+   |
|  |       B      |   |
|  +--------------+   |
|  (lb,ub)    (rb,ub) |
+---------------------+
(la,ua)             (ra,ua)

Auch in diesem Fall ist la <= rb und lb <= ra und oa <= ub und ob <= ua erfüllt.
 
Brauchst Du nicht, das wird von Deiner Prüfung bereits abgefangen.

Code:
(la,oa)             (ra,oa)
+---------------------+
|  (lb,ob)  A (rb,ob) |
|  +--------------+   |
|  |       B      |   |
|  +--------------+   |
|  (lb,ub)    (rb,ub) |
+---------------------+
(la,ua)             (ra,ua)

Auch in diesem Fall ist la <= rb und lb <= ra und oa <= ub und ob <= ua erfüllt.
Vielen Dank. Ja stimmt.. durch das Gleichzeichen ist es auch abgedeckt.
 
Habe es nun so implementiert, einmal einen Fall für 4 Schnittpunkte, einmal einen Fall für 3 Schnittpunkte. Jetzt bräuchte ich nur einen Fall, wenn es bloß zwei Schnittpunkte oder einen gibt. Da hab ich grad noch keine Idee, wie ich das überprüfen soll. Habt ihr eine Idee?

Mein letzten Rechtecke sollte nur die Schnittpunkte 3/2 und 4/2 haben aber mir gibt es noch weitere aus, die es gar nicht gibt. Ich müsste also noch eine Bedingung einbauen aber mir fällt nicht ein, wie ich das überprüfe ob es einen, zwei, drei oder vier Schnittpunkte gibt.

Java:
public class Collison {
    
    
    static boolean collison(float xKoordinateA, float yKoordinateA, float breiteA,
            float hoeheA, float xKoordinateB, float yKoordinateB, float breiteB,
            float hoeheB) {       
        
        //Alle vier Bedingungen müssen für eine Kollison erfüllt sein
        if(xKoordinateA<=xKoordinateB+breiteB &&
           xKoordinateA+breiteA>=xKoordinateB &&
           yKoordinateA<=yKoordinateB+hoeheB &&
           yKoordinateA+hoeheA>=yKoordinateB){
            return true;
        }
        
        //Komplette Umschließung der Rechtecke
        //Eines der Rechtecke kann auch das andere umschließen
        if(xKoordinateA==xKoordinateB && yKoordinateA==yKoordinateB
                && breiteA==breiteB && hoeheA == hoeheB) {
            return true;
        }
        
        return false;
    }
    
    
    //Schnittpunkte bestimmen
    
    public static void schnittpunkte(float xKoordinateA, float yKoordinateA, float breiteA,
            float hoeheA, float xKoordinateB, float yKoordinateB, float breiteB,
            float hoeheB) {
    
            //xMax und xMin sind nicht die Schnittpunkte sondern die Punkte dazwischen
            //X-Koordinaten Rechteck A:
            float x1=xKoordinateA;
            float x2=xKoordinateA+breiteA;
            
            //Y-Koordinaten Rechteck A:
            float y1=yKoordinateA;
            float y2=yKoordinateA+hoeheA;
            
            //X-Koordinaten Rechteck B:
            float x3=xKoordinateB;
            float x4=xKoordinateB+breiteB;
            
            //Y-Koordinaten Rechteck B:
            float y3=yKoordinateB;
            float y4=yKoordinateB+hoeheB;
            
            
            
            
            //finde die größere X-Koordinate der linken Kante der beiden Rechtecke
            float maxXLinks = Math.max(x1, x3);
            
            //finde die kleinere X-Koordinate der rechten Kante der beiden Rechtecke
            float minXRechts = Math.min(x2, x4);
            
            //finde die größere Y-Koordinate oben der beiden Rechtecke
            float minYOben = Math.max(y1, y3);
            
            //finde die kleinere X-Koordinate der rechten Kante der beiden Rechtecke
            float maxYUnten = Math.min(y2, y4);
            
            
            //wenn es eine Kollision gibt, dann gebe die Schnittpunkte aus:
            if((collison(xKoordinateA, yKoordinateA, breiteA,
                    hoeheA, xKoordinateB, yKoordinateB, breiteB,
                    hoeheB)==true) && xKoordinateA!=xKoordinateB && yKoordinateA!=yKoordinateB)  {
                
                System.out.println("Die x Koordinate des linken oberen Schnittpunktes ist:" +maxXLinks +"/"+maxYUnten);
                System.out.println("Die x Koordinate des rechten unteren Schnittpunktes ist:" +minXRechts+"/"+minYOben);
                
                System.out.println("Die x Koordinate des rechten oberen Schnittpunktes ist:" +minXRechts +"/"+maxYUnten);
                System.out.println("Die x Koordinate des linken unteren Schnittpunktes ist:" +maxXLinks+"/"+minYOben);
            }
            
            
            //wenn es eine Kollision gibt, aber Rechteck A und B dieselben x und y Koodrinaten haben, dann gibt es nur drei Schnittpunkte:
            if((collison(xKoordinateA, yKoordinateA, breiteA,
                
                        hoeheA, xKoordinateB, yKoordinateB, breiteB,
                        hoeheB)==true) && xKoordinateA==xKoordinateB && yKoordinateA==yKoordinateB) {

                System.out.println("Die x Koordinate des linken oberen Schnittpunktes ist:" +maxXLinks +"/"+maxYUnten);
                System.out.println("Die x Koordinate des rechten unteren Schnittpunktes ist:" +minXRechts+"/"+minYOben);
                System.out.println("Die x Koordinate des unteren linken Schnittpunktes ist:" +xKoordinateA+"/"+yKoordinateA);
            }
    }


    

    

    public static void main(String[] args) {
        
        //3 Schnittpunkte
        System.out.println(collison(2,3,7,7,2,3,4,5));       
        schnittpunkte(2,3,7,7,2,3,4,5);
        
        //4 Schnittpunkte
        System.out.println(collison(5,1,1,4,4,2,3,2));       
        schnittpunkte(5,1,1,4,4,2,3,2);
    
        //2 Schnittpunkte
        System.out.println(collison(5,1,1,4,4,2,3,2));       
        schnittpunkte(2,1,3,1,3,1.5f,1,2);
    }

}
 
Edit: Die 16 Werte kommen zustande, wenn du die Werte beider Rechtecke testet, ohne vorher irgendwas zu testen und/oder auszuschließen.
4 mögliche X-Werte, 4 mögliche Y-Werte.
Wenn's mit weniger geht, auch gut.
Über diese Brute-Force Methode kriegst du sofort alle möglichen Schnittpunkte, manche mögen in der Liste doppelt vorhanden sein, wenn die Linien genau übereinander liegen. Das muss dann noch gefiltert werden (am besten gleich ein Set für das Ergebnis verwenden).

Das kann man klarerweise optimieren, indem man die 4 Punkte eines Rechtecks jeweils nur für das andere Rechteck testet. Die anderen werden für beide getestet.
 
Zuletzt bearbeitet:
Brauchst Du nicht, das wird von Deiner Prüfung bereits abgefangen.
Code:
(la,oa)             (ra,oa)
+---------------------+
|  (lb,ob)  A (rb,ob) |
|  +--------------+   |
|  |       B      |   |
|  +--------------+   |
|  (lb,ub)    (rb,ub) |
+---------------------+
(la,ua)             (ra,ua)

Auch in diesem Fall ist la <= rb und lb <= ra und oa <= ub und ob <= ua erfüllt.

Hab die Funktion im OP gerade mit (50,50,200,200,55,55,100,100) aufgerufen. Das zweite Rechteck liegt komplett im ersten. R1 umschließt R2 also komplett.
Sie lieferte true.

Im Zweifelsfall einfach testen.
 
Moment, evtl. hab ich das falsch verstanden: soll nur der Rand auf Schnitt überprüft werden?
Genau, also ich möchte nur die Schnittpunkte der zwei Rechtecke. Manchmal gibts dann einen (Eck), zwei, drei oder vier Schnittpunkte oder wenn sie sich überdecken dann gar keinen. Weiß nur nicht wie ich die zwei oder einen (das Eck) rausbekomme.
 
Wenn die Rechtecke nicht gedreht sind (Das ist bei Deinem Code so, weil Du ja nur eine Ecke + Breite und Höhe zur Festlegung des Rechtecks hast), dann wird es relativ einfach.

Generell musst Du nur prüfen, welche Punkte des einen Rechtecks innerhalb des anderen Rechtecks sind. Das ist ja relativ einfach festzustellen.
Du hast dann die Fälle:
0 Punkte des einen Rechtecks sind im anderen Rechteck -> Hier musst du es dann noch umgekehrt prüfen.
1 Punkt ist in dem anderen Rechteck. Dann kannst Du die Zwei Schnittpunkte einfach feststellen, denn Du weißt ja, in welche Richtung die Kanten gehen (Sprich: War es der linke obere Punkt, dann müssen die Schnittpunkte nach rechts und nach unten gehen). Und da nur der Punkt im Rechteck liegen, sind die Kreuzungspunkte die linke und die untere Kante des anderen Rechtecks und da hast Du ja auch die Koordinaten.
2 Punkte sind in dem Rechteck. Das ist ein Paar wie die oberen Punkte, die rechten Punkte, die unteren Punkte, ... Sind es die oberen Punkte, dann weisst Du die x-Koordinaten der zwei Schnittpunkte schon (Das sind die von den beiden Punkten). Die Y-Koordinate der untere Kante des anderen Rechtecks ist dann die Y-Koordinate der beiden Punkte.
Alle 4 Punkte sind innen drin: Dann hast Du keine Schnittpunkte und das eine Rechteck ist komplett im anderen.

Also einfache Prüfungen und einfache Feststellung der Koordinaten.

Und bei der Feststellung musst Du am Ende bei den 2 Schnittpunkten nur prüfen, ob diese gleich sind. Das ist der Fall, wenn ein Punkt im Rechteck war und dann bei den jeweiligen Koordinaten eben wieder genau die x bzw y Koordinate heraus gekommen ist. (Sprich: Du warst schon genau auf dem Eckpunkt. Du kannst also weder in Breite noch in Höhe weiter gehen um den Schnittpunkt zu bekommen.
 
Manchmal gibts dann einen (Eck), zwei, drei oder vier Schnittpunkte
Die drei und vier Schnittpunkte sehe ich nicht. So die Rechtecke nur mit einer Koordinate + hoehe/breite angegeben werden, hast Du die Fälle mit ein oder zwei Schnittpunkten oder eben ein Beinhalten. Wenn Rechtecke "gedreht" sein können, dann wird es etwas komplexer. Aber der Algorithmus von oben lässt sich im Prinzip weiter verwenden nur die Prüfungen werden etwas schwerer bezüglich "Ist ein Punkt im gedrehten Rechteck" und auch die Schnittpunkte wären dann etwas schwerer zu berechnen. Aber wenn das notwendig wird, dann müsste man sich das nur einmal im Detail aufmalen um es dann berechnen zu können.
 
Die drei und vier Schnittpunkte sehe ich nicht. So die Rechtecke nur mit einer Koordinate + hoehe/breite angegeben werden, hast Du die Fälle mit ein oder zwei Schnittpunkten oder eben ein Beinhalten. Wenn Rechtecke "gedreht" sein können, dann wird es etwas komplexer. Aber der Algorithmus von oben lässt sich im Prinzip weiter verwenden nur die Prüfungen werden etwas schwerer bezüglich "Ist ein Punkt im gedrehten Rechteck" und auch die Schnittpunkte wären dann etwas schwerer zu berechnen. Aber wenn das notwendig wird, dann müsste man sich das nur einmal im Detail aufmalen um es dann berechnen zu können.
Ich denke, die vier "Schnittpunkte" kriegt man bei genauer Überlappung raus. Ob man hier noch von Schnittpunkten reden kann, ist fraglich, laut dem Code im ersten Post gehe ich aber davon aus, dass das gewünscht ist.
Ebenso werden Punkte als Schnittpunkte gewertet, wenn z.B. die rechte Linie des einen Rechtecks ein Teil der linken Linke des anderen ist, obwohl es keine Überschneidung im eigentlichen Sinne gibt.
So kann man auch drei mögliche Schnittpunkte erhalten, wenn ein Eck genau übereinander liegt, ein Rechteck aber in jeder Richtung größer ist als das andere (komplett umschlossen mit zwei überlappenden Seitenlinien).

Unsereins denkt dank Erfahrung mit diesen Themen einfach zu weit 🙂 Bei solchen Übungsaufgaben sind all die Spezialfälle normalerweise kein Thema.
 
Ok, das ist eine Sichtweise, die ich verstehen würde - auch wenn ich diese so erst einmal nicht sehe. Aber das liegt dann vermutlich auch nur am Verständnis was ein Schnittpunkt ist - dabei ist aber dann auch nur wichtig, was im Sinne der Aufgabe gemeint ist. Und da scheinen Deine Gedanken auf jeden Fall naheliegend zu sein wenn man die gewählten Worte betrachtet.

Wenn man bei wikipedia schaut, dann ist ein Schnittpunkt:
Ein Schnittpunkt ist in der Mathematik ein gemeinsamer Punkt von Kurven oder Flächen in der Ebene oder im Raum.
und dann wäre eine gemeinsame Strecke (Teilkante? Oder wie würde man das nennen?) sogar eine unendliche Menge an Schnittpunkten.
 
und dann wäre eine gemeinsame Strecke (Teilkante? Oder wie würde man das nennen?) sogar eine unendliche Menge an Schnittpunkten.
Ja das wäre eine Möglichkeit. Wenn man sich in der Praxis mit so was beschäftigt, werden im Normalfall aber nur die Eckpunkte gebraucht, die den Abschnitt beschreiben, den beid Rechtecke gemeinsam haben. Klar ist auch hier die Bezeichnung "Schnittpunkt" falsch.
Ich hab damit immer wieder zu tun, nur geht's in meinem Fall um Auslassungen (wobei es nicht nur um Rechtecke geht) von einem Körper. An den Seitenbereichen braucht's Spezialbehandlung, deshalb ist der überlappende Teil der Kontur wichtig. Intern reden wir dann vom nach außen offenen Bereich der Auslassung. Die Leute, für die das Ganze gemacht wird, die dann damit produzieren, haben jedoch - wie in so vielen anderen Fällen - keine einheitlichen Begriffe, jeder nennt's anders, manchmal heißen auch drei verschiedene Sachen gleich. Das verursacht schon mal migräneartige Kopfschmerzen.
 

Zurück
Oben