Algorithmus, um zu prüfen, ob sich zwei Linien schneiden??

SFandler

Hallo,

Ich versuche zu prüfen, ob sich ein Punkt in einem Rechteck befindet.

Gegeben ist der Punkt P(10,10) und das Rechteck ( (0,0),(10,0),(10,10),(0,10) ).

Ich habe gestern schon nach einem Alghoritmus gesucht, der prüft, ob sich der Punkt
P im Rechteck befindet.
Gefunden habe ich eine Methode, wo man eine Linie von P (10,10) bis Q (1000,1000)
( also Q hat irgendwelche x und y Koordinaten, die Linie muss nur lange genug sein ).
Wenn man die Linie gezogen hat, prüft man, ob diese Linie die Seiten des Rechtecks
schneidet ( also insgesamt 4x ). Jedes mal, wenn sie sich schneiden, erhöhe ich eine Variable,
die ich am Beginn auf 0 gesetzt habe, um 1. Wenn diese Variable nach
der Überprüfung ungerade ist, befindet sich der Punkt im Rechteck.

Mein Problem ist, wie ich prüfe, ob sich diese Linien schneiden ..
Ich habe bereits einen Algorithums gefunden, aber der
arbeitet nicht richtig.

// DAS IST DIE FUNKTION, DIE PRÜFT, OB SICH ZWEI LINIEN SCHNEIDEN:
// TRUE: schneiden sich
bool lineIntercept ( float Line1XStart, float Line1YStart, float Line1XEnd, float Line1YEnd, float Line2XStart, float Line2YStart, float Line2XEnd, float Line2YEnd )
{
	float U1;
	float Numerator, Denominator;

	Numerator = (((Line2XEnd - Line2XStart) * (Line1YStart - Line2YStart)) - ((Line2YEnd - Line2YStart) * (Line1XStart - Line2XStart))) ;
	Denominator = (((Line2YEnd - Line2YStart) * (Line1XEnd - Line1XStart)) - ((Line2XEnd - Line2XStart) * (Line1YEnd - Line1YStart))) ;

	U1 = Numerator / Denominator ;

	if ( ( Numerator == 0.0 ) && ( Denominator == 0.0 ) )
	{
		// Linien sind gleich
		return true;
	}

	if ( Denominator == 0.0 )
	{
		// Linien sind Parallel
		return false ;
	}

	if ( ! ( U1 > 0.0 && U1 < 1.0 ) )
	{
		// Kein Schnittpunkt
		return false ;
	}

	return true ;
}

// HIER WIRD GEPRÜFT OB DER PUNKT INNERHALB DES RECHTECKS IST:
    if ( lineIntercept ( ball -> x, ball -> z, ball -> x + 1050, ball -> z + 1000, Object::x1, Object::z1, Object::x2, Object::z2 ) )
		lic ++;		
	if ( lineIntercept ( ball -> x, ball -> z, ball -> x + 1050, ball -> z + 1000, Object::x2, Object::z2, Object::x3, Object::z3 ) )
		lic ++;				
	if ( lineIntercept ( ball -> x, ball -> z, ball -> x + 1050, ball -> z + 1000, Object::x3, Object::z3, Object::x4, Object::z4 ) )
		lic ++;			
	if ( lineIntercept ( ball -> x, ball -> z, ball -> x + 1050, ball -> z + 1000, Object::x4, Object::z4, Object::x1, Object::z1 ) )
		lic ++;

	// if lic is odd, the ball centre is in the rectangle
	if ( lic % 2 == 1 )
	{
		// the ball is on the platform
		return true;
	}

Kann sich das bitte jemand angucken?

Lg
SFandler

SeppJ

Warum so kompliziert? Wenn Koordinaten größer als linke untere Ecke und kleiner als rechte obere Ecke, dann liegt der Punkt im Rechteck.

SFandler

Das mit den 0 und 10er x und y Koordinaten war nur ein Beispiel.
Ich will das auch bei Rechtecken überprüfen, die nicht parallel zu einer x- oder y-Achse sind.

Guck mal hier: http://softsurfer.com/algorithm_archive.htm

SFandler

Danke, die Seite sieht interessant aus, aber ich bräuchte "nur" den Algorithmus, um zu berrechnen, ob sich zwei Geraden schneiden/ kreuzen.

Lg
SFandler

SFandler

Ok ich habe weiter gesucht und etwas gefunden.
Sehr kompliziert, aber Hauptsache ist, dass es funktioniert

static bool IsOnSegment(double xi, double yi, double xj, double yj,
                        double xk, double yk) {
  return (xi <= xk || xj <= xk) && (xk <= xi || xk <= xj) &&
         (yi <= yk || yj <= yk) && (yk <= yi || yk <= yj);
}

static char ComputeDirection(double xi, double yi, double xj, double yj,
                             double xk, double yk) {
  double a = (xk - xi) * (yj - yi);
  double b = (xj - xi) * (yk - yi);
  return a < b ? -1 : a > b ? 1 : 0;
}

/** Do line segments (x1, y1)--(x2, y2) and (x3, y3)--(x4, y4) intersect? */
bool DoLineSegmentsIntersect(double x1, double y1, double x2, double y2,
                             double x3, double y3, double x4, double y4) {
  char d1 = ComputeDirection(x3, y3, x4, y4, x1, y1);
  char d2 = ComputeDirection(x3, y3, x4, y4, x2, y2);
  char d3 = ComputeDirection(x1, y1, x2, y2, x3, y3);
  char d4 = ComputeDirection(x1, y1, x2, y2, x4, y4);
  return (((d1 > 0 && d2 < 0) || (d1 < 0 && d2 > 0)) &&
          ((d3 > 0 && d4 < 0) || (d3 < 0 && d4 > 0))) ||
         (d1 == 0 && IsOnSegment(x3, y3, x4, y4, x1, y1)) ||
         (d2 == 0 && IsOnSegment(x3, y3, x4, y4, x2, y2)) ||
         (d3 == 0 && IsOnSegment(x1, y1, x2, y2, x3, y3)) ||
         (d4 == 0 && IsOnSegment(x1, y1, x2, y2, x4, y4));
}

