Seite 1 von 1
Rechtecke, die kollidieren
Verfasst: Samstag 17. Juni 2017, 15:47
von vladima
Hallöchen! Ich bin gerade dabei, mir Klassen etwas näher anzusehen und stecke gerade ein bisschen fest. Ich habe vorgegebene Rechtecke und soll nun schauen, ob sie kollidieren und falls ja, den Flächeninhalt des entstandenen Rechtecks auszurechnen.
Irgendwas stimmt momentan nicht und ich komme nicht dahinter, was. Prinzipiell hab ich mir überlegt, dass ich mir ja die obere linke Ecke (bzw irgendeine, ist ja erstmal egal) aussuche und vergleiche. Da kam ich allerdings schon zu einer relativ langen, ekligen if Bedingung, die man mit Sicherheit auch schöner ausdrücken kann - abgesehen davon, ist sie auch falsch.

Mein Code ist hier:
Code: Alles auswählen
class Rechteck:
#Rechteck besteht aus den Koordinaten des Mittelpunktes, der Länge l und der Breite b
def __init__(self, cx, cy, l, b):
self.cx = cx
self.cy = cy
self.l = l
self.b = b
def __str__(self):
s = "[" + str(int(self.cx - self.b/2))+","+ str(int(self.cx + self.b/2)) +"] x ["+ str(int(self.cy - self.l/2))+"," + str(int(self.cy + self.l/2)) + "]"
return s
def schnitt(self,other):
#ls1 ist die linke,obere Ecke des ersten Rechtecks, angegeben durch den Mittelpunktx - Länge/2 und Mittelpunkty + breite/2 als Liste
ls1 = [self.cx - self.l / 2, self.cy + self.b / 2]
#ls2 ist die linke,obere Ecke des zweiten Rechtecks, gleiche Angabe als Liste
ls2 = [other.cx - other.l / 2, other.cy + other.b / 2]
# WENN die x Koordinate von Rechteck 1 kleiner als die von Rechteck 2 + breite von 2 ist UND
# WENN die x Koordinate von Rechteck 2 kleiner als die von Rechteck 1 + breite von 1 ist UND
# WENN die y Koordinate von Rechteck 2 kleiner als die von Rechteck 1 + länge von 1 ist UND
# WENN die y Koordinate von Rechteck 1 kleiner als die von Rechteck 2 + länge von 2 ist
#DANN returne TRUE
#SONST FALSE
if ls1[0] < ls2[0] + other.b and ls2[0] < ls1[0] + self.b and ls1[1] < ls1[1] + other.l and ls2[1] < ls1[1] + self.l:
return True
else:
return None
Dadurch wird ja im Prinzip ein "Umfangsrechteck" erstellt und wenn beide Rechtecke drin liegen (=TRUE), kollidieren sie. Theoretisch..
Außerdem hätte ich dann noch gern die Koordinaten, was bei dieser Methode relativ schwer ist, rauszulesen, fürchte ich. Da hab ich mir aber überlegt, wenn es TRUE ist, muss ich nochmal 4 Bedingungen implementieren, mit denen die Schnittpunkte der Breiten und Längen überprüft werden. Den Flächeninhalt kann ich ja dann relativ einfach mit einer neuen Funktion machen
(zB def calcFI(self):
return(self.b*self.l)
Das ganze scheint mir allerdings so ineffizient zu sein... Hat vielleicht jemand von euch einen Hinweis, wie ich das besser machen könnte?
Liebe Grüße!
Re: Rechtecke, die kollidieren
Verfasst: Samstag 17. Juni 2017, 16:49
von BlackJack
@vladima: Ich würde als erstes mal die interne Repräsentation ändern. Mittelpunkt und äh, wofür steht eigentlich `l` und `b`… Also nein, als allererstes würde ich vernünftige Namen wählen, wo sich der Leser nicht Fragen muss warum `l` als Abkürzung für Höhe gewählt wurde.
Und dann wie gesagt eine sinnvollere interne Darstellung. Zum Beispiel die linke obere Ecke und die Breite und die Höhe.
Danach dann erst einmal einen ganzen Zoo von `property`\s um die rechte untere Ecke, den linken, rechten, unteren, oberen Rand, und was man sonst noch so wissen können möchte, abfragen zu können.
Und dann kann man sich zum Beispiel die horizontale und vertikale ”Ausbreitung” getrennt anschauen. Also annehmen die beiden Rechtecke wären zwei unendlich hohe Streifen und man rechnet aus wie wo der linke und der rechte Rand des Streifens ist an dem die sich überlagern. Das gleiche macht man dann in der anderen Richtung. Und sofern die sich in beiden Richtungen überschneiden, hat man dann die vier Ränder des Rechtecks an dem sich die beiden unendlich Streifen kreuzen — was das gesuchte Rechteck ist. Sollte bei einer der beiden Richtungen keine Überschneidung auftreten, haben wird auch kein Schnittrechteck.
Edit: Kleine Erinnerung an die Funktionen `min()` und `max()`.
Re: Rechtecke, die kollidieren
Verfasst: Samstag 17. Juni 2017, 16:52
von __deets__
Zuerstmal ist deine Repraesentation durch Mittelpunkt und Ausdehnung ungewoehnlich. Ueblicher ist der kleinste Ankerpunkt (also zB links oben wenn du von normalen Bildschirmkoordinaten ausgehst, links unten bei mathematischen), und dann die Ausdehnung.
Dann bietet es sich an, 4 Properties einzufuehren: tl, bl, tr, br fuer top-left, bottom-left, top-right, bottom-right. Kann man natuerlich auch anders benennen. Achtung: tl - tr = breite - 1 ! Wenn dir dein Zentrum wichtig ist, kannst du natuerlich auch ein center definieren.
Wenn du dann eine Methode schreibst, die fuer einen gegebenen Punkt prueft, ob er in einem Rechteck enthalten ist, dann ist das fuer die Kollision schon die halbe Miete - da musst du dann ja nur noch alle vier oben definierten Eckpunkte von Rechteck A pruefen, ob einer im gegebenen Rechteck B enthalten ist. Wenn nicht, musst du das mit vertauschten Rollen B/A machen, denn es kann ja auch sein, dass ein Rechteck komplett im anderen enthalten ist.
Fuer die Schnittflaechenberechnung bietet es sich an, sich zu merken, welches die jeweils kleinsten und groessen Koordinaten in x und y Richtung sind, die durch einen Punkt gegeben werden, der enthalten ist. Daraus resultieren dann die beiden gegenueberliegenden Punkte, die das Schnitt-Rechteck aufspannen.
Re: Rechtecke, die kollidieren
Verfasst: Samstag 17. Juni 2017, 17:05
von vladima
Vielen Dank an euch beide!
Ich werde das ganze nochmal umstrukturieren und versuchen, gerade mit der Umbenennung und naja, einer "sinnvolleren" Angabe des Rechtecks ist es vielleicht einfacher. Mir ist noch nicht ganz klar, wie ich am besten prüfen kann, ob ein Punkt im Rechteck liegt oder nicht. Im Kopf ist das so einfach, in Python dann leider nicht so sehr
Ich melde mich morgen eventuell nochmal, falls ich es nicht hinbekomme.
Liebe Grüße
Re: Rechtecke, die kollidieren
Verfasst: Sonntag 18. Juni 2017, 14:09
von vladima
Hallöchen!
ich hab mir jetzt eine neue Methode überlegt, die aber auch noch nicht ganz richtig ist. aber schon so gut wie! Mir fällt aber gerade der Fehler nicht auf.
Edit: Im Prinzip gleiche ich erst die x Werte ab, wenn die linke Seite des ersten Rechtecks rechts von der rechten Seite des 2. Rechtecks ist, kann keine Berührung statt finden. Wenn die rechte Seite des ersten Rechtecks links von der linken des 2. Rechtecks ist, kann keine Berührung statt finden.
Das gleiche mit der oberen Kante des 1. Rechtecks und der unteren Kante des 2. Rechtecks und umgekehrt
Code: Alles auswählen
def schnitt(self,other):
#die vier ecken des 1. rechtecks
tl1 = [self.cx - self.l/2, self.cy + self.b/2]
bl1 = [self.cx - self.l/2, self.cy - self.b/2]
tr1 = [self.cx + self.l/2, self.cy + self.b/2]
#die 4 ecken des 2. rechtecks
tl2 = [other.cx - other.l/2, other.cy + other.b/2]
bl2 = [other.cx - other.l/2, other.cy - other.b/2]
tr2 = [other.cx + other.l/2, other.cy + other.b/2]
#x Wert: wenn die linke Seite von Rechteck 1 rechts von der rechten Seite von 2 ist
if tl1[0] > tr2[0]:
return None
#x Wert: wenn die rechte Seite von Rechteck 1 links von der linken Seite von 2 ist
elif tr1[0] < tl2[0]:
return None
#y Wert: wenn die obere Kante von 1 unter der unteren Kante von 2 ist
elif tl1[1] < bl2[1]:
return None
#y Wert: wenn die untere Kante von 1 über der oberen Kante von 2 ist
elif bl1[1] > tl2[1]:
return None
#ansonsten findet eine Berührung statt
else:
return True
def flaeche(self):
return abs(self.l)*abs(self.b) #länge * breite für den Flächeninhalt
Theoretisch hab ich ja alles abgedeckt, aber praktisch scheinbar nicht. Vielen Dank schonmal, falls jemand helfen möchte
Liebe Grüße
Re: Rechtecke, die kollidieren
Verfasst: Sonntag 18. Juni 2017, 18:55
von Sirius3
@vladima: wenn Du die linke, rechte, obere oder untere Seite brauchst, warum berechnest Du dann tl, tr und bl? Eine Funktion sollte nicht verschiedene Datentypen zurückliefern, warum None und True und nicht False und True? Mal doch mal die verschiedenen Fälle auf Kästchenpapier nach.
Re: Rechtecke, die kollidieren
Verfasst: Sonntag 18. Juni 2017, 22:58
von bords0
__deets__ hat geschrieben:Wenn du dann eine Methode schreibst, die fuer einen gegebenen Punkt prueft, ob er in einem Rechteck enthalten ist, dann ist das fuer die Kollision schon die halbe Miete - da musst du dann ja nur noch alle vier oben definierten Eckpunkte von Rechteck A pruefen, ob einer im gegebenen Rechteck B enthalten ist. Wenn nicht, musst du das mit vertauschten Rollen B/A machen, denn es kann ja auch sein, dass ein Rechteck komplett im anderen enthalten ist.
Es kann auch sein, dass kein Eckpunkt im anderen Rechteck enthalten ist, und sich die Rechtecke trotzdem schneiden.
Geometrische Fallunterscheidungen sind oft schwierig. Beim Programmieren vergisst man leicht etwas. Der Ausweg ist die Methode, die Blackjack beschrieb - die geometrische Bedeutung der Konstruktion ist verstanden, und der Spezialfalls (achsenparallele Rechtecke) wird ausgenutzt.
Re: Rechtecke, die kollidieren
Verfasst: Montag 19. Juni 2017, 00:32
von BlackJack
@vladima: Was mich ein wenig irritiert ist das `abs()` beim berechnen der Fläche: Du erlaubst negative Breite und/oder Höhe?
Re: Rechtecke, die kollidieren
Verfasst: Montag 19. Juni 2017, 09:20
von __deets__
bords0 hat geschrieben:
Es kann auch sein, dass kein Eckpunkt im anderen Rechteck enthalten ist, und sich die Rechtecke trotzdem schneiden.
Geometrische Fallunterscheidungen sind oft schwierig. Beim Programmieren vergisst man leicht etwas. Der Ausweg ist die Methode, die Blackjack beschrieb - die geometrische Bedeutung der Konstruktion ist verstanden, und der Spezialfalls (achsenparallele Rechtecke) wird ausgenutzt.
Hast du ein Beispiel für deinen fall?
Re: Rechtecke, die kollidieren
Verfasst: Montag 19. Juni 2017, 09:33
von Kebap
Hier ein Beispiel von der im übrigen auch thematisch verwandten Seite
http://www.back-side.net/codingrects.html

Re: Rechtecke, die kollidieren
Verfasst: Montag 19. Juni 2017, 11:04
von __deets__
Hah! Danke. Und ja, den hab' ich nicht bedacht.
Re: Rechtecke, die kollidieren
Verfasst: Montag 19. Juni 2017, 12:34
von vladima
bords0 hat geschrieben:__deets__ hat geschrieben:Wenn du dann eine Methode schreibst, die fuer einen gegebenen Punkt prueft, ob er in einem Rechteck enthalten ist, dann ist das fuer die Kollision schon die halbe Miete - da musst du dann ja nur noch alle vier oben definierten Eckpunkte von Rechteck A pruefen, ob einer im gegebenen Rechteck B enthalten ist. Wenn nicht, musst du das mit vertauschten Rollen B/A machen, denn es kann ja auch sein, dass ein Rechteck komplett im anderen enthalten ist.
Es kann auch sein, dass kein Eckpunkt im anderen Rechteck enthalten ist, und sich die Rechtecke trotzdem schneiden.
Geometrische Fallunterscheidungen sind oft schwierig. Beim Programmieren vergisst man leicht etwas. Der Ausweg ist die Methode, die Blackjack beschrieb - die geometrische Bedeutung der Konstruktion ist verstanden, und der Spezialfalls (achsenparallele Rechtecke) wird ausgenutzt.
Dann stell ich das ganze nochmal um und versuche das ganze, wie auf der verlinkten Seite beschrieben. Meine Güte, dass das so zeitaufwendig ist, hätte ich nicht gedacht. hab ein Video gesehen und dachte mir, versuchste das einfach mal... dankeschön!
BlackJack hat geschrieben:@vladima: Was mich ein wenig irritiert ist das `abs()` beim berechnen der Fläche: Du erlaubst negative Breite und/oder Höhe?
Eigentlich nicht. Wieso das da reingerutscht ist, weiß ich ehrlich gesagt gerade auch nicht mehr, ich hau das eben raus.
Ich meld mich später nochmal, falls es geklappt hat und ich keine doofen Fehler eingebaut hab.
Liebe Grüße
edit: @sirius3: das ganze hab ich der Vollständigkeit halber berechnet. Aber man kanns natürlich auch rausnehmen. Und ist das nur "schlechter Stil" wenn eine Funktion verschiedene Typen zurückgibt? Das war mir ehrlich gesagt auch nicht so bewusst, wäre dann ein True/False besser? Bzw. wo ist denn der Unterschied zwischen None und False?
Re: Rechtecke, die kollidieren
Verfasst: Montag 19. Juni 2017, 13:33
von vladima
darf leider nicht mehr editieren, daher neuer Post:
ich hab das jetzt so weit programmiert (ehrlich gesagt sehr nach Vorbild der Seite) und glaube, dass das zumindest funktioniert. Das einzige was noch fehlt, sind die Koordinaten. Bzw. ist mir gerade nicht klar, wie ich mir die tatsächlichen Schnittkoordinaten ausgeben kann, damit ich bspw. den Flächeninhalt der Schnittfläche berechnen kann
(die seltsame Angabe von x1,2,y1,2 kommt durch die Mittelpunktangabe)
Code: Alles auswählen
def schnitt(self, other):
koll = 0 #variable, die die kollision zählt, was gerade nicht funktioniert. koll ist ja logischerweise immer 1. reicht für testzwecke aber
x1 = self.cx - self.w / 2 #linke Kante vom 1. rechteck
x2 = other.cx + other.w / 2 #rechte Kante vom 2. rechteck
y1 = self.cy + self.h / 2 #obere Kante 1. rechteck
y2 = other.cy - other.h / 2 #untere Kante 2. rechteck
xl = x1 #linke Kante Umfangsrechtecks
yo = y1 #obere Kante des Umfangrechtecks
xr = x2 #rechte Kante von Rechteck2
yu = y2 #untere Kante durch untere Kante von 2
#in den foldenen if bedingungen wird geschaut, welches rechteck links/rechts ist und ggf getauscht
if x2 < x1:
xl = x2
if y2 < y1:
yo = y2
if x1> x2:
xr = x1
if y1> y2:
yu = y1
#wenn die Summe der Breiten von 1 und 2 größer ist als die Differenz der x-kanten vom U-Rechteck UND
#die SUmme der Höhen von 1 und 2 größer ist als die DIfferenz der y-kanten vom U-rechteck, Dann findet eine Überschneidung statt
if self.w+ other.w > xr - xl and self.h + other.h > yu - yo:
koll +=1
return koll
Also Pycharm spuckt mir zumindest keinen Fehler aus. Und es scheint zu funktionieren
kann ich bei den Koordinaten evtl mit min und max arbeiten?
Liebe Grüße
Edit: Nah, ganz richtig ist es immernoch nicht. Gerade getestet. Ein paar Werte sind immernoch falsch
Edit2: statt elif, if wird schon richtiger, ist aber immernoch nicht ganz korrekt aargh
Re: Rechtecke, die kollidieren
Verfasst: Montag 19. Juni 2017, 14:03
von BlackJack
@vladima: Was heisst „nur schlechter Stil“ — so eine API ist halt komisch. Man erwartet bei einer Testfunktion das das Ergebnis entweder ”wahr” oder ”unwahr” ist, aber nicht das es ”wahr” oder ”nichts” ist. Der Unterschied zwischen `False` und `None` ist das es zwei unterschiedliche Werte von unterschiedlichen Typen sind. Zwar ist es üblich `None` quasi für jeden Typ zu nehmen um ”nichts” oder ”kein Wert” zu signalisieren, aber hier ist ja trotzdem diese Asymmetrie das das Gegenteil von `True` halt nicht `None` sondern `False` ist. Eine API mit allen drei Werten wäre wieder okay, wenn man das `None` für den Fall verwendet das weder `True` noch `False` ermittelt werden konnte.
Im letzten ist es ja noch schlimmer, da wird entweder 1 zurückgegeben oder `None` wobei das `None` implizit durch das Methodenende zustande kommt. Und eine Variable die mit 0 initialisiert wird und die *eine* Kollision ”zählt” ist auch komisch.
Die ganzen Kommentare bräuchte man übrigens nicht, wenn man die Namen vernünftig ausschreiben würde. Und wie gesagt, ich würde `property`\s dafür anlegen, so dass man einfach ``if other.left < self.right:`` schreiben kann.