Überlappung bei Rechtecken

[3_of_8]

Morgen.

Ich steh grad total aufm Schlauch.

Ich brauche eine Funktion, die zurückgibt, ob sich zwei Rechtecke mit gegebenen Koordinaten überschneiden und eine andere, die das Schnittrechteck zurückgibt.

Ein Denkanstoß und evtl. Pseudocode wären gut...

Danke im Voraus.

[marabu]

Nimm IntersectRect() und du hast beides.

Grüße vom marabu

[3_of_8]

Java. Nicht Delphi. Sonst hätt ichs ja unter "Sonstige Fragen zu Delphi" gepostet.

Außerdem sollen wir wohl eine eigene Funktion schreiben.

[alcaeus]

Mal einen Denkanstoss:

die Rechtecke haben die Koordinaten (AL, AT, AR, AB) bzw. (BL, BT, BR, BB) fuer (Links, Oben, Rechts, Unten), wobei der erste Buchstabe das Rechteck angibt. Die Rechtecke ueberschneiden sich dann, wenn mindestens eine Ecke eines Rechtecks in der Flaeche des anderen Rechtecks liegt. Ich zeigs mal fuer ein Rechteck. Damit sie sich ueberlappen, muss folgendes zutreffen:

• Links oben im Rechteck: AL in BL..BR && AT in BT..BB
• Links unten im Rechteck: AL in BL..BR && AB in BT..BB
• Rechts unten im Rechteck: AR in BL..BR && AB in BT..BB
• Rechts oben im Rechteck: AR in BL..BR && AT in BT..BB

Du kannst das natuerlich auch umgekehrt machen; jedenfalls gilt: wenn eine Ecke von Rechteck A in Rechteck B liegt, so muss mindestens eine Ecke von Rechteck B in Rechteck A liegen ;)
Wenn eben eine dieser Bedingungen zutrifft, ueberlappen sich die Rechtecke. Die Ueberlappungsflaeche laesst sich dann anhand der zutreffenden Ecke sehr schnell finden.

Greetz
alcaeus

[3_of_8]

So ähnlich hab ichs mir auch schon gedacht...

Aber ich hab dann nicht mehr weitergemacht, weil ich mir irgendwie dumm dabei vorgekommen bin, vier if-Abfragen zu schreiben...

Und außerdem bin ich hundemüde...

Das kann ja was werden, wenn ich am 27. Klausur schreib...

Danke jedenfalls.

[JasonDX]

Zitat:

Zitat von 3_of_8

Aber ich hab dann nicht mehr weitergemacht, weil ich mir irgendwie dumm dabei vorgekommen bin, vier if-Abfragen zu schreiben...

Falls keine ifs dabeisein sollen koennte ich mit sowas dienen:

Code:

struct Rectangle
{
  int l; //left
  int r; //right
  int t; //top
  int b; //bottom
}
bool Overlaying(Rectangle r1, Rectangle r2)
{
   return ((((r1.r-r1.l+r2.r-r2.l)/2)-(java.lang.Math.abs(r1.l+r1.r-r2.l-r2.r)/2))<0?0:1+((java.lang.Math.abs(r1.t+r1.b-r2.t-r2.b)/2)-((r1.b-r1.t+r2.b-r2.t)/2))>0?0:1)>0;
}

Ist zwar rein mathematisch, die Leserlichkeit sei allerdings dahingestellt...
Auf Herz und Nieren getestet hab ichs auch nich, aber von Gedanken und Implementierung her muessts passen.

greetz
Mike

[marabu]

Zitat:

Zitat von 3_of_8

Java. Nicht Delphi. Sonst hätt ichs ja unter "Sonstige Fragen zu Delphi" gepostet.

In welcher Sprache du InterSectRect() implementierst bleibt doch dir überlassen. In Delphi sind es sehr übersichtliche fünf Zeilen Code. Wenn ich meine Funktion jetzt hier hin schreibe, dann verstoße ich sicher gegen den Hausaufgabenhilfe-Paragraphen. Außerdem wirst du dann antworten, dass du es dir schon ganz ähnlich gedacht hattest. Deshalb nur ein Hinweis: der Code wird viel kompakter, wenn du die Kanten und nicht die Ecken betrachtest.

Gute Nacht

marabu

[3_of_8]

Also, diese Übungen sind freiwillig, ist ja auch an der Uni. Werden nicht bewertet, darum wollte ich ja auch "nur" einen Denkanstoß bzw. Pseudocode.

Wo ich IntersectRect finde, wusste ich nicht, ich dachte, die entsprechende Unit wäre nicht als Source in Delphi dabei.