SeppJ

SFandler schrieb:

Danke, die Seite sieht interessant aus, aber ich bräuchte "nur" den Algorithmus, um zu berrechnen, ob sich zwei Geraden schneiden/ kreuzen.

Das ist immer noch viel zu kompliziert. Sei A eine Ecke, B und C zwei andere die nicht diagonal gegenüber von A liegen. P sei dein Punkt. Dann und genau dann wenn (P-A).(B-A) < |B-A| und (P-A).(C-A) < |C-A|, dann ist der Punkt im Rechteck, für beliebige Rechtecke (sogar für beliebige Rauten). Dabei ist . das Skalarprodukt. Das sind 4 Subtraktionen, 4 Multiplikationen, 2 Additionen, 2 Vergleiche und 2 Längenberechnungen (die man eventuell schon vorher erledigen kann).

SeppJ schrieb:

Dann und genau dann wenn (P-A).(B-A) < |B-A| und (P-A).(C-A) < |C-A|, dann ist der Punkt im Rechteck, für beliebige Rechtecke (sogar für beliebige Rauten).

"(P-A).(B-A) < |B-A|"

Die Projektion des Vektors P-A auf die Dreieckskante B-A ist kürzer als eben diese Kante.
Ziemlich klug.

knivil

Gefunden habe ich eine Methode, [..] Wenn diese Variable nach
der Überprüfung ungerade ist, befindet sich der Punkt im Rechteck.

Ja das geht. Nennt sich Strahltest und ist fuer beliebige Polygone geeignet. Aber es geht viel einfacher. Dreiecke und Vierecke sind konvexe Polygne. Es reicht, fuer jede Seite zu testen, ob der Punkt links von ihr liegt (wenn das Polydon gegen den Uhrzeigersinn gegeben ist). Um das zu pruefen benoetigt man nur das Skalarprodukt. Eine moegliche Punktklasse fuer 2D in C++ ist hier: point.h bzw. point.cpp.

Will man beispielsweise wissen, ob der Punkt P innerhalb des Vierecks A,B,C,D liegt, reicht es:

P.leftOf(A,B) && P.leftOf(B,C) && P.leftOf(C,D) && P.leftOf(D,A)

@knivil: Allgemein sind Vierecke aber nicht konvex

Werner Salomon

SeppJ schrieb:

Sei A eine Ecke, B und C zwei andere die nicht diagonal gegenüber von A liegen. P sei dein Punkt. Dann und genau dann wenn (P-A).(B-A) < |B-A| und (P-A).(C-A) < |C-A|, dann ist der Punkt im Rechteck, für beliebige Rechtecke (sogar für beliebige Rauten). Dabei ist . das Skalarprodukt. Das sind 4 Subtraktionen, 4 Multiplikationen, 2 Additionen, 2 Vergleiche und 2 Längenberechnungen (die man eventuell schon vorher erledigen kann).

Die oben angegebene Bedingung ist falsch. Sie ist schon deshalb falsch, weil links eine Fläche und rechts eine Länge steht - das lässt sich nicht vergleichen. Korrekt wäre:
0 <= (P-A)x(C-A) <= (B-A)x(C-A)
0 <= (B-A)x(P-A) <= (B-A)x(C-A)
wobei x das Kreuzprodukt ist und (B-A)x(C-A)>0.
Das gilt für alle Parallelogramme ABDC - mit D=B+C-A.

Gruß
Werner

SeppJ

Stimmt, rechts fehlt ein Quadrat:
(P-A).(B-A) < |B-A|²
(P-A).(C-A) < |C-A|²

Warum?
Was stimmt an obiger Erklärung von mir nicht?

Und warum sollte links eine Fläche stehen, es ist doch das Skalarprodukt.

SeppJ

Damit die Erklärung stimmt, braucht man die Länge der orthogonalen Projektion des Punktes auf die Außenlinien. Damit die Länge passt, muss man aber noch den Vektor auf den projiziert wird normieren. Sonst käme z.B. wenn man (1,1) auf (2,0) projiziert 2 heraus, nicht 1. Daher muss noch durch die Länge des aufprojizierten Vektors geteilt werden oder, wie in meinem letzten Beitrag, an die andere Seite multipliziert werden (das macht die Rechnung sogar wesentlich einfacher, weil man dann keine Wurzeln ziehen braucht).

Und angenommen, du hast zwei Vektoren (1m, 2m) und (3m, 4m), dann ist das Skalarprodukt 11m². Steht m für eine Länge , so ist das eine Fläche.

joerider

Dumme Frage: warum überprüfst Du nicht die lineare Abhängigkeit der Vektoren?
Wenn sie lin. abhängig sind, dann handelt es sich entweder um parallele Geraden, oder es handelt sich um dieselbe Gerade.
Wenn sie lin. unabhängig sind, schneiden sich die Geraden.

CStoll

joerider schrieb:

Dumme Frage: warum überprüfst Du nicht die lineare Abhängigkeit der Vektoren?
Wenn sie lin. abhängig sind, dann handelt es sich entweder um parallele Geraden, oder es handelt sich um dieselbe Gerade.
Wenn sie lin. unabhängig sind, schneiden sich die Geraden.

Weil es hier nicht um Geraden geht, sondern um Strecken Und die können auch so liegen, daß sie einander Verfehlen - wie z.B. diese beiden: \ -