Rechtecke, die kollidieren

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
vladima
User
Beiträge: 14
Registriert: Sonntag 23. April 2017, 14:58

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. :D
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!
Zuletzt geändert von Anonymous am Samstag 17. Juni 2017, 16:10, insgesamt 1-mal geändert.
Grund: Quelltext in Python-Codebox-Tags gesetzt.
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()`.
__deets__
User
Beiträge: 14493
Registriert: Mittwoch 14. Oktober 2015, 14:29

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.
vladima
User
Beiträge: 14
Registriert: Sonntag 23. April 2017, 14:58

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 :D
Ich melde mich morgen eventuell nochmal, falls ich es nicht hinbekomme.

Liebe Grüße
vladima
User
Beiträge: 14
Registriert: Sonntag 23. April 2017, 14:58

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
Zuletzt geändert von Anonymous am Sonntag 18. Juni 2017, 14:56, insgesamt 1-mal geändert.
Grund: Quelltext in Python-Codebox-Tags gesetzt.
Sirius3
User
Beiträge: 17711
Registriert: Sonntag 21. Oktober 2012, 17:20

@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.
bords0
User
Beiträge: 234
Registriert: Mittwoch 4. Juli 2007, 20:40

__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.
BlackJack

@vladima: Was mich ein wenig irritiert ist das `abs()` beim berechnen der Fläche: Du erlaubst negative Breite und/oder Höhe?
__deets__
User
Beiträge: 14493
Registriert: Mittwoch 14. Oktober 2015, 14:29

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?
Benutzeravatar
Kebap
User
Beiträge: 686
Registriert: Dienstag 15. November 2011, 14:20
Wohnort: Dortmund

Hier ein Beispiel von der im übrigen auch thematisch verwandten Seite http://www.back-side.net/codingrects.html

Bild
MorgenGrauen: 1 Welt, 8 Rassen, 13 Gilden, >250 Abenteuer, >5000 Waffen & Rüstungen,
>7000 NPC, >16000 Räume, >200 freiwillige Programmierer, nur Text, viel Spaß, seit 1992.
__deets__
User
Beiträge: 14493
Registriert: Mittwoch 14. Oktober 2015, 14:29

Hah! Danke. Und ja, den hab' ich nicht bedacht.
vladima
User
Beiträge: 14
Registriert: Sonntag 23. April 2017, 14:58

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?
vladima
User
Beiträge: 14
Registriert: Sonntag 23. April 2017, 14:58

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
Zuletzt geändert von Anonymous am Montag 19. Juni 2017, 13:49, insgesamt 1-mal geändert.
Grund: Quelltext in Python-Codebox-Tags gesetzt.
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.
Antworten