Prüfen, ob eine Strecke ein Quadrat schneidet

Wie mache ich das am schnellsten?

Im Moment ist die Überlegung so, dass ich die Kanten des Quadrats zu einer Seite verlänger und den Schnittpunkt mit der Strecke bestimme. Anschließend, wird der Abstand zwischen dem Eckpunkt und dem Schnittpunkt bestimmt.

Das Quadrat ist durch den Mittelpunkt und seinen "Radius" definiert (womit es natürlich möglich ist, die Eckpunkte auszurechnen).
Die Strecke ist durch die zwei Endpunkte definiert.
Siehe Bild.

Gibt es noch eine bessere Möglichkeit? Davon gehe ich mal aus
Mit Google hab ich zur Zeit noch nichts gefunden.

P.S. Ich weiss noch nicht mal sicher, ob die jetzige Methode überhaupt immer funktioniert.

SnorreDev

http://www.cfxweb.net/~cfxamir/tutorials.html - schau dir das an. Eine Plane hilft dir wohl nicht, da dein Bereich nicht Infinite ist. Wirst wohl um Ray / Triangle collision drumrumkommen.

Irgendwie kann ich das nicht so einsetzen wie ich es brauche (vielleicht bin ich auch zu dumm dafür ).

Andere Frage: Wie kann ich _performant_ prüfen, ob zwei Strecken einen Schnittpunkt haben?
Dann mach ich des halt für alle vier Seiten des Quadrats. Das dürfte deutlich einfacher sein.

Bei Geraden wäre es kein Problem, da müsste ich nur prüfen, ob sie kolinear sind. Bei Strecken ist das schon kniffliger...
Eine Strecke ist nach wie vor durch zwei Punkte bzw. einen Punkt und einen Vektor (was halt günstiger ist) definiert.

thx schon mal

rofl, ich hätt doch Java nehmen sollen:
http://www.yworks.com/products/yfiles/doc/api/y/geom/LineSegment.html#contains(y.geom.YPoint)

TGGC

Ich hoffe das macht die Erklärug etwas sinnvoller: http://www.fh-merseburg.de/~roesch/trash/quadrat.jpg (Strecke würde hier waagrerecht liegen.)

Erst mal erstellst du eine Gerade, in welcher die Strecke liegt. Jetzt errechnest du den Abstand vom Mittelpunkt des Quadrats zur Strecke (das hatten wir letztens?!) und nun kann der Schnitt schonmal nur stattfinden, wenn die Gerade in einem gewissen Bounding-Quadrat um das Quadrat liegt. Dessen Grösse hängt davon ab, wie gross das Quadrat ist und welcher Winkel zwischen Gerade und Quadrat liegt (Im Bild sieht man, bei alpha = 45° ist es am grössten). Das Quadrat ist a + b gross, also cos alpha + sin alpha, logisch. Liegt die Gerade ausserhalb des Quadrats (also Abstand von Mitte > Breite / 2) kann keine Kollision stattfinden.

Jetzt erstellst du senkrechte Geraden (zu deiner Strecke), die durch Anfangs- und Endpunkt deiner Strecke gehen, und errechnest wieder deren Abstand zum Mittelpunkt. Liegen jetzt beide ausserhalb, aber auf der selben Seite (Abstand hat gleiches Vorzeichen), so gibt es keine Kollision. Liegen beide auf unterschiedlichen Seiten, so gibt es eine Kollision. Liegt einer innerhalb, kommst du um die Line-Line Intersection mit allen Kanten des Quadrats nicht herum. Aber dafür gibts auch optimierte Algos im Netz, google anwerfen...

Bye, TGGC

hmmm hab vergessen zu sagen, dass das Quadrat immer an den Koordinatenachsen ausgerichtet ist.

Ich hab gestern um halb vier ( ) ne Funktion gefunden, die prüft, ob sich zwei Strecken schneiden (so wie du beschrieben hast mit Vorzeichen). Sobald ich sie in C++ übersetzt habe, werde ich damit alle 4 Seiten des Quadrats prüfen.
Und ich hab mir das auch so gedacht, erstmal zu prüfen, ob die Entfernung Mittelpunkt des Quadrats - Strecke kleiner gleich 1,4143 ist.
Ich weiß aber nicht, ob sich das lohnt, weil ich dazu die Wurzel ziehen muss.

TGGC

hmmm hab vergessen zu sagen, dass das Quadrat immer an den Koordinatenachsen ausgerichtet ist.

Macht nix. Dann kann man alpha noch einfacher berechnen.

Und ich hab mir das auch so gedacht, erstmal zu prüfen, ob die Entfernung Mittelpunkt des Quadrats - Strecke kleiner gleich 1,4143 ist.
Ich weiß aber nicht, ob sich das lohnt, weil ich dazu die Wurzel ziehen muss.

Wofür die Wurzel? Optimier das mal!

Bye, TGGC

class PointFloat
{
[...]

	// Berechnet die quadratische Entfernung zwischen zwei Punkten.
    float getDisToPointSquare(const PointFloat &other)
	{
		const float distanceX = other.x - x;
		const float distanceY = other.y - y;

		return distanceX*distanceX + distanceY*distanceY;
	}

	// Berechnet die korrekte Entfernung zwischen zwei Punkten.
	float getDisToPointNormal(const PointFloat &other)
	{
		return sqrtf(getDisToPointSquare(other));
	}

	// Berechnet das Innenprodukt der beiden Vektoren.
	float getDotProduct(PointFloat &other)
	{
		return x * other.x  +  y * other.y;
	}

	// Berechnet die kürzeste Entfernung des Punkts
	// zu einer aus zwei Punkten gegebenen Strecke.
	inline float getDistanceToSegment(const PointFloat &rStartPoint, const PointFloat &rEndPoint)
	{	
		PointFloat v = rEndPoint - rStartPoint;
		PointFloat w = *this     - rStartPoint;

		const float c1 = w.getDotProduct(v);
		if (c1 <= 0)
			return getDisToPointNormal(rStartPoint);

		const float c2 = v.getDotProduct(v);
		if (c2 <= c1)
		   return getDisToPointNormal(rEndPoint);

		const float b = c1 / c2;
		PointFloat Pb(rStartPoint.x + b * v.x, rStartPoint.y + b * v.y);
		return getDisToPointNormal(Pb);
	}
[...]
}

IMO kann man auf die Wurzel nicht verzichten, wenn man die korrekte Entfernung haben will. Ich lasse mich aber gerne eines besseren belehren.

Außerdem werde ich mal prüfen, ob mir die quadratische Entfernung reicht...
nach dem Motto: Entfernung(Strecke, Mittelpunkt der Box) <= (sqrt(2))^2 [== 2]

rapso

wie hoch ist die wahrscheinlichkeit, dass eine box geschnitten wird?

rapso->greets();

Hmmmm nicht zu gering würde ich sagen. Hindernisse werden zunächst nur in Zielrichtung erfasst, deshalb sind es meistens alles Boxen, die ne hohe Wahrscheinlichkeit haben, im Weg zu liegen.

(Für die, die es nicht wissen, es geht um Wegfindung)