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

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: \ -