Rechteckezusammenfügen

Übersicht BlitzMax, BlitzMax NG Allgemein

Neue Antwort erstellen

M0rgenstern

Betreff: Rechteckezusammenfügen

 BeitragDo, März 22, 2012 16:35
Antworten mit Zitat
Benutzer-Profile anzeigen
Hallo Leute.
Ich sitze hier gerade an einer Sache, die mich fast zum verzweifeln bringt.
Undzwar habe ich mehrere, gleichgroße Rechtecke.
Diese können direkt aneinander liegen.
Also so:
Zitat:
[][]

Oder:
Zitat:

[]
[]

Sie können aber auch sonst wie liegen, das heißt nicht direkt aneinander.
Zusätzlich können beliebig viele Rechtecke sich waagerecht und senkrecht berühren.

In meinem Programm sind die Rechtecke sowas wie Mauern, das heißt ich prüfe andere Objekte gegen diese Rechtecke.
Bei vielen Rechtecken ist es jedoch nicht gerade sehr schnell.
Deshalb möchte ich die Rechtecke, die eine Linie bilden, zusammenfassen.

Mein momentaner Ansatz ist eine rekursive Funktion.
Prinzipiell funktioniert es auch.
Aber die Rechtecke sind dann immer nach links verschoben. Undzwar scheinbar um den Wert:
Code: [AUSKLAPPEN]
Anzahl zusammengefasster Rechtecke * BreiteJedesRechtecks/2

Das heißt, bei 3 Rechtecken von jeweils 32 Pixeln ist das ganze dann um 48 Pixel nach links verschoben.
Und ich weiß echt nicht, woran es liegt.

Meine Funktion sieht momentan so aus:

BlitzMax: [AUSKLAPPEN] 
	Function SumRects()
		Local tlRectsUsed:TList = New TList
	
		For Local rect1:TObstacle = EachIn TObstacle.tlAllObstacles 'Durch alle Objekte durchlaufen
			For Local rect2:TObstacle = EachIn TObstacle.tlAllObstacles 'Nochmal durch alle durchlaufen
				If Not (tlRectsUsed.Contains(rect1)) Then 'Objekt ist noch nicht genutzt
					If Not (tlRectsUsed.Contains(rect2)) Then 'Objekt ist noch nicht genutzt
					If(rect1 <> rect2) Then 'Rechtecke sind verschieden
						If(TRectangle(rect1) And TRectangle(rect2)) Then 'Beides sind Rechtecke
                                                        'Casten und zwischenspeichern:
							Local r1:TRectangle = Trectangle(rect1) 
							Local r2:TRectangle = Trectangle(rect2)

                                                        'Debugausgaben:
							DebugLog("Pos Rect1: " + r1.fX + " | " + r1.fY)
							DebugLog("End Rect1: " + (r1.fX + r1.fWidth) + " | " + (r1.fY + r1.fHeight))
							DebugLog("Pos Rect2: " + r2.fX + " | " + r2.fY)
							DebugLog("End Rect2: " + (r2.fX + r2.fWidth) + " | " + (r2.fY + r2.fHeight))

                                                        'r2 endet dort wo r1 anfängt
								If(r1.fX = (r2.fX + r2.fWidth)) Then
									If(r1.fY = r2.fY) Then 'Gleiche vertikale Position
                                                        'Neues Rechteck an der Position von r2 erstellen, als Breite die Summe aus den Rechteckbreiten nehmen
										TRectangle.Create(r2.fX, r2.fY, r1.fWidth + r2.fWidth, r2.fHeight)
                                                                         'Rechtecke der genutzt Liste hinzufügen
										tlRectsUsed.AddLast(rect1)
										tlRectsUsed.AddLast(rect2)
									EndIf
                                                        'r1 endet dort wo r2 anfängt
								ElseIf(r2.fX = (r1.fX + r1.fWidth)) Then
									If(r1.fY = r2.fY) Then 'Gleiche vertikale Position
                                                        'Neues Rechteck an der Position von r1 erstellen, als Breite die Summe aus den Rechteckbreiten nehmen
										TRectangle.Create(r1.fX, r1.fY, r1.fWidth + r2.fWidth, r1.fHeight)
                                                                            'Rechtecke der genutzt Liste hinzufügen
										tlRectsUsed.AddLast(rect1)
										tlRectsUsed.AddLast(rect2)
									EndIf
                                                        'r2 endet dort, wo r1 anfängt
								ElseIf(r1.fY = (r2.fY + r2.fHeight)) Then
									If(r1.fX = r2.fX) Then 'Gleiche horizontale Position
                                                        'Neues Rechteck an der Position von r1 erstellen, als Höhe die Summe aus den Rechteckhöhen nehmen
										TRectangle.Create(r1.fX, r2.fY, r2.fWidth, r2.fHeight + r1.fHeight)
                                                                             'Rechtecke der genutzt Liste hinzufügen
										tlRectsUsed.AddLast(rect1)
										tlRectsUsed.AddLast(rect2)
									EndIf
                                                        'r1 endet dort, wo r2 anfängt
								ElseIf(r2.fY = (r1.fY + r1.fHeight)) Then
									If(r1.fX = r2.fX) Then 'Gleiche horizontale Position
                                                        'Neues Rechteck an der Position von r1 erstellen, als Höhe die Summe aus den Rechteckhöhen nehmen
										TRectangle.Create(r2.fX, r1.fY, r2.fWidth, r2.fHeight + r1.fHeight)
                                                                             'Rechtecke der genutzt Liste hinzufügen
										tlRectsUsed.AddLast(rect1)
										tlRectsUsed.AddLast(rect2)
									EndIf
								EndIf
						       EndIf
						EndIf
					EndIf
				EndIf
			Next
		Next
		
                'Alle Rechtecke die benutzt wurden aus der Liste entfernen, da sie schon zusammengefügt wurden
		For Local rect:TRectangle = EachIn tlRectsUsed
			TObstacle.tlAllObstacles.Remove(rect)
		Next
		
		DebugLog("************************")
		If(tlRectsUsed.Count() <> 0) Then
                        'Liste leeren und Funktion nochmal aufrufen, falls die Liste nicht leer ist
			tlRectsUsed.Clear()
			SumRects()
		EndIf
	End Function


