Rechteck-Kollision

[Saul]

Guten Morgen Community,
bin mal wieder auf ein Problem gestoßen und wollte mal eure Meinung dazu hören. Vielleicht habe ich in meinem Ansatz ja einen Denkfehler.
Ich habe hier ne reihe von Rechtecken, die sich ab und an mal überschneiden bzw. andere Rechtecke einschließen.
Nun möchte ich diese Rechtecke die in anderen Rechtecken platziert sind bzw. zum größten Teil von einem anderen Rechteck eingeschlossen sind löschen.
Meine Vorgehensweise:
Ich betrachte immer zwei Rechtecke gleichzeitig. Nun berechne ich die Distanz zwischen den beiden Mittelpunkten. Wenn diese Distanz kleiner als die Breite bzw. die Höhe (da alle Rechtecke quadratisch) des größeren Rechtecks sein sollte, werden alle Werte auf null gesetzt. D.h. das größere der beiden betrachteten Rechtecke soll behalten werden.
Habe dazu mal ein Bild hochgeladen. Dabei sollen die gelben Rechtecke gelöscht werden.
http://img14.imageshack.us/img14/74/rechtecke.jpg

int a, b, manhattanDistanz;
double distanz;

for(int i = 0; i < rectAnz; i++) // rectAnz ist in dem Bild 53
	for(int k = 0; k < rectAnz; k++) 
		if(i != k)
		{
			a = abs(rectStruct.mittelpunktX[i] - rectStruct.mittelpunktX[k]);
			b = abs(rectStruct.mittelpunktY[i] - rectStruct.mittelpunktY[k]);
			manhattanDistanz = a + b;
			distanz = sqrt((double)((a * a) + (b * b)));

			if(rectStruct.width[i] >= rectStruct.width[k])
				//if(manhattanDistanz  < (rectStruct.width[i]*2/3))
				if(distanz < (rectStruct.width[i]/2))
				{
					rectStruct.nummer[k] = 0;
					rectStruct.x[k] = 0;
					rectStruct.y[k] = 0;
					rectStruct.width[k] = 0;
					rectStruct.height[k] = 0;
					rectStruct.mittelpunktX[k] = 0;
					rectStruct.mittelpunktY[k] = 0;
				}
			else if(rectStruct.width[i] < rectStruct.width[k])
				//if(manhattanDistanz  < (rectStruct.width[k]*2/3))
				if(distanz < (rectStruct.width[k]/2))
				{
					rectStruct.nummer[i] = 0;
					rectStruct.x[i] = 0;
					rectStruct.y[i] = 0;
					rectStruct.width[i] = 0;
					rectStruct.height[i] = 0;
					rectStruct.mittelpunktX[i] = 0;
					rectStruct.mittelpunktY[i] = 0;
				}
		}

Vielleicht ist das Problem mit der manhattanDistanz auch eleganter zu lösen??

Nun stehe ich vor einem Problem, denn es werden nicht alle gewünschten Rechtecke "gelöscht". Das liegt an der Distanz bzw. am Vergleich Distanz und Breite in der If-Abfrage. Denn wenn das kleinere Rechteck seinen Mittelpunkt z.B. in der Ecke des größeren Rechtecks hat (z.B. das oberste gelbe Rechteck auf meinem Bild) wird das kleine nicht nicht gelöscht. Somit könnte man die Abfrage ändern in z.B. if(distanz < (rectStruct.width[ ])) anstatt ".width[ ]/2". Nun werden aber auch kleinere Rechtecke gelöscht, die außerhalb neben dem großen Rechteck liegen bzw. nur ein kleines Stück eingeschlossen wird.

Deshalb kam mir eine zweite Idee. Einfach eine Kollisionsabfrage auf den Mittelpunkt des kleineren Rechtecks anzuwenden. D.h. wenn der Mittelpunkt innerhalb bzw. auf dem großen Rechteck liegt soll es gelöscht werden.

