Kleinste euklidische Distanz zwischen 2 Quadraten

[Dirty Oerti]

Tag zusammen

Das folgende Problem könnte auch im Matheboard stehen, ich suche aber ja auch einen Algorithmus, und die Mathematik dahinter steht nicht im Vordergund. Deshalb also hier mein Problem ^^

Die Aufgabe klingt auf den ersten Blick einfach, ich bin bisher aber noch auf keine "gute" Lösung des Problems gekommen.
Es seien zwei Quadrate gegeben.
Die Quadrate sind nicht gedreht, die Seiten sind also entweder parallel oder senkrecht zu jeder Koordinatenachse.
Von jedem Quadrat sind die Koordinaten des Mittelpunkts sowie die Seitenlänge bekannt.

Gesucht ist nun die kürzeste Verbindung dieser beiden Quadrate!
Und das natürlich ohne einfach ein Raster (3x3) um die Quadrate bilden zu müssen.

Ideen? (Schreibt einfach, was euch einfällt. Ich werde dann versuchen zu zeigen, dass die Idee nicht so toll ist Und bei einer Idee kann ich das dann hoffentlich nicht zeigen .. )

[Xin]

Tag zusammen

Das folgende Problem könnte auch im Matheboard stehen, ich suche aber ja auch einen Algorithmus, und die Mathematik dahinter steht nicht im Vordergund. Deshalb also hier mein Problem ^^

Ich überlege auch noch, es zu verschieben... schauen wir mal, wie es sich entwickelt.

Die Aufgabe klingt auf den ersten Blick einfach, ich bin bisher aber noch auf keine "gute" Lösung des Problems gekommen.
Es seien zwei Quadrate gegeben.
Die Quadrate sind nicht gedreht, die Seiten sind also entweder parallel oder senkrecht zu jeder Koordinatenachse.

Wo ist dann das Problem? ^^

Von jedem Quadrat sind die Koordinaten des Mittelpunkts sowie die Seitenlänge bekannt.

Gesucht ist nun die kürzeste Verbindung dieser beiden Quadrate!
Und das natürlich ohne einfach ein Raster (3x3) um die Quadrate bilden zu müssen.

Raster? Wie stellst Du Dir das vor?

Ideen? (Schreibt einfach, was euch einfällt. Ich werde dann versuchen zu zeigen, dass die Idee nicht so toll ist Und bei einer Idee kann ich das dann hoffentlich nicht zeigen .. )

Man bilde einen Vektor von Mittelpunkt 1 zu Mittelpunkt2.
Bei einem Quadrat wäre die Sonderbedingung, dass ein Quadrat im anderen liegt oder die Quadrate gleichgroß sind und den gleichen Mittelpunkt haben.

Mit dem Vektor hast Du die Richtung, die Dir angibt, welche der vier Kanten (begrenzte Geraden, die Linien enden ja an den Ecken) geschnitten wird. Anschließend nimmst Du die Entfernungen der beiden geschnittenen Kanten und testest, ob die Segmente nebeneinander liegen. In dem Fall ist es die gerade Entfernung zwischen den Segmenten, die rechtwinklig zur Richtung der Kanten verläuft.
Anderenfalls ist die kürzeste Entfernung von einem Ende der Kante zum anderen Ende der Kante. Hier macht es wohl wenig Sinn, die Ecken analytisch zu bestimmen, weil es vermutlich schneller ist, alle vier Möglichkeiten auszurechnen und die kürzeste Entfernung herauszusuchen.

[AnGaiNoR]

Ich hab mal eine Lösung zusammengewerkelt (in C). Kannst sie dir ja mal durcharbeiten und dann bewerten. ^^

Code: Alles auswählen

#include <math.h>

#define SQUARE(x) ((x)*(x))
#define MIN(a,b) ((a<b)?a:b)
#define MIN4(a,b,c,d) (MIN(MIN(a,b), MIN(c,d)))

// Struktur für ein Rechteck
struct Rectangle
{
	// Koordinaten
	double left, top, right, bottom;
};

// Funktion, die den Abstand der Rechtecke ermittelt
double rectangleDistance (struct Rectangle const* r1, struct Rectangle const* r2)
{
	// Lage ermitteln und Abstand errechnen
	double dist;
	if ( r1->bottom < r2->top ) // r1 über r2
	{
		if ( r1->right < r2->left ) // r1 links über r2
		{
			dist = sqrt( SQUARE( r2->left - r1->right )
					+ SQUARE( r2->top - r1->bottom ) );
		}
		else if ( r2->right < r1->left ) // r1 rechts über r2
		{
			dist = sqrt( SQUARE( r1->left - r2->right )
					+ SQUARE( r2->top - r1->bottom ) );
		}
		else // r1 über r2
		{
			dist = r2->top - r1->bottom; 
		}
	}
	else if ( r2->bottom < r1->top ) // r1 unter r2
	{
		if ( r1->right < r2->left ) // r1 links unter r2
		{
			dist = sqrt( SQUARE( r2->left - r1->right )
					+ SQUARE( r1->top - r2->bottom ) );
		}
		else if ( r2->right < r1->left ) // r1 rechts unter r2
		{
			dist = sqrt( SQUARE( r1->left - r2->right )
					+ SQUARE( r1->top - r2->bottom ) );
		}
		else // r1 unter r2
		{
			dist = r1->top - r2->bottom; 
		}
	}
	else
	{
		if ( r1->right < r2->left ) // r1 links von r2
		{
			dist = r2->left - r1->right;
		}
		else if ( r2->right < r1->left ) // r1 rechts von r2
		{
			dist = r1->top - r2->bottom;
		}
		else // r1 und r2 liegen ineinander
		{
			// alle Kantenabstände ermitteln (Vorzeichen positiv, wenn Kante von r1 in r2)
			double top = r1->top - r2->top, bottom = r2->bottom - r1->bottom,
					left = r1->left - r2->left, right = r2->right - r1->right;
					
			// wenn sich die Vorzeichen irgendwo unterscheiden, dann schneiden sich r1 und r2
			if ( top*bottom < 0 || top*left < 0 || top*right < 0
					|| bottom*left < 0 || bottom*right < 0 || left*right < 0 )
			{
				dist = 0.0;
			}
			else // eines der Rechtecke liegt im anderen
			{
				// niedrigste Kantendistanz zurückgeben
				dist = abs( MIN4( top, bottom, left, right ) );
			}
		}
	}
	
	// Distanz zurückgeben
	return dist;
}

