Added preliminary circle-to-circle intersection code.

[architektonas] / src / geometry.cpp

diff --git a/src/geometry.cpp b/src/geometry.cpp
index b67c64e30e6211d8cd9dafefbd1204671101f02b..6ed6fab1020c70449e64955f4bc9c6c0548f28b8 100644 (file)
--- a/src/geometry.cpp
+++ b/src/geometry.cpp
@@ -16,6 +16,7 @@
 #include "geometry.h"
 #include <math.h>
 #include <stdio.h>
+#include "global.h"
 #include "mathconstants.h"
 
 
@@ -104,12 +105,14 @@ double Geometry::Determinant(Point p1, Point p2)
 }
 
 
-int Geometry::Intersects(Object * obj1, Object * obj2, double * tp/*= 0*/, double * up/*= 0*/, double * vp/*= 0*/, double * wp/*= 0*/)
+void Geometry::Intersects(Object * obj1, Object * obj2)//, double * tp/*= 0*/, double * up/*= 0*/, double * vp/*= 0*/, double * wp/*= 0*/)
 {
-       if ((obj1->type == OTLine) && (obj2->type == OTLine))
-               return CheckLineToLineIntersection(obj1, obj2, tp, up);
+       Global::numIntersectPoints = Global::numIntersectParams = 0;
 
-       return 0;
+       if ((obj1->type == OTLine) && (obj2->type == OTLine))
+               CheckLineToLineIntersection(obj1, obj2);
+       else if ((obj1->type == OTCircle) && (obj2->type == OTCircle))
+               CheckCircleToCircleIntersection(obj1, obj2);
 }
 
 
@@ -133,8 +136,10 @@ So check if the above two numbers are both >=0 and <=1.
 
 
 // Finds the intersection between two lines (if any)
-int Geometry::CheckLineToLineIntersection(Object * l1, Object * l2, double * tp, double * up)
+void Geometry::CheckLineToLineIntersection(Object * l1, Object * l2)//, double * tp, double * up)
 {
+       Global::numIntersectPoints = Global::numIntersectParams = 0;
+
        Vector r(l1->p[0], l1->p[1]);
        Vector s(l2->p[0], l2->p[1]);
        Vector v1 = l2->p[0] - l1->p[0];        // q - p
@@ -158,7 +163,7 @@ 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;
+                       return;
 
 #if 0
 //this works IFF the vectors are pointing in the same direction. everything else
@@ -182,7 +187,7 @@ printf("  -->(q - p) . s = %lf, (p - q) . r = %lf\n", v1.Dot(s), v2.Dot(r));
                else if (l1->p[1] == l2->p[1])
                        t = 1.0, u = 1.0;
                else
-                       return 0;
+                       return;
 #endif
        }
        else
@@ -204,6 +209,7 @@ Now there are five cases (NOTE: only valid if vectors face the same way!):
 5. Otherwise, the two line segments are not parallel but do not intersect.
 */
        // Return parameter values, if user passed in valid pointers
+#if 0
        if (tp)
                *tp = t;
 
@@ -215,6 +221,56 @@ Now there are five cases (NOTE: only valid if vectors face the same way!):
                return 1;
 
        return 0;
+#else
+       Global::intersectParam[0] = t;
+       Global::intersectParam[1] = u;
+
+       // If the parameters are in range, we have overlap!
+       if ((t >= 0) && (t <= 1.0) && (u >= 0) && (u <= 1.0))
+               Global::numIntersectParams = 1;
+#endif
+}
+
+
+void Geometry::CheckCircleToCircleIntersection(Object * c1, Object * c2)
+{
+       // Set up global vars
+       Global::numIntersectPoints = Global::numIntersectParams = 0;
+
+       // Get the distance between the centers of the circles
+       Vector centerLine(c1->p[0], c2->p[0]);
+       double d = centerLine.Magnitude();
+       double clAngle = centerLine.Angle();
+
+       // If the distance between centers is greater than the sum of the radii or
+       // less than the difference between the radii, there is NO intersection
+       if ((d > (c1->radius[0] + c2->radius[0]))
+               || (d < fabs(c1->radius[0] - c2->radius[0])))
+               return;
+
+       // If the distance between centers is equal to the sum of the radii or
+       // equal to the difference between the radii, the intersection is tangent
+       // to both circles.
+       if ((d == (c1->radius[0] + c2->radius[0]))
+               || (d == fabs(c1->radius[0] - c2->radius[0])))
+       {
+               Global::intersectPoint[0].x = c1->p[0].x + (cos(clAngle) * c1->radius[0]);
+               Global::intersectPoint[0].y = c1->p[0].y + (sin(clAngle) * c1->radius[0]);
+               Global::numIntersectPoints = 1;
+               return;
+       }
+
+       // Use the Law of Cosines to find the angle between the centerline and the
+       // radial line on Circle #1
+       double a = acos(((c1->radius[0] * c1->radius[0]) + (d * d) - (c2->radius[0] * c2->radius[0])) / (2.0 * c1->radius[0] * d));
+
+       // Finally, find the points of intersection by using +/- the angle found
+       // from the centerline's angle
+       Global::intersectPoint[0].x = c1->p[0].x + (cos(clAngle + a) * c1->radius[0]);
+       Global::intersectPoint[0].y = c1->p[0].y + (sin(clAngle + a) * c1->radius[0]);
+       Global::intersectPoint[1].x = c1->p[0].x + (cos(clAngle - a) * c1->radius[0]);
+       Global::intersectPoint[1].y = c1->p[0].y + (sin(clAngle - a) * c1->radius[0]);
+       Global::numIntersectPoints = 2;
 }
 
 
@@ -359,6 +415,9 @@ int Geometry::Intersects(Circle * c1, Circle * c2, double * tp/*= 0*/, double *
 
        // Find the distance from the center of c1 to the perpendicular chord
        // (which contains the points of intersection)
+       // [N.B.: This is derived from Pythagorus by using the unknown distance
+       //        from the center line to the point where the two radii coincide as
+       //        a common unknown to two instances of the formula.]
        double x = ((d * d) - (c2->radius * c2->radius) + (c1->radius * c1->radius))
                / (2.0 * d);
        // Find the the length of the perpendicular chord
@@ -399,9 +458,9 @@ int Geometry::Intersects(Circle * c1, Circle * c2, double * tp/*= 0*/, double *
 
 // should we just do common trig solves, like AAS, ASA, SAS, SSA?
 // Law of Cosines:
-// c^2 = a^2 + b^2 -2ab*cos(C)
+// c² = a² + b² - 2ab * cos(C)
 // Solving for C:
-// cos(C) = (c^2 - a^2 - b^2) / -2ab = (a^2 + b^2 - c^2) / 2ab
+// cos(C) = (c² - a² - b²) / -2ab = (a² + b² - c²) / 2ab
 // Law of Sines:
 // a / sin A = b / sin B = c / sin C