From 0fcc2d879e1e0ca17eeaceae2159f5143a06586f Mon Sep 17 00:00:00 2001 From: Shamus Hammons Date: Sat, 5 Nov 2016 21:30:11 -0500 Subject: [PATCH] Added line-to-circle intersection code. Fixed circle-to-circle intersection code, also converted all circular functions to use TAU instead of PI. (Yes, PI is wrong! ;-) --- src/about.cpp | 2 +- src/applicationwindow.cpp | 3 +- src/connection.cpp | 2 +- src/drawingview.cpp | 104 +++++-------- src/drawingview.h | 1 - src/fileio.cpp | 2 +- src/geometry.cpp | 314 +++++++++----------------------------- src/geometry.h | 10 +- src/main.cpp | 2 +- src/mathconstants.h | 22 ++- src/painter.cpp | 14 +- src/utils.cpp | 2 +- src/vector.cpp | 4 + src/vector.h | 26 ++-- 14 files changed, 162 insertions(+), 346 deletions(-) diff --git a/src/about.cpp b/src/about.cpp index 17b4f96..7a8a210 100644 --- a/src/about.cpp +++ b/src/about.cpp @@ -7,7 +7,7 @@ // JLH = James Hammons // // Who When What -// --- ---------- ------------------------------------------------------------- +// --- ---------- ------------------------------------------------------------ // JLH 01/21/2010 Created this file // JLH 01/22/2010 Fleshed out the credits a bit more // JLH 01/22/2010 Fixed centering and decorating of window diff --git a/src/applicationwindow.cpp b/src/applicationwindow.cpp index ac4122d..ad83272 100644 --- a/src/applicationwindow.cpp +++ b/src/applicationwindow.cpp @@ -8,7 +8,7 @@ // JLH = James Hammons // // Who When What -// --- ---------- ------------------------------------------------------------- +// --- ---------- ------------------------------------------------------------ // JLH 03/22/2011 Created this file // JLH 09/29/2011 Added simple zoom in/out functionality // JLH 10/03/2011 Fixed zoom tool to zoom in/out from center of screen @@ -88,7 +88,6 @@ ApplicationWindow::ApplicationWindow(): setUnifiedTitleAndToolBarOnMac(true); Global::font = new QFont("Verdana", 15, QFont::Bold); - connect(lw, SIGNAL(LayerSelected(int)), drawing, SLOT(SetCurrentLayer(int))); connect(lw, SIGNAL(LayerDeleted(int)), drawing, SLOT(DeleteCurrentLayer(int))); connect(lw, SIGNAL(LayerToggled()), drawing, SLOT(HandleLayerToggle())); connect(lw, SIGNAL(LayersSwapped(int, int)), drawing, SLOT(HandleLayerSwap(int, int))); diff --git a/src/connection.cpp b/src/connection.cpp index 7170c46..8e12234 100644 --- a/src/connection.cpp +++ b/src/connection.cpp @@ -8,7 +8,7 @@ // JLH = James Hammons // // Who When What -// --- ---------- ------------------------------------------------------------- +// --- ---------- ------------------------------------------------------------ // JLH 03/14/2013 Created this file // diff --git a/src/drawingview.cpp b/src/drawingview.cpp index 5ae9c9a..0e563e7 100644 --- a/src/drawingview.cpp +++ b/src/drawingview.cpp @@ -7,7 +7,7 @@ // JLH = James Hammons // // Who When What -// --- ---------- ------------------------------------------------------------- +// --- ---------- ------------------------------------------------------------ // JLH 03/22/2011 Created this file // JLH 09/29/2011 Added middle mouse button panning // @@ -91,8 +91,8 @@ DrawingView::DrawingView(QWidget * parent/*= NULL*/): QWidget(parent), document.objects.push_back(new Line(Vector(10, 83), Vector(17, 2))); document.objects.push_back(new Circle(Vector(100, 100), 36)); document.objects.push_back(new Circle(Vector(50, 150), 49)); - document.objects.push_back(new Arc(Vector(300, 300), 32, PI / 4.0, PI * 1.3)), - document.objects.push_back(new Arc(Vector(200, 200), 60, PI / 2.0, PI * 1.5)); + document.objects.push_back(new Arc(Vector(300, 300), 32, TAU / 8.0, TAU * 0.65)), + document.objects.push_back(new Arc(Vector(200, 200), 60, TAU / 4.0, TAU * 0.75)); document.objects.push_back(new Dimension(Vector(50, 40), Vector(5, 5))); document.objects.push_back(new Text(Vector(10, 83), "Here is some awesome text!")); #endif @@ -147,20 +147,6 @@ we do! :-) } -#if 0 -void DrawingView::SetToolActive(Action * action) -{ - if (action != NULL) - { - toolAction = action; - connect(toolAction, SIGNAL(ObjectReady(Object *)), this, - SLOT(AddNewObjectToDocument(Object *))); - connect(toolAction, SIGNAL(NeedRefresh()), this, SLOT(HandleActionUpdate())); - } -} -#endif - - void DrawingView::SetGridSize(uint32_t size) { // Sanity check @@ -182,7 +168,6 @@ void DrawingView::SetGridSize(uint32_t size) pmp.end(); // Set up new BG brush & zoom level (pixels per base unit) -// Painter::zoom = gridPixels / gridSpacing; Global::zoom = gridPixels / Global::gridSpacing; UpdateGridBackground(); } @@ -267,14 +252,6 @@ zero; so we do another modulus operation on the result to achieve this. } -void DrawingView::SetCurrentLayer(int /*layer*/) -{ -//Not needed anymore... -// Global::currentLayer = layer; -//printf("DrawingView::CurrentLayer = %i\n", layer); -} - - // // Basically, we just make a single pass through the Container. If the layer # // is less than the layer # being deleted, then do nothing. If the layer # is @@ -340,9 +317,9 @@ void DrawingView::HandleLayerSwap(int layer1, int layer2) QPoint DrawingView::GetAdjustedMousePosition(QMouseEvent * event) { - // This is undoing the transform, e.g. going from client coords to local coords. - // In essence, the height - y is height + (y * -1), the (y * -1) term doing the - // conversion of the y-axis from increasing bottom to top. + // This is undoing the transform, e.g. going from client coords to local + // coords. In essence, the height - y is height + (y * -1), the (y * -1) + // term doing the conversion of the y-axis from increasing bottom to top. return QPoint(offsetX + event->x(), offsetY + (size().height() - event->y())); } @@ -351,7 +328,7 @@ QPoint DrawingView::GetAdjustedClientPosition(int x, int y) { // VOODOO ALERT (ON Y COMPONENT!!!!) (eh?) // No voodoo here, it's just grouped wrong to see it. It should be: - // -offsetY + (size.height() + (y * -1.0)) <-- this is wrong, offsetY should be positive + // -offsetY + (size.height() + (y * -1.0)) <-- this is wrong, offsetY should be positive [why? we use -offsetX after all] return QPoint(-offsetX + x, (size().height() - (-offsetY + y)) * +1.0); } @@ -477,19 +454,19 @@ void DrawingView::RenderObjects(Painter * painter, std::vector & v, int if (d->subtype == DTLinearVert) { - if ((angle < 0) || (angle > PI)) + if ((angle < 0) || (angle > HALF_TAU)) { x1 = (d->p[0].x > d->p[1].x ? d->p[0].x : d->p[1].x); y1 = (d->p[0].y > d->p[1].y ? d->p[0].y : d->p[1].y); ortho = Vector(1.0, 0); - angle = PI3_OVER_2; + angle = THREE_QTR_TAU; } else { x1 = (d->p[0].x > d->p[1].x ? d->p[1].x : d->p[0].x); y1 = (d->p[0].y > d->p[1].y ? d->p[1].y : d->p[0].y); ortho = Vector(-1.0, 0); - angle = PI_OVER_2; + angle = QTR_TAU; } linePt1.x = linePt2.x = x1; @@ -497,7 +474,7 @@ void DrawingView::RenderObjects(Painter * painter, std::vector & v, int } else if (d->subtype == DTLinearHorz) { - if ((angle < PI_OVER_2) || (angle > PI3_OVER_2)) + if ((angle < QTR_TAU) || (angle > THREE_QTR_TAU)) { x1 = (d->p[0].x > d->p[1].x ? d->p[0].x : d->p[1].x); y1 = (d->p[0].y > d->p[1].y ? d->p[0].y : d->p[1].y); @@ -509,7 +486,7 @@ void DrawingView::RenderObjects(Painter * painter, std::vector & v, int x1 = (d->p[0].x > d->p[1].x ? d->p[1].x : d->p[0].x); y1 = (d->p[0].y > d->p[1].y ? d->p[1].y : d->p[0].y); ortho = Vector(0, -1.0); - angle = PI; + angle = HALF_TAU; } linePt1.y = linePt2.y = y1; @@ -539,10 +516,9 @@ void DrawingView::RenderObjects(Painter * painter, std::vector & v, int painter->DrawLine(p3, p5); painter->DrawLine(p4, p6); - // Calculate whether or not the arrowheads are too crowded to put inside - // the extension lines. 9.0 is the length of the arrowhead. + // Calculate whether or not the arrowheads are too crowded to put + // inside the extension lines. 9.0 is the length of the arrowhead. double t = Geometry::ParameterOfLineAndPoint(linePt1, linePt2, linePt2 - (unit * 9.0 * scaledThickness)); - //printf("Dimension::Draw(): t = %lf\n", t); // On the screen, it's acting like this is actually 58%... // This is correct, we want it to happen at > 50% @@ -568,9 +544,6 @@ void DrawingView::RenderObjects(Painter * painter, std::vector & v, int painter->SetFont(QFont("Arial", 8.0 * Global::zoom * scaledThickness)); Point ctr = p2 + (Vector(p2, p1) / 2.0); - #if 0 - QString dimText = QString("%1\"").arg(Vector(endpoint - position).Magnitude()); - #else QString dimText; if (length < 12.0) @@ -585,7 +558,6 @@ void DrawingView::RenderObjects(Painter * painter, std::vector & v, int else dimText = QString("%1' %2\"").arg(feet).arg(inches); } - #endif painter->DrawAngledText(ctr, angle, dimText, scaledThickness); @@ -744,7 +716,7 @@ void DrawingView::ToolDraw(Painter * painter) double span = angle - toolPoint[2].x; if (span < 0) - span += PI_TIMES_2; + span += TAU; painter->DrawLine(toolPoint[0], toolPoint[3]); painter->SetBrush(QBrush(Qt::NoBrush)); @@ -974,7 +946,7 @@ void DrawingView::ArcHandler(int mode, Point p) double span = endAngle - toolPoint[2].x; if (span < 0) - span += PI_TIMES_2; + span += TAU; Arc * arc = new Arc(toolPoint[0], toolPoint[1].x, toolPoint[2].x, span); arc->layer = Global::activeLayer; @@ -1029,8 +1001,8 @@ void DrawingView::RotateHandler(int mode, Point p) { obj2->angle[0] = obj.angle[0] + angle; - if (obj2->angle[0] > PI_TIMES_2) - obj2->angle[0] -= PI_TIMES_2; + if (obj2->angle[0] > TAU) + obj2->angle[0] -= TAU; } } } @@ -1132,8 +1104,8 @@ void DrawingView::MirrorHandler(int mode, Point p) // This is 2*mirror angle - obj angle - obj span obj2->angle[0] = (2.0 * angle) - obj.angle[0] - obj.angle[1]; - if (obj2->angle[0] > PI_TIMES_2) - obj2->angle[0] -= PI_TIMES_2; + if (obj2->angle[0] > TAU) + obj2->angle[0] -= TAU; } } } @@ -1325,9 +1297,17 @@ void DrawingView::mouseMoveEvent(QMouseEvent * event) if (numIntersecting > 0) { Vector v1 = Global::intersectPoint[0]; + + if (numIntersecting == 2) + { + Vector v2 = Global::intersectPoint[1]; + + if (Vector::Magnitude(v2, point) < Vector::Magnitude(v1, point)) + v1 = v2; + } + QString text = tr("Intersection <%1, %2>"); informativeText = text.arg(v1.x).arg(v1.y); - hoveringIntersection = true; intersectionPoint = v1; } @@ -1550,28 +1530,28 @@ void DrawingView::CheckObjectBounds(void) // If the end of the arc is before the beginning, add 360 degrees to it if (end < start) - end += 2.0 * PI; + end += TAU; // Adjust the bounds depending on which axes are crossed - if ((start < PI_OVER_2) && (end > PI_OVER_2)) + if ((start < QTR_TAU) && (end > QTR_TAU)) bounds.setTop(1.0); - if ((start < PI) && (end > PI)) + if ((start < HALF_TAU) && (end > HALF_TAU)) bounds.setLeft(-1.0); - if ((start < (PI + PI_OVER_2)) && (end > (PI + PI_OVER_2))) + if ((start < THREE_QTR_TAU) && (end > THREE_QTR_TAU)) bounds.setBottom(-1.0); - if ((start < (2.0 * PI)) && (end > (2.0 * PI))) + if ((start < TAU) && (end > TAU)) bounds.setRight(1.0); - if ((start < ((2.0 * PI) + PI_OVER_2)) && (end > ((2.0 * PI) + PI_OVER_2))) + if ((start < (TAU + QTR_TAU)) && (end > (TAU + QTR_TAU))) bounds.setTop(1.0); - if ((start < (3.0 * PI)) && (end > (3.0 * PI))) + if ((start < (TAU + HALF_TAU)) && (end > (TAU + HALF_TAU))) bounds.setLeft(-1.0); - if ((start < ((3.0 * PI) + PI_OVER_2)) && (end > ((3.0 * PI) + PI_OVER_2))) + if ((start < (TAU + THREE_QTR_TAU)) && (end > (TAU + THREE_QTR_TAU))) bounds.setBottom(-1.0); bounds.setTopLeft(QPointF(bounds.left() * a->radius[0], bounds.top() * a->radius[0])); @@ -1665,7 +1645,7 @@ bool DrawingView::HitTestObjects(Point point) // Make sure we get the angle in the correct spot if (angle < obj->angle[0]) - angle += PI_TIMES_2; + angle += TAU; // Get the span that we're pointing at... double span = angle - obj->angle[0]; @@ -1756,13 +1736,13 @@ void DrawingView::HandleObjectMovement(Point point) double delta = angle - obj->angle[0]; if (delta < 0) - delta += PI_TIMES_2; + delta += TAU; obj->angle[1] -= delta; obj->angle[0] = angle; if (obj->angle[1] < 0) - obj->angle[1] += PI_TIMES_2; + obj->angle[1] += TAU; QString text = QObject::tr("Span: %1") + QChar(0x00B0) + QObject::tr("\n%2") + QChar(0x00B0) + QObject::tr(" - %3") + QChar(0x00B0); informativeText = text.arg(obj->angle[1] * RADIANS_TO_DEGREES, 0, 'd', 4).arg(obj->angle[0] * RADIANS_TO_DEGREES, 0, 'd', 2).arg((obj->angle[0] + obj->angle[1]) * RADIANS_TO_DEGREES, 0, 'd', 2); @@ -1783,7 +1763,7 @@ void DrawingView::HandleObjectMovement(Point point) obj->angle[1] = angle - obj->angle[0]; if (obj->angle[1] < 0) - obj->angle[1] += PI_TIMES_2; + obj->angle[1] += TAU; QString text = QObject::tr("Span: %1") + QChar(0x00B0) + QObject::tr("\n%2") + QChar(0x00B0) + QObject::tr(" - %3") + QChar(0x00B0); informativeText = text.arg(obj->angle[1] * RADIANS_TO_DEGREES, 0, 'd', 4).arg(obj->angle[0] * RADIANS_TO_DEGREES, 0, 'd', 2).arg((obj->angle[0] + obj->angle[1]) * RADIANS_TO_DEGREES, 0, 'd', 2); @@ -1794,7 +1774,7 @@ void DrawingView::HandleObjectMovement(Point point) obj->angle[0] = angle - obj->angle[1]; if (obj->angle[0] < 0) - obj->angle[0] += PI_TIMES_2; + obj->angle[0] += TAU; QString text = QObject::tr("End angle: %1") + QChar(0x00B0); informativeText = text.arg((obj->angle[0] + obj->angle[1]) * RADIANS_TO_DEGREES, 0, 'd', 4); diff --git a/src/drawingview.h b/src/drawingview.h index 454d6f2..cf70e40 100644 --- a/src/drawingview.h +++ b/src/drawingview.h @@ -36,7 +36,6 @@ class DrawingView: public QWidget void HandleObjectMovement(Point); public slots: - void SetCurrentLayer(int); void DeleteCurrentLayer(int); void HandleLayerToggle(void); void HandleLayerSwap(int, int); diff --git a/src/fileio.cpp b/src/fileio.cpp index 503ccc1..e0028cd 100644 --- a/src/fileio.cpp +++ b/src/fileio.cpp @@ -8,7 +8,7 @@ // JLH = James Hammons // // Who When What -// --- ---------- ------------------------------------------------------------- +// --- ---------- ------------------------------------------------------------ // JLH 02/20/2013 Created this file // diff --git a/src/geometry.cpp b/src/geometry.cpp index 6ed6fab..b915897 100644 --- a/src/geometry.cpp +++ b/src/geometry.cpp @@ -20,32 +20,6 @@ #include "mathconstants.h" -// This is unused -#if 0 -Point Geometry::IntersectionOfLineAndLine(Point p1, Point p2, Point p3, Point p4) -{ - // Find the intersection of the lines by formula: - // px = (x1y2 - y1x2)(x3 - x4) - (x1 - x2)(x3y4 - y3x4) - // py = (x1y2 - y1x2)(y3 - y4) - (y1 - y2)(x3y4 - y3x4) - // d = (x1 - x2)(y3 - y4) - (y1 - y2)(x3 - x4) = 0 if lines are parallel - // Intersection is (px / d, py / d) - - double d = ((p1.x - p2.x) * (p3.y - p4.y)) - ((p1.y - p2.y) * (p3.x - p4.x)); - - // Check for parallel lines, and return sentinel if so - if (d == 0) - return Point(0, 0, -1); - - double px = (((p1.x * p2.y) - (p1.y * p2.x)) * (p3.x - p4.x)) - - ((p1.x - p2.x) * ((p3.x * p4.y) - (p3.y * p4.x))); - double py = (((p1.x * p2.y) - (p1.y * p2.x)) * (p3.y - p4.y)) - - ((p1.y - p2.y) * ((p3.x * p4.y) - (p3.y * p4.x))); - - return Point(px / d, py / d, 0); -} -#endif - - // Returns the parameter of a point in space to this vector. If the parameter // is between 0 and 1, the normal of the vector to the point is on the vector. // Note: lp1 is the tail, lp2 is the head of the line (vector). @@ -105,7 +79,7 @@ double Geometry::Determinant(Point p1, Point p2) } -void 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) { Global::numIntersectPoints = Global::numIntersectParams = 0; @@ -113,6 +87,10 @@ void Geometry::Intersects(Object * obj1, Object * obj2)//, double * tp/*= 0*/, d CheckLineToLineIntersection(obj1, obj2); else if ((obj1->type == OTCircle) && (obj2->type == OTCircle)) CheckCircleToCircleIntersection(obj1, obj2); + else if ((obj1->type == OTLine) && (obj2->type == OTCircle)) + CheckLineToCircleIntersection(obj1, obj2); + else if ((obj1->type == OTCircle) && (obj2->type == OTLine)) + CheckLineToCircleIntersection(obj2, obj1); } @@ -136,17 +114,14 @@ So check if the above two numbers are both >=0 and <=1. // Finds the intersection between two lines (if any) -void Geometry::CheckLineToLineIntersection(Object * l1, Object * l2)//, double * tp, double * up) +void Geometry::CheckLineToLineIntersection(Object * l1, Object * l2) { 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 -#if 0 - Vector v2 = l1->p[0] - l2->p[0]; // p - q -printf("l1: (%lf, %lf) (%lf, %lf), l2: (%lf, %lf) (%lf, %lf)\n", l1->p[0].x, l1->p[0].y, l1->p[1].x, l1->p[1].y, l2->p[0].x, l2->p[0].y, l2->p[1].x, l2->p[1].y); -#endif + double rxs = (r.x * s.y) - (s.x * r.y); double t, u; @@ -154,29 +129,10 @@ printf("l1: (%lf, %lf) (%lf, %lf), l2: (%lf, %lf) (%lf, %lf)\n", l1->p[0].x, l1- { double qpxr = (v1.x * r.y) - (r.x * v1.y); -#if 0 -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)); -#endif - // Lines are parallel, so no intersection... if (qpxr != 0) return; -#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->p[0] == l2->p[0]) t = 0, u = 0; @@ -188,47 +144,19 @@ printf(" -->(q - p) . s = %lf, (p - q) . r = %lf\n", v1.Dot(s), v2.Dot(r)); t = 1.0, u = 1.0; else return; -#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 (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. -2. If r × s = 0 and (q − p) × r = 0, but neither 0 ≤ (q − p) · r ≤ r · r nor 0 ≤ (p − q) · s ≤ s · s, then the two lines are collinear but disjoint. - -3. If r × s = 0 and (q − p) × r ≠ 0, then the two lines are parallel and non-intersecting. - -4. If r × s ≠ 0 and 0 ≤ t ≤ 1 and 0 ≤ u ≤ 1, the two line segments meet at the point p + t r = q + u s. - -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; - - if (up) - *up = u; - - // If the parameters are in range, we have overlap! - if ((t >= 0) && (t <= 1.0) && (u >= 0) && (u <= 1.0)) - 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 } @@ -251,15 +179,27 @@ void Geometry::CheckCircleToCircleIntersection(Object * c1, Object * c2) // 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]))) + if (d == (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; } + else if (d == fabs(c1->radius[0] - c2->radius[0])) + { + double sign = (c1->radius[0] > c2->radius[0] ? +1 : -1); + Global::intersectPoint[0].x = c1->p[0].x + (cos(clAngle) * c1->radius[0] * sign); + Global::intersectPoint[0].y = c1->p[0].y + (sin(clAngle) * c1->radius[0] * sign); + Global::numIntersectPoints = 1; + return; + } +/* + c² = a² + b² - 2ab·cos µ +2ab·cos µ = a² + b² - c² + cos µ = (a² + b² - c²) / 2ab +*/ // 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)); @@ -274,188 +214,72 @@ void Geometry::CheckCircleToCircleIntersection(Object * c1, Object * c2) } -#if 0 -// Finds the intersection between two lines (if any) -int Geometry::Intersects(Line * l1, Dimension * d1, double * tp/*= 0*/, double * up/*= 0*/) +// +// N.B.: l is the line, c is the circle +// +void Geometry::CheckLineToCircleIntersection(Object * l, Object * c) { - Line l2(d1->position, d1->endpoint); - return Intersects(l1, &l2, tp, up); -} + // Set up global vars + Global::numIntersectPoints = Global::numIntersectParams = 0; + // Step 1: Find shortest distance from center of circle to the infinite line + double t = ParameterOfLineAndPoint(l->p[0], l->p[1], c->p[0]); + Point p = l->p[0] + (Vector(l->p[0], l->p[1]) * t); + Vector radial = Vector(c->p[0], p); + double distance = radial.Magnitude(); -// Finds the intersection(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*/) -{ -#if 0 - Vector center = c->position; - Vector v1 = l->position - center; - Vector v2 = l->endpoint - center; - Vector d = v2 - v1; - double dr = d.Magnitude(); - double determinant = (v1.x * v2.y) - (v1.y * v2.x); + // Step 2: See if we have 0, 1, or 2 intersection points - double discriminant = ((c->radius * c->radius) * (dr * dr)) - (determinant * determinant); + // Case #1: No intersection points + if (distance > c->radius[0]) + return; + // Case #2: One intersection point (possibly--tangent) + else if (distance == c->radius[0]) + { + // Only intersects if the parameter is on the line segment! + if ((t >= 0.0) && (t <= 1.0)) + { + Global::intersectPoint[0] = c->p[0] + radial; + Global::numIntersectPoints = 1; + } - if (discriminant < 0) - return false; + return; + } - + // Case #3: Two intersection points (possibly--secant) - return true; -#else -/* -I'm thinking a better approach to this might be as follows: - --- Get the distance of the circle's center from the line segment. If it's - > the radius, it doesn't intersect. --- If the parameter is off the line segment, check distance to endpoints. (Not sure - how to proceed from here, it's different than the following.) - [Actually, you can use the following for all of it. You only know if you have - an intersection at the last step, which is OK.] --- If the radius == distance, we have a tangent line. --- If radius > distance, use Pythagorus to find the length on either side of the - normal to the spots where the hypotenuse (== radius' length) contact the line. --- Use those points to find the parameter on the line segment; if they're not on - the line segment, no intersection. -*/ - double t = ParameterOfLineAndPoint(l->position, l->endpoint, c->position); -//small problem here: it clamps the result to the line segment. NOT what we want -//here! !!! FIX !!! [DONE] - Vector p = l->GetPointAtParameter(t); - double distance = Vector::Magnitude(c->position, p); - - // If the center of the circle is farther from the line than the radius, fail. - if (distance > c->radius) - return 0; - - // Now we have to check for intersection points. - // Tangent case: (needs to return something) - if ((distance == c->radius) && (t >= 0.0) && (t <= 1.0)) - { - // Need to set tp & up to something... !!! FIX !!! - if (tp) - *tp = t; + // So, we have the line, and the perpendicular from the center of the + // circle to the line. Now figure out where the intersection points are. + // This is a right triangle, though do we really know all the sides? + // Don't need to, 2 is enough for Pythagoras :-) + // Radius is the hypotenuse, so we have to use c² = a² + b² => a² = c² - b² + double perpendicularLength = sqrt((c->radius[0] * c->radius[0]) - (distance * distance)); - if (up) - *up = Vector(c->position, p).Angle(); + // Now, find the points using the length, then check to see if they are on + // the line segment + Vector lineUnit = Vector(l->p[0], l->p[1]).Unit(); + Point i1 = p + (lineUnit * perpendicularLength); + Point i2 = p - (lineUnit * perpendicularLength); - return 1; - } + // Now we have our intersection points, next we need to see if they are on + // the line segment... + double u = ParameterOfLineAndPoint(l->p[0], l->p[1], i1); + double v = ParameterOfLineAndPoint(l->p[0], l->p[1], i2); - // The line intersects the circle in two points (possibly). Use Pythagorus - // to find them for testing. - double offset = sqrt((c->radius * c->radius) - (distance * distance)); -//need to convert distance to paramter value... :-/ -//t = position on line / length of line segment, so if we divide the offset by length, -//that should give us what we want. - double length = Vector::Magnitude(l->position, l->endpoint); - double t1 = t + (offset / length); - double t2 = t - (offset / length); - -//need to find angles for the circle... - Vector cp1 = l->position + (Vector(l->position, l->endpoint) * (length * t1)); - Vector cp2 = l->position + (Vector(l->position, l->endpoint) * (length * t2)); - double a1 = Vector(c->position, cp1).Angle(); - double a2 = Vector(c->position, cp2).Angle(); - -//instead of this, return a # which is the # of intersections. [DONE] - int intersections = 0; - - // Now check for if the parameters are in range - if ((t1 >= 0) && (t1 <= 1.0)) + if ((u >= 0.0) && (u <= 1.0)) { - intersections++; + Global::intersectPoint[Global::numIntersectPoints] = i1; + Global::numIntersectPoints++; } - if ((t2 >= 0) && (t2 <= 1.0)) + if ((v >= 0.0) && (v <= 1.0)) { - intersections++; + Global::intersectPoint[Global::numIntersectPoints] = i2; + Global::numIntersectPoints++; } - - return intersections; -#endif } -// Finds the intersection(s) between a circle and a circle (if any) -// There can be 0, 1, or 2 intersections. -// Returns the angles of the points of intersection in tp thru wp, with the -// angles returned as c1, c2, c1, c2 (if applicable--in the 1 intersection case, -// only the first two angles are returned: c1, c2). -int Geometry::Intersects(Circle * c1, Circle * c2, double * tp/*= 0*/, double * up/*= 0*/, double * vp/*= 0*/, double * wp/*= 0*/, Point * p1/*= 0*/, Point * p2/*= 0*/) -{ - // Get the distance between centers. If the distance plus the radius of the - // smaller circle is less than the radius of the larger circle, there is no - // intersection. If the distance is greater than the sum of the radii, - // there is no intersection. If the distance is equal to the sum of the - // radii, they are tangent and intersect at one point. Otherwise, they - // intersect at two points. - Vector centerLine(c1->position, c2->position); - double d = centerLine.Magnitude(); -//printf("Circle #1: pos=<%lf, %lf>, r=%lf\n", c1->position.x, c1->position.y, c1->radius); -//printf("Circle #2: pos=<%lf, %lf>, r=%lf\n", c2->position.x, c2->position.y, c2->radius); -//printf("Distance between #1 & #2: %lf\n", d); - - // Check to see if we actually have an intersection, and return failure if not - if ((fabs(c1->radius - c2->radius) > d) || ((c1->radius + c2->radius) < d)) - return 0; - - // There are *two* tangent cases! - if (((c1->radius + c2->radius) == d) || (fabs(c1->radius - c2->radius) == d)) - { - // Need to return something in tp & up!! !!! FIX !!! [DONE] - if (tp) - *tp = centerLine.Angle(); - - if (up) - *up = centerLine.Angle() + PI; - - return 1; - } - - // 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 -// Not needed...! - double a = sqrt((-d + c2->radius - c1->radius) * (-d - c2->radius + c1->radius) * (-d + c2->radius + c1->radius) * (d + c2->radius + c1->radius)) / d; - - // Now, you can use pythagorus to find the length of the hypotenuse, but we - // already know that length, it's the radius! :-P - // What's needed is the angle of the center line and the radial line. Since - // there's two intersection points, there's also four angles (two for each - // circle)! - // We can use the arccos to find the angle using just the radius and the - // distance to the perpendicular chord...! - double angleC1 = acos(x / c1->radius); - double angleC2 = acos((d - x) / c2->radius); - - if (tp) - *tp = centerLine.Angle() - angleC1; - - if (up) - *up = (centerLine.Angle() + PI) - angleC2; - - if (vp) - *vp = centerLine.Angle() + angleC1; - - if (wp) - *wp = (centerLine.Angle() + PI) + angleC2; - - if (p1) - *p1 = c1->position + (centerLine.Unit() * x) + (Vector::Normal(Vector(), centerLine) * (a / 2.0)); - - if (p2) - *p2 = c1->position + (centerLine.Unit() * x) - (Vector::Normal(Vector(), centerLine) * (a / 2.0)); - - return 2; -} -#endif - // should we just do common trig solves, like AAS, ASA, SAS, SSA? // Law of Cosines: // c² = a² + b² - 2ab * cos(C) diff --git a/src/geometry.h b/src/geometry.h index 1c4177b..f1371e3 100644 --- a/src/geometry.h +++ b/src/geometry.h @@ -8,18 +8,14 @@ class Geometry { public: // All methods are class methods for this class -//unused static Point IntersectionOfLineAndLine(Point, Point, Point, Point); static double ParameterOfLineAndPoint(Point, Point, Point); static Point MirrorPointAroundLine(Point, Point, Point); static Point RotatePointAroundPoint(Point, Point, double); static double Determinant(Point, Point); - static void Intersects(Object *, Object *);//, double * tp = 0, double * up = 0, double * vp = 0, double * wp = 0); + static void Intersects(Object *, Object *); 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); -// static int Intersects(Circle * c1, Circle * c2, double * tp = 0, double * up = 0, double * vp = 0, double * wp = 0, Point * p1 = 0, Point * p2 = 0); + static void CheckCircleToCircleIntersection(Object *, Object *); + static void CheckLineToCircleIntersection(Object *, Object *); static void FindAnglesForSides(double s1, double s2, double s3, double * a1, double * a2, double * a3); static Point GetPointForParameter(Object *, double); }; diff --git a/src/main.cpp b/src/main.cpp index 42425e9..7a2e392 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -8,7 +8,7 @@ // JLH = James Hammons // // Who When What -// --- ---------- ------------------------------------------------------------- +// --- ---------- ------------------------------------------------------------ // JLH 03/22/2011 Created this file // diff --git a/src/mathconstants.h b/src/mathconstants.h index 42f4940..b0e516e 100644 --- a/src/mathconstants.h +++ b/src/mathconstants.h @@ -1,7 +1,7 @@ // Mathematical Constants used by Architektonas // // Part of the Architektonas Project -// (C) 2011 Underground Software +// (C) 2016 Underground Software // See the README and GPLv3 files for licensing and warranty information // // NOTE: Since this has no code associated with it, there is no corresponding @@ -10,14 +10,20 @@ // JLH = James Hammons // // WHO WHEN WHAT -// --- ---------- ------------------------------------------------------------ +// --- ---------- ----------------------------------------------------------- // JLH 04/01/2011 Created this file +// JLH 03/15/2016 Added Tau constants, removed Pi constants // -#define PI 3.14159265358979323846264338327 -#define PI_OVER_2 (PI / 2.0) -#define PI3_OVER_2 ((3.0 * PI) / 2.0) -#define PI_TIMES_2 (PI * 2.0) -#define RADIANS_TO_DEGREES (180.0 / PI) -#define DEGREES_TO_RADIANS (PI / 180.0) +#define TAU 6.28318530717958647692528676655 +#define TAU_1QTR (TAU * 0.25) +#define TAU_2QTR (TAU * 0.50) +#define TAU_3QTR (TAU * 0.75) +#define RADIANS_TO_DEGREES (360.0 / TAU) +#define DEGREES_TO_RADIANS (TAU / 360.0) + +// Convenience definitions +#define HALF_TAU (TAU_2QTR) +#define QTR_TAU (TAU_1QTR) +#define THREE_QTR_TAU (TAU_3QTR) diff --git a/src/painter.cpp b/src/painter.cpp index 5bd5ae4..e8aaba1 100644 --- a/src/painter.cpp +++ b/src/painter.cpp @@ -148,11 +148,19 @@ void Painter::DrawAngledText(Vector center, double angle, QString text, double s float yOffset = -12.0 * Global::zoom * size; // Fix text so it isn't upside down... +#if 0 if ((angle > PI * 0.5) && (angle < PI * 1.5)) { angle += PI; yOffset = 12.0 * Global::zoom * size; } +#else + if ((angle > QTR_TAU) && (angle < THREE_QTR_TAU)) + { + angle += HALF_TAU; + yOffset = 12.0 * Global::zoom * size; + } +#endif textBox.translate(0, yOffset); painter->save(); @@ -230,7 +238,7 @@ void Painter::DrawArrowHandle(Vector center, double angle) // Since we're drawing directly on the screen, the Y is inverted. So we use // the mirror of the angle. - double orthoAngle = -angle + (PI / 2.0); + double orthoAngle = -angle + QTR_TAU;//(PI / 2.0); Vector orthogonal = Vector(cos(orthoAngle), sin(orthoAngle)); Vector unit = Vector(cos(-angle), sin(-angle)); @@ -256,7 +264,7 @@ void Painter::DrawArrowToLineHandle(Vector center, double angle) // Since we're drawing directly on the screen, the Y is inverted. So we use // the mirror of the angle. - double orthoAngle = -angle + (PI / 2.0); + double orthoAngle = -angle + QTR_TAU;//(PI / 2.0); Vector orthogonal = Vector(cos(orthoAngle), sin(orthoAngle)); Vector unit = Vector(cos(-angle), sin(-angle)); @@ -355,7 +363,7 @@ void Painter::DrawArrowhead(Vector head, Vector tail, double size) // We draw the arrowhead aligned along the line from tail to head double angle = Vector(head - tail).Angle(); - double orthoAngle = angle + (PI / 2.0); + double orthoAngle = angle + QTR_TAU;//(PI / 2.0); Vector orthogonal = Vector(cos(orthoAngle), sin(orthoAngle)); Vector unit = Vector(head - tail).Unit(); diff --git a/src/utils.cpp b/src/utils.cpp index 2c3e1a4..12f7146 100644 --- a/src/utils.cpp +++ b/src/utils.cpp @@ -7,7 +7,7 @@ // JLH = James Hammons // // Who When What -// --- ---------- ------------------------------------------------------------- +// --- ---------- ------------------------------------------------------------ // JLH 05/01/2015 Created this file // diff --git a/src/vector.cpp b/src/vector.cpp index 23b4299..53c6bfe 100644 --- a/src/vector.cpp +++ b/src/vector.cpp @@ -214,7 +214,11 @@ double Vector::Angle(void) // quadrant the angle is in... Though, if the y-coordinate of the vector is // negative, that means that the angle is in quadrants III - IV. double rawAngle = acos(Unit().x); +#if 0 double correctedAngle = (y < 0 ? (2.0 * PI) - rawAngle : rawAngle); +#else + double correctedAngle = (y < 0 ? TAU - rawAngle : rawAngle); +#endif return correctedAngle; } diff --git a/src/vector.h b/src/vector.h index 4bcb461..e59b0e8 100644 --- a/src/vector.h +++ b/src/vector.h @@ -25,20 +25,20 @@ class Vector Vector operator=(Vector const v); Vector operator+(Vector const v); Vector operator-(Vector const v); - Vector operator-(void); // Unary negation - Vector operator*(double const v); // Vector times constant (double) - Vector operator*(float const v); // Vector times constant (float) - Vector operator/(double const v); // Vector divided by constant (double) - Vector operator/(float const v); // Vector divided by constant (float) - Vector operator*(Vector const v); // Vector product - double Dot(Vector const v); // Dot product + Vector operator-(void); // Unary negation + Vector operator*(double const v); // Vector times constant (double) + Vector operator*(float const v); // Vector times constant (float) + Vector operator/(double const v); // Vector divided by constant (double) + Vector operator/(float const v); // Vector divided by constant (float) + Vector operator*(Vector const v); // Vector product + double Dot(Vector const v); // Dot product - Vector& operator*=(double const v); // Vector times constant self-assignment - Vector& operator/=(double const v); // Vector divided by constant self-assignment - Vector& operator+=(Vector const v); // Vector plus Vector self-assignment - Vector& operator+=(double const v); // Vector plus constant self-assignment - Vector& operator-=(Vector const v); // Vector minus Vector self-assignment - Vector& operator-=(double const v); // Vector minus constant self-assignment + Vector& operator*=(double const v); // Vector times constant self-assignment + Vector& operator/=(double const v); // Vector divided by constant self-assignment + Vector& operator+=(Vector const v); // Vector plus Vector self-assignment + Vector& operator+=(double const v); // Vector plus constant self-assignment + Vector& operator-=(Vector const v); // Vector minus Vector self-assignment + Vector& operator-=(double const v); // Vector minus constant self-assignment bool operator==(Vector const v); // Check for equality bool operator!=(Vector const v); // Check for inequality -- 2.37.2