Was mir so einfällt

Teil 1 – Einführung
Teil 2 – Kollision mit Gerade
Teil 2 – Kollision mit Gerade – Demoprogramm
Teil 3 – Kollision mit Strecke
Teil 3 – Kollision mit Strecke – Demoprogramm

Übersicht:

1. Problem
2. Lösungsansatz
3. Die Lösung
4. Geradenschnittpunkt
5. Parametergleichung umgekehrt
6. Ende und Demo

Das Problem

Beim Herumspielen mit dem Demoprogramm fällt schnell auf, was wir noch beachten müssen. Die Kollision wird selbst dann berechnet, wenn die Bewegung gänzlich außerhalb der Begrenzungskante verläuft, wie hier veranschaulicht:

Dabei wäre die unkorrigierte Zielposition die korrekte. Wir müssen also entscheiden, ob eine Bewegung eine Begrenzungskante berührt oder nicht.
Dazu könnten wir einfach den Schnittpunkt der Geraden und bestimmen und überprüfen, ob dieser innerhalb der Strecke zwischen und liegt. Wenn nicht, wird keine Kollisionserkennung durchgeführt. Allerdings würde dann folgendes passieren:

Der Schnittpunkt liegt außerhalb der Strecke zwischen und und eine Kollisionserkennung würde nicht durchgeführt werden.
Allerdings findet eine Kollision statt, wie der rote Kreis verdeutlicht.

Lösungsansatz

Dadurch dass wir nicht nur eine Kollision für einen Punkt sondern für Kreise berechnen wollen, müssen wir auch die äußeren Begrenzungslinien der Bewegung daraufhin überprüfen, ob die Bewegung mit der Begrenzungskante kollidiert:

Die Punkte , , und spannen ein Rechteck auf, welches die Bewegung vollständig erfasst. Jetzt muss überprüft werden ob einer der Schnittpunkte und zwischen und liegen. Zusätzlich kann es noch einen Schnittpunkt geben, der durch die Strecke , entsteht. Für diesen muss die Überprüfung auch durchgeführt werden.
Sollte das einer der Schnittpunkte zwischen und liegen, ist eine Kollision mit der Begrenzungskante eingetreten, die erkannt und korrigiert werden muss.

Die Lösung

Zuerst müssen allerdings die Punkte , , und berechnet werden. Das ist relativ einfach:

Wie prüft man nun, ob zwei Strecken sich kreuzen? Erstmal sollte man überprüfen, ob sich die beiden Geraden die durch die beiden Strecken aufgespannt werden überschneiden. Sollte das der Fall sein kann man an Hand des Schnittpunktes, testen ob dieser innerhalb der beiden Strecken liegt.
Alle Punkte auf einer Strecke zwischen und sind durch die Parametergleichung

bestimmt.
Haben wir den Schnittpunkt der beiden Geraden also erst einmal gefunden, müssen wir für diesen Punkt nur noch den Parameter für beide Strecken bestimmen. Liegen beide Parameter innerhalb des Intervals , so kreuzen sich die Strecken:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

bool TestBoundedMovement::DoLineSegmentsIntersect( sf::Vector2f s1, sf::Vector2f e1, 
	sf::Vector2f s2, sf::Vector2f e2 )
{
	sf::Vector2f v1 = e1 - s1;
	sf::Vector2f v2 = e2 - s2;
	sf::Vector2f intersection;
	if ( LinesIntersection( s1, v1, s2, v2, intersection ) ) {
		float k = LineParam( s1, v1, intersection );
		float m = LineParam( s2, v2, intersection );
		if( ( m >= 0 ) && ( m <= 1 ) &&
			( k >= 0 ) && ( k <= 1 ) ) {
			return true;
		} else {
			return false;
		}
	}  else 
		return false;
}

Geradenschnittpunkt

Die mathematischen Hintergründe für die Berechnung eines Geradenschnittpunktes sind hier zu finden : Schnittpunkt zweier Geraden

Daraus ergibt sich folgender Programmcode:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

bool TestBoundedMovement::LinesIntersection( sf::Vector2f s1, sf::Vector2f v1, 
	sf::Vector2f s2, sf::Vector2f v2, sf::Vector2f &intersection )
{
	if( v1.x != 0 ) {
		float a = v2.x * v1.y / v1.x - v2.y;
		if( a != 0 ) {
			float m = ( s2.y - s1.y - ( s2.x - s1.x ) * v1.y / v1.x ) / a;
			intersection.x = s2.x + m * v2.x;
			intersection.y = s2.y + m * v2.y;
			return true;
		} else {
			return false;
		}
	} else {
		if ( v2.x != 0 ) {
			float m = ( s1.x - s2.x ) / v2.x;
			intersection.x = s2.x + m * v2.x;
			intersection.y = s2.y + m * v2.y;
			return true;
		} else {
			return false;
		}
	}
}

Parametergleichung umgekehrt

Möchte man den Parameter aus der Parametergleichung eines Punktes auf einer Geraden berechnen, muss man diese nur umstellen. Auf Grund der Trivialität dieses Vorgangs lasse ich die mathematischen Hintergründe hier ganz außen vor. Folgender Quellcode ergibt sich:

1
2
3
4
5
6
7
8
9
10

float TestBoundedMovement::LineParam( sf::Vector2f s, sf::Vector2f v, sf::Vector2f p )
{
	float k = 0;
	if( v.y != 0 ) {
		k = (p.y - s.y) / v.y;
	} else if ( v.x != 0 ) {
		k = (p.x - s.x) / v.x;
	}
	return k ;
}

Ende und Demo

Nun muss nur noch die Überprüfung für die beiden Strecken eingebaut werden:

//...
if( ! DoLineSegmentsIntersect( s + nh0 * r, z + v0 * r + nh0 * r, pl1, pl2 ) &&
    ! DoLineSegmentsIntersect( s - nh0 * r, z + v0 * r - nh0 * r, pl1, pl2 ) &&
    ! DoLineSegmentsIntersect( z + v0 * r + nh0 * r, z + v0 * r - nh0 * r, pl1, pl2 )) {
	//Bewegungslinie und BoundLine überschneiden sich nicht,
	//also wird keine Kollisionserkennung vorgenommen,
	//also ist myCircleCorrectDest = myCircleDest
	myCircleCorrectDest.SetPosition( z );
	return;
}
//...

Dazu gibt es wieder ein Demonstrationsprogramm:
Demonstrationsprogramm zu diesem Teil