Und wie du das mit den Kanten meinst, weiß ich nicht.

[mkinzler]

In der Mathematik bezeichnet man die Seiten als Kanten.

BTW. Mit 15 an der Uni. Respekt ;-)

[3_of_8]

Ich weiß was Kanten sind (so doof bin ich jetzt wieder auch ned. ;) ), aber ich weiß nicht, was dadurch leichter wird, wenn ich Kanten und nicht Ecken betrachte.

Und, ich sage es nochmal, das nennt sich Schülerstudium, sind bis zu 3 Kurse (jeweils mit Klausur), der erste hat schon angefangen und den mache ich jetzt.

[JasonDX]

Also: damit mein Post oben nicht fuer immer ein kryptisches Geheimnis bleibt erklaer ich mal, wie ich meine Loesung geschrieben habe:
Betrachten wir mal nur die erste der 2 Dimensionen, die unsere zwei Rechtecke (A und B) haben, und gehen mal davon aus, dass sie sich y-maessig schneiden.
Wie ueberpruefe ich aber, ob sich die Rechtecke nur in Beachtung der X-Achse schneiden? ganz einfach, ich messe deren Abstand zwischen den Mittelpunkten der 2 Rechtecke. Diesen Abstand nennen wir mal d.
Wenn man sich nun die Rechtecke anguckt, fragt man sich: Wie gross darf der Abstand maximal sein, dass sich die Rechtecke noch schneiden?
Ganz einfach:
Sei a die Ausdehnung des ersten Rechtecks an der X-Achse, und b die des zweiten Rechtecks, so muss d < a/2 + b/2 sein. Wenn man sich das aufzeichnet, faellt es relativ schnell auf ;)
Wenn ich dies nun nicht nur fuer die X-, sondern auch fuer die Y-Achse mache, und alle anderen Dimensionen, die ich hab, so erhalte ich am Ende viele boolsche Werte:
A&B schneiden sich bezueglich der X-Achse
A&B schneiden sich nicht bezueglich der Y-Achse
[...]

Die Rechtecke schneiden sich nur, wenn sie sich in Bezug zu jeden einzelnen Achsen ueberlagern. Also: Die erhaltenen boolschen Werte mit & verknuepfen und als Ergebnis zurueckgeben, und schon hammas :)

Das sollte als Gedankenanstoss reichen, und es sollte kein allzugrosses Problem mehr sein, dieses Prinzip in halbwegs lesbaren Java-Code zu implementieren ;)

greetz
Mike

[Luckie]

Zitat:

Zitat von 3_of_8

Java. Nicht Delphi.

Und wo erfährt man, dass es dir um Java geht? :roll: Hellsehen kann hier wahrscheinlich noch keiner. :wall:

[Hansa]

Zitat:

Zitat von 3_of_8

...aber ich weiß nicht, was dadurch leichter wird, wenn ich Kanten und nicht Ecken betrachte...

Du reduzierst damit ein 2-dimensionales Problem auf 1 Dimension. Und das kann ein gewaltiger Unterschied sein. Die Frage gehört sowieso eher in die 6. Klasse, als auf die Uni.

OT : Mann, mann. Sieht so die "Bekämpfung" der Pisa-Studie aus ? :shock: Sechstklässler werden zu Studenten "befördert", die das machen müssen, was sie in der Schule sowieso nicht kapiert haben ? :lol:

[3_of_8]

Also, @Luckie: Es ist vollkommen irrelevant mit welcher Sprache, ich will ja keine fertige Funktion verwenden, sondern selber eine schreiben, daher auch "Denkanstoß" und "Pseudocode".

@Hansa: Ich kann natürlich eine einzelne Kante betrachten. Ich hab bloß nicht so ganz kapiert, was mir das im gesamten hilft. Denn ich hab den Beitrag so verstanden, dass ich eine Kante und nicht eine Ecke vergleichen soll. Und das kam mir irgendwie komisch vor. Jetzt kapier ichs, das kommt dann allerdings ziemlich genau auf alcaeus' Code raus. Und, ich bin ein Neuntklässler und sicherlich nicht deshalb dafür ausgewählt worden, weil ich so furchtbar dumm bin. Bemerkungen dieser Art finde ich ungerechtfertigt.

[Hawkeye219]

Ok, noch ein Denkanstoß:
Versuche zunächst die Koordinaten eines (möglichen) Schnittrechtecks zu bestimmen. Vielleicht beantwortet das ja auch die Frage nach der Existenz einer Überdeckung...

Gruß Hawkeye