Added preliminary circle-to-circle intersection code.

diff --git a/src/drawingview.cpp b/src/drawingview.cpp
index 62f240a1c931a32c5b49f4cf77e79f872c89136c..5ae9c9a9081e5ccf121c82958eac22e6634d6400 100644 (file)
--- a/src/drawingview.cpp
+++ b/src/drawingview.cpp
@@ -1302,8 +1302,12 @@ void DrawingView::mouseMoveEvent(QMouseEvent * event)
        {
                GetHovered(hover);
 
-               double t, u;
-               int numIntersecting = Geometry::Intersects((Object *)hover[0], (Object *)hover[1], &t, &u);
+//             double t, u;
+//             int numIntersecting = Geometry::Intersects((Object *)hover[0], (Object *)hover[1], &t, &u);
+               Geometry::Intersects((Object *)hover[0], (Object *)hover[1]);
+               int numIntersecting = Global::numIntersectParams;
+               double t = Global::intersectParam[0];
+               double u = Global::intersectParam[1];
 
                if (numIntersecting > 0)
                {
@@ -1315,6 +1319,18 @@ void DrawingView::mouseMoveEvent(QMouseEvent * event)
                        hoveringIntersection = true;
                        intersectionPoint = v1;
                }
+
+               numIntersecting = Global::numIntersectPoints;
+
+               if (numIntersecting > 0)
+               {
+                       Vector v1 = Global::intersectPoint[0];
+                       QString text = tr("Intersection <%1, %2>");
+                       informativeText = text.arg(v1.x).arg(v1.y);
+
+                       hoveringIntersection = true;
+                       intersectionPoint = v1;
+               }
        }
 
        // Do tool handling, if any are active...

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
 

diff --git a/src/geometry.h b/src/geometry.h
index 02cfada77dee1c68b9e658adf335b6a7c9110d45..1c4177b10e68120655b66ae9bc2ee48dcc068261 100644 (file)
--- a/src/geometry.h
+++ b/src/geometry.h
@@ -13,8 +13,9 @@ class Geometry
                static Point MirrorPointAroundLine(Point, Point, Point);
                static Point RotatePointAroundPoint(Point, Point, double);
                static double Determinant(Point, Point);
-               static int Intersects(Object *, Object *, double * tp = 0, double * up = 0, double * vp = 0, double * wp = 0);
-               static int CheckLineToLineIntersection(Object *, Object *, double *, double *);
+               static void Intersects(Object *, Object *);//, double * tp = 0, double * up = 0, double * vp = 0, double * wp = 0);
+               static void CheckLineToLineIntersection(Object *, Object *);
+               static void CheckCircleToCircleIntersection(Object *, Object *);//, Point *, Point *);
 //             static int Intersects(Line *, Line *, double * tp = 0, double * up = 0);
 //             static int Intersects(Line *, Dimension *, double * tp = 0, double * up = 0);
 //             static int Intersects(Line * l, Circle * c, double * tp = 0, double * up = 0, double * vp = 0, double * wp = 0);

diff --git a/src/global.cpp b/src/global.cpp
index 8b89b9437a309b96d9fdfba9b0f3eac338610012..8dc2f98d76693b99c3470746288355119590e3de 100644 (file)
--- a/src/global.cpp
+++ b/src/global.cpp
@@ -38,6 +38,11 @@ Vector Global::screenSize(200.0, 200.0);
 
 float Global::scale = 0.5;
 
+Point Global::intersectPoint[16]; // Overkill, yes
+double Global::intersectParam[16]; // Ditto
+int Global::numIntersectPoints = 0;
+int Global::numIntersectParams = 0;
+
 int Global::activeLayer = 0;
 int Global::numLayers = 1;
 std::vector<bool> Global::layerHidden;

diff --git a/src/global.h b/src/global.h
index 6495524d05022ce6502e8fd7f6bd29ff8ad07d04..c0f019aa839ab9cba999ad0b72e3911785af9a80 100644 (file)
--- a/src/global.h
+++ b/src/global.h
@@ -44,6 +44,11 @@ class Global
 
                static float scale;
 
+               static Point intersectPoint[16]; // Overkill, yes
+               static double intersectParam[16]; // Ditto
+               static int numIntersectPoints;
+               static int numIntersectParams;
+
                static int activeLayer;
                static int numLayers;
                static std::vector<bool> layerHidden;