Einen anderen Ansatz habe ich bisher nicht gefunden.
Aber ich verstehe auch einfach nicht, warum das ganze so verschoben ist.
Ich nehme ja immer das Rechteck, das am weitesten links positioniert ist als Startpunkt.
Wenn ich diese Funktion nicht ausführe und somit alle Rechtecke einzeln lasse, dann sind sie alle an der richtigen Position.

Kann mir bitte jemand helfen oder vielleicht nen anderen Lösungsvorschlag machen?
Ich weiß echt nicht woran es liegt und habe auch schon den größten Blödsinn versucht.

Lg, M0rgenstern

Xeres

Moderator

BeitragDo, März 22, 2012 17:09
Antworten mit Zitat
Benutzer-Profile anzeigen
Zitat:
In meinem Programm sind die Rechtecke sowas wie Mauern, das heißt ich prüfe andere Objekte gegen diese Rechtecke.
Bei vielen Rechtecken ist es jedoch nicht gerade sehr schnell.
Darum benutzt man z.B. Tilemaps. Oder Teilt den Bereich in kleinere Teile auf.
Beliebig große Rechtecke sind einfach keine tolle Lösung und der Codewust um es irgendwie zu verbessern, zeigt schon, dass du vielleicht anders an das ganze Problem herangehen solltest.
Win10 Prof.(x64)/Ubuntu 16.04|CPU 4x3Ghz (Intel i5-4590S)|RAM 8 GB|GeForce GTX 960
Wie man Fragen richtig stellt || "Es geht nicht" || Video-Tutorial: Sinus & Cosinus
THERE IS NO FAIR. THERE IS NO JUSTICE. THERE IS JUST ME. (Death, Discworld)
 

PhillipK

 BeitragDo, März 22, 2012 17:13
Antworten mit Zitat
Benutzer-Profile anzeigen
Zuersteinmal:
So auf die schnelle erkenne ich keinen fehler.

Vielleicht liegts an TRectangle.Create() ?

Wenn die dinger nach links verschoben sind, undzwar im endeffekt um total_width/2, dann klingts so, als würde deine funktion die x positionen "mittig" aufs Rect setzen.

Sprich:

Local startX = 10
Local width = 10
Local x = startX - (width/2) ' x ist nun 5, dh das rect geht nun von 5-15

Ansonsten fällt mir nur ein kleines Performance problem auf:
BlitzMax: [AUSKLAPPEN] 
			For Local rect2:TObstacle = EachIn TObstacle.tlAllObstacles 'Nochmal durch alle durchlaufen
				If Not (tlRectsUsed.Contains(rect1)) Then 'Objekt ist noch nicht genutzt


Du könntest die if abfrage direkt nach der ersten forschleife einbringen, um somit einen kompletten Rect2 durchlauf zu sparen.

Also hier mein tipp:
Überprüfe einmal die TRectangle.create funktion und erstelle gegebenenfalls eine 2te, die auf deine Zusammenfassung zugeschnitten ist.

Ansonsten wäre die funktion an sich vllt ganz intressant - wo "beginnt" das rect? (ist das rect-origin mittig oder oben links?)