for(int i = 0; i < rectAnz; i++)
	for(int k = 0; k < rectAnz; k++) 
		if(i != k)
		{
			if(rectStruct.width[i] >= rectStruct.width[k])
				if((rectStruct.mittelpunktX[k] >= rectStruct.x[i]) 
					&& (rectStruct.mittelpunktX[k] <= (rectStruct.x[i] + rectStruct.width[i])) 
					&& (rectStruct.mittelpunktY[k] >= rectStruct.y[i]) 
					&& (rectStruct.mittelpunktY[k] <= (rectStruct.y[i] + rectStruct.height[i])))
				{
					rectStruct.nummer[k] = 0;
					rectStruct.x[k] = 0;
					rectStruct.y[k] = 0;
					rectStruct.width[k] = 0;
					rectStruct.height[k] = 0;
					rectStruct.mittelpunktX[k] = 0;
					rectStruct.mittelpunktY[k] = 0;
				}
			else if(rectStructTpl.width[i] < rectStructTpl.width[k])
				if((rectStruct.mittelpunktX[i] >= rectStruct.x[k]) 
					&& (rectStruct.mittelpunktX[i] <= (rectStruct.x[k] + rectStruct.width[k])) 
					&& (rectStruct.mittelpunktY[i] >= rectStruct.y[k]) 
					&& (rectStruct.mittelpunktY[i] <= (rectStruct.y[k] + rectStruct.height[k])))
				{
					rectStruct.nummer[i] = 0;
					rectStruct.x[i] = 0;
					rectStruct.y[i] = 0;
					rectStruct.width[i] = 0;
					rectStruct.height[i] = 0;
					rectStruct.mittelpunktX[i] = 0;
					rectStruct.mittelpunktY[i] = 0;
				}
		}

Aber scheinbar habe ich hier nen großen Denkfehler drin. Denn das klappt nicht so wie gewünscht

Hoffe mir kann jemand helfen.

Gruß
Saul

[Heimelchen]

Hab jetzt deinen Code nicht verfolgt, aber ich glaub deine Logik ist nen bissl falsch (währe vielleicht eher was für's Matheforum ;-)).

Wenn deine zwei Rechtecke die gleiche Orientierung haben (also nicht verdreht sind) und die Breite d1 und d2 und die Mittelpunkte m1 und m2, dann liegen diese nicht aufeinander wenn:
m2 - m1 > d1 / 2 + d2 / 2

Das ist jetzt nur eindimensional, müsstest du für die Höhe auch noch umsetzen. Dabei frage ich mich grade, ob es nicht Kongruenzformeln für sowas gibt. Mit Vektorgleichungen oder so...

[Saul]

Hab jetzt nicht genau verstanden was du meinst, aber normal habe ich es meines Wissens mit beachtet.

Beim ersten Code Beispiel ist die Distanz sozusagen die Hälfte der Breite. Die Distanz kann man als Radius eines Kreises sehen der genau im Rechteck liegt.
Und da der Kreis das Rechteck nicht komplett abdeckt, gibt es noch Gegenden im Rechteck, wo die Distanz nicht ausreicht (halt außerhalb vom Kreis, aber immernoch im Rechteck). Sprich im Bereich der Ecken des Rechtecks.

Und im zweiten Codebeispiel habe ich doch in der If-Abfrage ebenfalls Breite und Höhe betrachtet.

rectStruct.mittelpunktX[i] >= rectStruct.x[k])
&& (rectStruct.mittelpunktX[i] <= (rectStruct.x[k] + rectStruct.width[k]))
&& (rectStruct.mittelpunktY[i] >= rectStruct.y[k])
&& (rectStruct.mittelpunktY[i] <= (rectStruct.y[k] + rectStruct.height[k]))

[Heimelchen]

Aber du fragst auf die Mittelpunkte ab. Liegt einer der Mittelpunkte außerhalb der Distanz des anderen, können sich die Rechtecke immernoch überschneiden.

Hab aber grad auf deiner Grafik gesehen, dass das nicht dein Problem ist.
Step dich doch einfach mal durch und guck, was er mit den Rechtecken macht. Vielleicht bearbeitet er die gar nicht...

[Saul]

Heimelchen schrieb:

