Fixed missing edge cases in line to line intersection function.

[architektonas] / src / geometry.cpp

diff --git a/src/geometry.cpp b/src/geometry.cpp
index eacaec7feabc20ee4b8cddce4a15e538f2905bd4..cfb051101c94498c1e026bacc7a2a58379d7f0ec 100644 (file)
--- a/src/geometry.cpp
+++ b/src/geometry.cpp
@@ -15,8 +15,9 @@
 
 #include "geometry.h"
 #include <math.h>
-#include "line.h"
 #include "circle.h"
+#include "dimension.h"
+#include "line.h"
 
 
 Point Geometry::IntersectionOfLineAndLine(Point p1, Point p2, Point p3, Point p4)
@@ -128,18 +129,57 @@ int Geometry::Intersects(Line * l1, Line * l2, double * tp/*= 0*/, double * up/*
 {
        Vector r(l1->position, l1->endpoint);
        Vector s(l2->position, l2->endpoint);
-       Vector v1 = l2->position - l1->position;
-//     Vector v1 = l1->position - l2->position;
-
+       Vector v1 = l2->position - l1->position;        // q - p
+//     Vector v2 = l1->position - l2->position;        // p - q
+//printf("l1: (%lf, %lf) (%lf, %lf), l2: (%lf, %lf) (%lf, %lf)\n", l1->position.x, l1->position.y, l1->endpoint.x, l1->endpoint.y, l2->position.x, l2->position.y, l2->endpoint.x, l2->endpoint.y);
        double rxs = (r.x * s.y) - (s.x * r.y);
+       double t, u;
 
        if (rxs == 0)
-               return 0;
+       {
+               double qpxr = (v1.x * r.y) - (r.x * v1.y);
 
-       double t = ((v1.x * s.y) - (s.x * v1.y)) / rxs;
-       double u = ((v1.x * r.y) - (r.x * v1.y)) / rxs;
+//printf("  --> R x S = 0! (q - p) x r = %lf\n", qpxr);
+//printf("  -->(q - p) . r = %lf, r . r = %lf\n", v1.Dot(r), r.Dot(r));
+//printf("  -->(p - q) . s = %lf, s . s = %lf\n", v2.Dot(s), s.Dot(s));
+//printf("  -->(q - p) . s = %lf, (p - q) . r = %lf\n", v1.Dot(s), v2.Dot(r));
+
+               // Lines are parallel, so no intersection...
+               if (qpxr != 0)
+                       return 0;
+
+#if 0
+//this works IFF the vectors are pointing in the same direction. everything else
+//is fucked!
+               // If (q - p) . r == r . r, t = 1, u = 0
+               if (v1.Dot(r) == r.Dot(r))
+                       t = 1.0, u = 0;
+               // If (p - q) . s == s . s, t = 0, u = 1
+               else if (v2.Dot(s) == s.Dot(s))
+                       t = 0, u = 1.0;
+               else
+                       return 0;
+#else
+               // Check to see which endpoints are connected... Four possibilities:
+               if (l1->position == l2->position)
+                       t = 0, u = 0;
+               else if (l1->position == l2->endpoint)
+                       t = 0, u = 1.0;
+               else if (l1->endpoint == l2->position)
+                       t = 1.0, u = 0;
+               else if (l1->endpoint == l2->endpoint)
+                       t = 1.0, u = 1.0;
+               else
+                       return 0;
+#endif
+       }
+       else
+       {
+               t = ((v1.x * s.y) - (s.x * v1.y)) / rxs;
+               u = ((v1.x * r.y) - (r.x * v1.y)) / rxs;
+       }
 /*
-Now there are five cases:
+Now there are five cases (NOTE: only valid if vectors face the same way!):
 
 1. If r × s = 0 and (q − p) × r = 0, then the two lines are collinear. If in addition, either 0 ≤ (q − p) · r ≤ r · r or 0 ≤ (p − q) · s ≤ s · s, then the two lines are overlapping.
 
@@ -166,6 +206,14 @@ Now there are five cases:
 }
 
 
+// Finds the intersection between two lines (if any)
+int Geometry::Intersects(Line * l1, Dimension * d1, double * tp/*= 0*/, double * up/*= 0*/)
+{
+       Line l2(d1->position, d1->endpoint);
+       return Intersects(l1, &l2, tp, up);
+}
+
+
 // Finds the intesection(s) between a line and a circle (if any)
 int Geometry::Intersects(Line * l, Circle * c, double * tp/*= 0*/, double * up/*= 0*/, double * vp/*= 0*/, double * wp/*= 0*/)
 {