Und: In welchem fall tritt das ganze auf? Kannst du das überprüfen?
Tritt es zb nur auf, wenn du r2 dort endet, wo r1 anfängt und/oder dort, wo r1 endet und r2 anfängt?

M0rgenstern

 BeitragDo, März 22, 2012 17:51
Antworten mit Zitat
Benutzer-Profile anzeigen
@Xeres:
Ich benutze als Grundlage ja Tilemaps. Aber es geht um Lichter. Und da habe ich schon Funktionen implementiert, die Rechtecke und Kreise beachten. Wenn ich jedes Tile prüfe ist es um einiges langsamer als wenn ich anliegende Tiles als Rechteck zusammenfasse.
Ich denke mir auch, dass es noch eine andere Lösung geben sollte. Aber ich wüsste nicht, wie ich anders herangehen sollte. Das ist jetzt das einzige was mir eingefallen ist.

Ich habe den Hauptteil der Funktion jetzt mal so verändert:
BlitzMax: [AUSKLAPPEN] 
	If(r1.fX = (r2.fX + r2.fWidth)) Then
									If(r1.fY = r2.fY) Then 'Gleiche vertikale Position
										DebugLog("At: 1")
                                                        'Neues Rechteck an der Position von r2 erstellen, als Breite die Summe aus den Rechteckbreiten nehmen
										TRectangle.Create(r2.fX + r2.fWidth / 2, r2.fY, r1.fWidth + r2.fWidth, r2.fHeight)
                                                                         'Rechtecke der genutzt Liste hinzufügen
										tlRectsUsed.AddLast(rect1)
										tlRectsUsed.AddLast(rect2)
									EndIf
                                                        'r1 endet dort wo r2 anfängt
								ElseIf(r2.fX = (r1.fX + r1.fWidth)) Then
									If(r1.fY = r2.fY) Then 'Gleiche vertikale Position
										DebugLog("At: 2")
                                                        'Neues Rechteck an der Position von r1 erstellen, als Breite die Summe aus den Rechteckbreiten nehmen
										TRectangle.Create(r1.fX + r1.fWidth / 2, r1.fY, r1.fWidth + r2.fWidth, r1.fHeight)
                                                                            'Rechtecke der genutzt Liste hinzufügen
										tlRectsUsed.AddLast(rect1)
										tlRectsUsed.AddLast(rect2)
									EndIf
                                                        'r2 endet dort, wo r1 anfängt
								ElseIf(r1.fY = (r2.fY + r2.fHeight)) Then
									If(r1.fX = r2.fX) Then 'Gleiche horizontale Position
										DebugLog("At: 3")
                                                        'Neues Rechteck an der Position von r1 erstellen, als Höhe die Summe aus den Rechteckhöhen nehmen
										TRectangle.Create(r1.fX, r2.fY + r2.fHeight / 2, r2.fWidth, r2.fHeight + r1.fHeight)
                                                                             'Rechtecke der genutzt Liste hinzufügen
										tlRectsUsed.AddLast(rect1)
										tlRectsUsed.AddLast(rect2)
									EndIf
                                                        'r1 endet dort, wo r2 anfängt
								ElseIf(r2.fY = (r1.fY + r1.fHeight)) Then
									If(r1.fX = r2.fX) Then 'Gleiche horizontale Position
										DebugLog("At: 4")
                                                        'Neues Rechteck an der Position von r1 erstellen, als Höhe die Summe aus den Rechteckhöhen nehmen
										TRectangle.Create(r2.fX, r1.fY + r1.fHeight / 2, r2.fWidth, r2.fHeight + r1.fHeight)
                                                                             'Rechtecke der genutzt Liste hinzufügen
										tlRectsUsed.AddLast(rect1)
										tlRectsUsed.AddLast(rect2)
									EndIf
								EndIf

Zu beachten sind die Aufrufe von Create. Ich rechne einfach noch die halbe Höhe bzw Breite (je nach Situation) zu der Startposition.
Das funktioniert, fast.
Die Rechtecke sind richtig positioniert. Aber nach 4 bis 5 zusammengefassten Rechtecken in der horizontalen werden die nächsten 4 bis 5 wieder zu einem eigenen zusammengefasst, diese beiden großen jedoch nicht.
In der Vertikalen scheint es diese Einschränkung nicht zu geben.

Die Create Funktion sieht ganz einfach so aus:
BlitzMax: [AUSKLAPPEN] 
Function Create:TRectangle(x:Float, y:Float, width:Float, height:Float)
		Local rect:TRectangle = New TRectangle
		
		rect.fX = x
		rect.fY = y
		rect.fWidth = width
		rect.fHeight = height
		
		Return rect
	End Function


