Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

Kollision von zwei Rechtecken berechnen

Werbeanzeige

Anonymous

unregistriert

11

29.05.2005, 17:10

Die falsche Vorgehensweise etwas weiter oben hatte ich anfangs auch, naja so lange sich die Objekte treffen scheint es zu passen, aber sobald sie auf der anderen Seite vorbeigehen trifft es ebenfalls zu :angel:




Zitat


Es ist mit viel weniger Aufwand verbunden, zwei rechtwinklig oder parallel zueinander verlaufende Linien auf Kollision zu prüfen als zwei beliebige Linien.


Könntest du mir das genauer erklären? Ich habe es leider nicht so mit Mathe, ich kann es zwar anwenden wenn ich es habe, aber das herleiten klappt nicht so ganz.

David Scherfgen

Administrator

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

12

29.05.2005, 17:24

Das ist wirklich nicht schwer.
Nimm Dir ein Blatt Papier und nen Bleistift und mal Dir mal verschiedene Situationen auf, wo zwei Linien, die parallel zu den Koordinatenachsen (x- bzw. y-Achse) verlaufen, sich schneiden oder nicht. Und dann schaust Du, anhand welcher Bedingung man das festmachen kann, ob sie sich schneiden.
David Scherfgens Website | Konzentrationstest Polizei

Anonymous

unregistriert

13

29.05.2005, 18:44

Also eine Optimierung ist dringend nötig, mit der oben genannten Vorgehensweise sinkt die Performance selbst bei nur 2 von den 8 Überprüfungen extrem bzw. geht regelrecht in den Keller.

Ich werde mich heute Abend mal hinsetzen und mir Gedanken machen, ich glaube ich habe schon ne ungefähre Vorstellungen was du meinst :)

Atlan

Frischling

Beiträge: 27

Wohnort: Deutschland, NRW

Beruf: Azubi

  • Private Nachricht senden

14

29.05.2005, 21:44

Hmm...ok an das 'Kreuz hate ich nicht gedacht....aber man kann meine Funktion oben ja einfach nen weites else if verpassen...

Das mit dem malen wollt ich auch machen...aber da ich rechtshänder bin und mir gerade diese Hand gebrochen hab, hat das nicht geklappt ;)

mfg
Atlan

Anonymous

unregistriert

15

30.05.2005, 20:25

Hm also ich bin jetzt ne ganze Weile hier gesessen und habe das wie Atlan oben auch festgestellt nur mit dem Kreuz bin ich mir nicht so sicher, mein Ansatz ist folgender:

Und als Beispiel nehme ich das

Quellcode

 
1
2
3
4
5
6
7
8
9
10

   |   |
    |   |
    |   |
 ___|___|___
|   |   |   |
|___|___|___|
    |   |
    |   |
    |   |
    |___|



Ich suche zuerst das Rechteck dessen vertikale Linie den kleinsten x-Wert hat, das wäre die linke Linie in der Zeichnung oben und gehört zum Querbalken.
Jetzt schaue ich ob der x-Wert einer der beiden vertikalen Linien des anderen Rechtecks innerhalb der vertikalen Linien des Querbalken liegen,
wenn das so ist, dann prüfe ich die horizontalen Linien, dort schaue ich nach der linie mit dem kleinsten y-wert, zu welchem Rechteck es gehört und ob einer der horizontalen Linien des anderen Rechtecks in diesen liegen, wenn das auch stimmt, so schneiden sich die beiden Rechtecke.

so weit mein Ansatz, nur bin ich mir nicht sicher ob das wirklich stimmt und um wie viel performanter diese Prüfung zu den Schnittpunkten ist.
Mir kommt sie ziemlich kompliziert vor

Anonymous

unregistriert

16

30.05.2005, 20:41

Was ich ganz vergessen habe, ich habe mal zum Spaß den Algo aus dem Tutorial für alle der 8Berechnungen von oben verwendet und bin zu einem seltsamen Ergebnis gekommen, nämlich aLinks mit bOben und aLinks mit bUnten funktioniert einwandfrei, jedoch aRechts mit bOben und aRechts mit bUnten ist nicht wirklich genau wenn ich mit Rechteck a links von Rechteck b vorbeifliege dann erkennt es das auch als Kollision obwohl noch so 3mm Platz dazwischen sind.
Und bei aOben mit bRechts und aOben mit bLinks läuft so gut wie gar nichts mehr da werden Kollisionen erkannt wo gar keine sein können.