Aber du fragst auf die Mittelpunkte ab. Liegt einer der Mittelpunkte außerhalb der Distanz des anderen, können sich die Rechtecke immernoch überschneiden.

Genau das meinte ich ja mit:

Saul schrieb:

Nun stehe ich vor einem Problem, denn es werden nicht alle gewünschten Rechtecke "gelöscht". Das liegt an der Distanz bzw. am Vergleich Distanz und Breite in der If-Abfrage. Denn wenn das kleinere Rechteck seinen Mittelpunkt z.B. in der Ecke des größeren Rechtecks hat (z.B. das oberste gelbe Rechteck auf meinem Bild) wird das kleine nicht nicht gelöscht. Somit könnte man die Abfrage ändern in z.B. if(distanz < (rectStruct.width[ ])) anstatt ".width[ ]/2". Nun werden aber auch kleinere Rechtecke gelöscht, die außerhalb neben dem großen Rechteck liegen bzw. nur ein kleines Stück eingeschlossen wird.

Es soll ja auch keine richtige Kollisionsabfrage sein. Heißt Rechtecke sollen sich auch überschneiden dürfen. Nur wenn sie komplett oder zum größten Teil in einem anderen Rechteck liegen sollen sie gelöscht werden. Das Problem sind halt nur die Gegenden wo die Distanz nicht hinreicht, aber der Mittelpunkt trotzdem noch im anderen Rechteck liegt.

Und deswegen hatte ich den Code des zweiten Beispiels programmiert. Aber scheinbar ist der ebenfalls fehlerhaft

Heimelchen schrieb:

Hab aber grad auf deiner Grafik gesehen, dass das nicht dein Problem ist.
Step dich doch einfach mal durch und guck, was er mit den Rechtecken macht. Vielleicht bearbeitet er die gar nicht...

Beziehst du dich jetzt auf das erste oder aufs zweite Beispiel?

[Heimelchen]

Ich bezieh mich auf dein Bild

Im Code springt mich jetzt nichts an, darum würde ich mich an deiner Stelle mal durch den Code steppen (welchen auch immer) bis zu der Stelle, an der die Fehler auftreten. Und dann einfach mal schauen, woran es hapert. Da muss ein Logikfehler drin stecken, ohne Debugger ist sowas aber recht schwierig...

[Heimelchen]

So, wenn ich mir das nochmal so recht anschaue, könnte es auch an folgendem liegen:

Saul schrieb:

if(distanz < (rectStruct.width[i]/2))

Wenn width kleiner 2 ist (und die Rechtecke sehen recht klein aus), ist das Ergebnis 0. Dann wird die Bedingung nie true und das Rechteck bleibt stehen.

[Saul]

Daran kann es nicht liegen, weil solche kleinen Rechtecke bei mir nicht vorkommen.
Die Weite wird in Pixeln angegeben und ist immer ganzzahlig. Kleiner als 2 wäre ja nur 1. Somit wäre 1 ein Punkt und kein Rechteck. Die Punkte fallen bei mir raus.
Das erste Code-Beispiel funktioniert ja eigentlich auch, nur das da nicht das komplette Rechteck betrachtet wird, sondern nur die Reichweite von der Distanz.
Deshalb wollte ich ja nun die zweite Variante nehmen.

Und bei der zweiten Variante finde ich einfach keinen Fehler. Das erscheint mir alles als richtig, aber das Ergebnis passt nicht.

[Heimelchen]

Heimelchen schrieb:

... darum würde ich mich an deiner Stelle mal durch den Code steppen (welchen auch immer) bis zu der Stelle, an der die Fehler auftreten. Und dann einfach mal schauen, woran es hapert. Da muss ein Logikfehler drin stecken, ohne Debugger ist sowas aber recht schwierig...

[Saul]

Ich habe den Fehler endlich gefunden. Er lag an einer ganz anderen Stelle, was noch gar nix mit der Kollisionsabfrage zu tun hatte. ^^
Am Algorithmus war soweit alles richtig. Vielen Dank für deine Bemühungen Heimelchen.
Greetz, Saul