Das ganze (trat) tritt immer auf, egal ob r1 oer r2 weiter vorne liegt.
Nebenbei: in den meisten/allen Fällen werden für die horizontale bzw. vertikale immer nur die erste Möglichkeit genommen, da das Rechteck, das weiter hinten in der Liste liegt auch später erstellt werde und somit weiter rechts/unten liegt.

Lg, M0rgenstern
 

PhillipK

 BeitragDo, März 22, 2012 22:22
Antworten mit Zitat
Benutzer-Profile anzeigen
Hm.
Die beiden großen, zusammengefassten, werden nicht zusammengefasst?
Nun, wenn ich jetzt nicht ganz blöd bin, bist du es! Razz

Solltest du nicht die rückgabe von der Create funktion (das zusammenfassen) nochmal irgendwie abfangen und irgendwo einfügen?
Vorzugsweise eine Zweite tList, welche zusammengefasste zusammenfügt.

Nun habe ich noch eine weitere idee:

Angenommen du hast die Rechtecke 1,2,3.

Sie sind nebeneinander angeordnet - [1][2][3] - sollten also zusammengefasst werden.
Wenn nun 1 und 2 zusammengefasst werden, kommt irgendwann die prüfung zu 2 und 3 dran.
Eventuell interpretierst du das rect |12| als das von |23| ?
Oder arber, wenn du diese zusammenfügt, gibts eben auch einen fehler, das am ende ein rect so breit wie 123+ breite 23/2 auftritt.
Ist eventuell ein wenig verwirrend wie ich das beschreibe, aber man kann leider recht wenig über die arbeitsweise einsehen Very Happy
Vielleicht hilft es dir, wenn du statt X,Y,W,H einfach X1,Y1,X2,Y2 annimst @ Create methode.

Dh:

BlitzMax: [AUSKLAPPEN] 
If(r1.fX = (r2.fX + r2.fWidth)) Then
	If(r1.fY = r2.fY) Then 'Gleiche vertikale Position
		Local newRect = TRectangle.Create2( r1.fX , r1.fY , (r2.fX + r2.fWidth) , (r2.fY + f2.fHeight))
		rectList.addLast(newRect)


-> Create2 sieht dann wie folgt aus:
BlitzMax: [AUSKLAPPEN] 
Function Create:TRectangle(x1:Float, y2:Float, x2Float, y2Float)
		Local rect:TRectangle = New TRectangle
		
		rect.fX = x1
		rect.fY = y1
		rect.fWidth = x2-x1
		rect.fHeight = y2-y1
		
		Return rect
	End Function

M0rgenstern

 BeitragDo, März 22, 2012 22:57
Antworten mit Zitat
Benutzer-Profile anzeigen
Also, es ist so:
In der Create Methode wird das erstellte Rechteck automatisch der Liste aller verfügbaren Rechtecke hinzu. Das heißt, dass dieses neue, größere Rechteck mit anderen geprüft werden kann.

An deinem Beispiel sähe das so aus:
[1][2][3] sind kleine Rechtecke.
Dann werden [1][2] zusammengefasst -> [12][3].
Dieses neue Rechteck [12] wird der Liste hinzugefügt. [1][2] bestehen zwar noch, dürfen aber nicht mehr geprüft werden (abfrage der used list).
Dann werden [12][3] geprüft und zusammengefügt. Dadurch entsteht [123]

Zitat:
Die beiden großen, zusammengefassten, werden nicht zusammengefasst?

Ja, im Prinzip trifft es das.

Dein Tipp den Konstruktor umzubauen habe ich ausprobiert: Das macht das ganze nur noch schlimmer.
Der Aufruf, den du gezeigt hast war übrigens so nicht richtig.
Es hätte so sein müssen:
BlitzMax: [AUSKLAPPEN] 
If(r1.fX = (r2.fX + r2.fWidth)) Then
	If(r1.fY = r2.fY) Then 'Gleiche vertikale Position
		Local newRect = TRectangle.Create2( r2.fX , r2.fY , (r1.fX + r1.fWidth) , (r1.fY + r1.fHeight))
		rectList.addLast(newRect)


Ich habe das ganze mal als Screenshot hochgeladen, damit ihr seht, wie das momentan aussieht. (Man würde in einem fertigen Spiel eigentlich fast nix davon mitbekommen. Aber mich stört es.)

user posted image

Zitat:
Nun, wenn ich jetzt nicht ganz blöd bin, bist du es! Razz

Wer weiß? Vielleicht sind wir es ja beide?^^

Lg, M0rgenstern.

Neue Antwort erstellen


Übersicht BlitzMax, BlitzMax NG Allgemein

Nach Oben

Gehe zu:

Powered by phpBB © 2001 - 2006, phpBB Group