Bevor ich auf aOben geprüft habe dachte ich mir, dass es mit größeren Zahlen größere Ungenauigkeiten gibt, aber bei aOben funktioniert es überhaupt nicht mehr.

Ich habe hier einmal die Daten aus einer gefunden Kollision von aRechts, obowhl es keine gibt wie man an den Koordinaten sehen kann:

Zitat


p(661|550)
u(661|600)
q(678|565)
v(728|565)

D -> 63335.0
Ds -> 1315.0
s -> 0.020762611
Dt -> 10498.0
t -> 0.16575353



Meine lineHitsLine-Funktion sieht so aus:

C-/C++-Quelltext

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

private boolean lineHitsLine( Vector2D p, Vector2D u, Vector2D q, Vector2D v )
{
    float D = u.y * v.x - u.x * v.y;
    
    if( D < 0.0001f && D > -0.0001f )
        return false;
        
    float Ds = (q.y -p.y ) * v.x - (q.x -p.x ) * v.y;
    float s = Ds / D;
    if( s < 0.0f || s > 1.0f )
        return false;
            
    float Dt = ( q.y - p.y ) * u.x - ( q.x - p.x ) + u.y;
    float t  = Dt / D;
    if( t < 0.0f || t > 1.0f )
        return false;
    
    return true;
}

Anonymous

unregistriert

17

02.06.2005, 17:48

Kann mir keiner helfen :crying:

Atlan

Frischling

Beiträge: 27

Wohnort: Deutschland, NRW

Beruf: Azubi

  • Private Nachricht senden

18

02.06.2005, 17:52

Ich blamier mich ja immer ;)

C-/C++-Quelltext

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

struct SRechteck 
{ 
   Vector2 LinksOben; 
   Vector2 RechtsUnten; 
}; 

bool KolisionZweierRechtecke(SRechteck A, SRechteck B) 
{ 
   if(A.LinksOben < B.LinksOben && A.LinksOben > B.RechtsUnten) 
      return true; 
   else if(B.LinksOben < A.LinksOben && B.LinksOben > A.RechtsUnten) 
      return true; 
   else if(A.RechtsUnten > B.LinksOben && A.RechtsUnten < B.RechtsUnten) 
      return true; 
   else if(B.RechtsUnten > A.LinksOben && B.RechtsUnten < A.RechtsUnten) 
      return true; 
   // Hier fehlt noch die 'Kreuz'-Kontrolle


   return false; 
}


Und jetzt denk dir einfach noch ne Abfrage für das 'Kreuz' aus.

mfg
Atlan

Anonymous

unregistriert

19

02.06.2005, 19:39

Genau das ist doch mein Problem, meine Idee steht ja auf der Seite davor und dafür brauche ich mehr Vergleiche wie die Funktion bisher hat

Steven77

Alter Hase

Beiträge: 515

Wohnort: Münster - Gievenbeach

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

20

03.06.2005, 11:49

Dreh die Tests doch einfach mal um! Du checkst die ganze Zeit, ob die Rechtecke sich schneiden. Teste doch einfach mal, ob die sich nicht schneiden:

Pseudo-Code:

Quellcode

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

struct Rechteck
{
    links, oben, rechts, unten
}

bool KollisionRechteckRechteck(Rechteck A, Rechteck B)
{

    if   A.links   rechts_von   B.rechts
        return false
    if   A.rechts   links_von   B.links
        return false
    if   A.oben    unter    B.unten
        return false
    if   A.unten   über   B.oben
        return false

    // Alles andere führt zu einer Kollision.
    // Entweder liegt mindestens ein Punkt des einen Rechtecks
    // in dem jeweils anderen, oder die Bäuche der Rechtecke
    // bilden ein Kreuz ;)
    return true

}

Werbeanzeige