[detewe89]

Habe einen ähnliche Algorithmus, poste ihn hier mal:

Beispielhaft für x-Achse; für y (und z bei Würfeln) gleiches Spiel
--------------------------------------------------------------------------------
i) Mittelpunktskoordinaten gleich? => setze x = 0 , fertig

ii) SONST: Welches Rechteck ist links, welches rechts?

iii) Berechne linke Seitenkoordinate (=x1) von rechtem Quadrat und rechte Seitenkoordinate (=x2) von linkem Quadrat.

iv) x1 - x2 < 0 => x = 0 , fertig (da dann ja die Seiten "nebeneinander" liegen)

v) SONST: x = x1 - x2
--------------------------------------------------------------------------------

Gleiches Spiel für y-Achse, und dann ist der Abstand der Betrag des Vektors d = (x , y): betrag(d) = sqrt(x^2 + y^2).


LG
Daniel

[Dirty Oerti]

Hm, beide Algorithmen stimmen, soweit ich das beurteilen kann.
Jedoch bauen beide auf der Idee eines 3x3 Rasters auf.

Ihr beide vergleicht zu nächst die x-Werte, so dass dabei 3 unterschiedliche Ergebnisse (links, rechts, gleich) herauskommen können.
Dazu vergleicht ihr noch die y-Werte, wobei wieder 3 unterschiedliche Ergebnisse (oben, unten, gleich) möglich sind.
Also ein 3x3 Raster.

Über diese Methode habe ich es nun auch implementiert. Damit ich schon mal was dastehen hab.

Was mir dann noch eingefallen ist:

Der Fall, dass das Quadrat (ich nenn es mal Q2, also nicht "ich" ) links von mir ist kann ja eigentlich dadurch gelöst werden, in dem man Q2 an mir spiegelt. Dann ist Q2 rechts von mir.
Das gleiche könnte man auch auf oben-unten anwenden, und so sozusagen alle möglichen Quadrate in einen "Quadranten" des 2D-Raumes bekommen.
Dann blieben dafür nur noch 3 Möglichkeiten (genau rechts von mir, rechts unten von mir, genau unten von mir aus)
Sind also 2 mal Spiegeln und 3 mal Vergleichen.

Ist die Frage, ob das etwas bringt?

[Xin]

Dann blieben dafür nur noch 3 Möglichkeiten (genau rechts von mir, rechts unten von mir, genau unten von mir aus)
Sind also 2 mal Spiegeln und 3 mal Vergleichen.

Ist die Frage, ob das etwas bringt?

Um zu spiegeln musst Du herausfinden, ob Du spiegeln musst. Mit dieser Erkenntnis kannst Du auch gleich den Wert nehmen.

Wenn Du eine universellere Lösung haben willst, muss Du wirklich den Vektor nehmen und alle Kanten prüfen, ob sie geschnitten werden. Anschließend musst Du den minimalen Abstand der beiden Kanten bestimmen.

Das 3x3 Raster versucht lediglich die Anzahl der Prüfungen zu optimieren, in dem einfacher zu beantwortende Fragen gestellt werden.
Beides sind korrekte Algorithmen. Die universelle Antwort ist hier aber aufwendiger.

[Dirty Oerti]

Um zu spiegeln musst Du herausfinden, ob Du spiegeln musst. Mit dieser Erkenntnis kannst Du auch gleich den Wert nehmen.

Ja, da hast du Recht.
Aber: Ich spiegle nun mal alles, was sich links von "mir" befindet. Also einen kleineren x-Wert (ich habe den Mittelpunkt angegeben) hat als ich (ob sich das andere Quadrat mit mir schneidet oder nicht ist mir dabei egal). Das ist also ein Vergleich.
Das gleiche mach ich noch an der y-Achse mit allem, was dann rechts (da ist es dann ja sicher) unter mir liegt.
Dann hab ich 2 Vergleiche angewandt und hab das Quadrat mit Sicherheit "rechts oben" von mir aus.
"rechts oben" heißt, dass es ...

- WIRKLICH rechts oben,
- wirklich rechts von mir aber nur "teilweise über mir",
- "teilweise rechts von mir" aber wirklich über mir,
- "teilweise rechts von mir" und "teilweise über mir", also "in mir" ist.

Sind also 4 Fälle, die ich angeben muss.
Für die 4 Fälle brauch ich aber nur 2 Vergleiche (jeweils 1 an der x und y Achse)

Ich komm also insgesamt mit 4 Vergleichen weg...

... Wenn ich mir meinen Code aber mal anguck ... da hab ich auch "nur" 6 Vergleiche. (Obwohl if, elseif, else und in jedem der drei Blöcke noch mal if,elseif,else - zugegeben, der Code könnte besser aufgebaut sein)

Im Allgemeinen Fall wird mir das Spiegeln natürlich wenig bringen.
Da wird es wirklich das Klügste sein, Kanten zu suchen...