From 6a7baa2814a8b4d0b93df776a4c99689bcfb3ffa Mon Sep 17 00:00:00 2001 From: Shamus Hammons Date: Tue, 12 Jan 2016 13:35:12 -0600 Subject: [PATCH] Added preliminary circle-to-circle intersection code. --- src/drawingview.cpp | 20 ++++++++++-- src/geometry.cpp | 77 +++++++++++++++++++++++++++++++++++++++------ src/geometry.h | 5 +-- src/global.cpp | 5 +++ src/global.h | 5 +++ 5 files changed, 99 insertions(+), 13 deletions(-) diff --git a/src/drawingview.cpp b/src/drawingview.cpp index 62f240a..5ae9c9a 100644 --- 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 b67c64e..6ed6fab 100644 --- a/src/geometry.cpp +++ b/src/geometry.cpp @@ -16,6 +16,7 @@ #include "geometry.h" #include #include +#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 02cfada..1c4177b 100644 --- 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 8b89b94..8dc2f98 100644 --- 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 Global::layerHidden; diff --git a/src/global.h b/src/global.h index 6495524..c0f019a 100644 --- 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 layerHidden; -- 2.37.2