X-Git-Url: http://shamusworld.gotdns.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=src%2Fgeometry.cpp;h=86d1906f764851e7b28b5172292ab60aaac1b4f9;hb=5d8c9e52606315fbfe857f2715b8f051b4f97491;hp=95d12c65068b16715086191e1d70c7e01483dcbd;hpb=742d2aa9bb46bce4f690474fa22f5980e175e55e;p=architektonas diff --git a/src/geometry.cpp b/src/geometry.cpp index 95d12c6..86d1906 100644 --- a/src/geometry.cpp +++ b/src/geometry.cpp @@ -1,3 +1,4 @@ +// // geometry.cpp: Algebraic geometry helper functions // // Part of the Architektonas Project @@ -19,7 +20,6 @@ #include "global.h" #include "mathconstants.h" - // 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). @@ -35,10 +35,10 @@ double Geometry::ParameterOfLineAndPoint(Point tail, Point head, Point point) double magnitude = lineSegment.Magnitude(); Vector pointSegment = point - tail; double t = lineSegment.Dot(pointSegment) / (magnitude * magnitude); + return t; } - double Geometry::DistanceToLineFromPoint(Point tail, Point head, Point point) { // Interpretation: given a line in the form x = a + tu, where u is the @@ -61,7 +61,6 @@ double Geometry::DistanceToLineFromPoint(Point tail, Point head, Point point) return dist.Magnitude() * (angle < HALF_TAU ? +1.0 : -1.0); } - Point Geometry::MirrorPointAroundLine(Point point, Point tail, Point head) { // Get the vector of the intersection of the line and the normal on the @@ -81,7 +80,6 @@ Point Geometry::MirrorPointAroundLine(Point point, Point tail, Point head) return mirroredPoint; } - // // point: The point we're rotating // rotationPoint: The point we're rotating around @@ -95,13 +93,11 @@ Point Geometry::RotatePointAroundPoint(Point point, Point rotationPoint, double return Vector(rotationPoint.x + px, rotationPoint.y + py, 0); } - double Geometry::Determinant(Point p1, Point p2) { return (p1.x * p2.y) - (p2.x * p1.y); } - void Geometry::Intersects(Object * obj1, Object * obj2) { Global::numIntersectPoints = Global::numIntersectParams = 0; @@ -116,7 +112,6 @@ void Geometry::Intersects(Object * obj1, Object * obj2) CheckLineToCircleIntersection(obj2, obj1); } - /* Intersecting line segments: An easier way: @@ -182,7 +177,6 @@ void Geometry::CheckLineToLineIntersection(Object * l1, Object * l2) Global::numIntersectParams = 1; } - void Geometry::CheckCircleToCircleIntersection(Object * c1, Object * c2) { // Set up global vars @@ -236,7 +230,6 @@ void Geometry::CheckCircleToCircleIntersection(Object * c1, Object * c2) Global::numIntersectPoints = 2; } - // // N.B.: l is the line, c is the circle // @@ -300,7 +293,6 @@ void Geometry::CheckLineToCircleIntersection(Object * l, Object * c) } } - // should we just do common trig solves, like AAS, ASA, SAS, SSA? // Law of Cosines: // c² = a² + b² - 2ab * cos(C) @@ -349,7 +341,6 @@ hmm... dunno... *a3 = angle3; } - Point Geometry::GetPointForParameter(Object * obj, double t) { if (obj->type == OTLine) @@ -363,22 +354,126 @@ Point Geometry::GetPointForParameter(Object * obj, double t) return Point(0, 0); } - Point Geometry::Midpoint(Line * line) { return Point((line->p[0].x + line->p[1].x) / 2.0, (line->p[0].y + line->p[1].y) / 2.0); } - /* How to find the tangent of a point off a circle: - • Calculate the midpoint on the point and the center of the circle - • Get the length of the line segment from the and the center divided by two + • Calculate the midpoint of the point and the center of the circle + • Get the length of the line segment from point and the center divided by two • Use that length to construct a circle with the point at the center and the radius equal to that length • The intersection of the two circles are the tangent points +Another way: + + • Find angle between radius and line between point and center + • Angle +/- from line (point to center) are the tangent points + +*/ +void Geometry::FindTangents(Object * c, Point p) +{ + // Set up global vars + Global::numIntersectPoints = Global::numIntersectParams = 0; + + // Get the distance between the point and the center of the circle, the + // length, and the angle. + Vector centerLine(c->p[0], p); + double d = centerLine.Magnitude(); + double clAngle = centerLine.Angle(); + + // If the point is on or inside the circle, there are no tangents. + if (d <= c->radius[0]) + return; + + // Use 'cos(a) = adjacent / hypotenuse' to get the tangent angle + double a = acos(c->radius[0] / d); + + // Finally, find the points of intersection by using +/- the angle found + // from the centerline's angle + Global::intersectPoint[0].x = c->p[0].x + (cos(clAngle + a) * c->radius[0]); + Global::intersectPoint[0].y = c->p[0].y + (sin(clAngle + a) * c->radius[0]); + Global::intersectPoint[1].x = c->p[0].x + (cos(clAngle - a) * c->radius[0]); + Global::intersectPoint[1].y = c->p[0].y + (sin(clAngle - a) * c->radius[0]); + Global::numIntersectPoints = 2; +} + +/* +The extangents can be found by collapsing the circle of smaller radius to a point, and diminishing the larger circle by the radius of the smaller, then treating it like the point-circle case (you have to translate the tangent back out by the length of the radius of the smaller circle once found). + +Not sure what the analogous method for finding the intangents are... :-/ +Looks like the intangent can be found by augmenting the larger circle by the smaller radius, and doing the center of the smaller as the point-circle case again, only translating the line back by the radius of the smaller. */ +void Geometry::FindTangents(Object * c1, Object * c2) +{ + // Set up global vars + Global::numIntersectPoints = Global::numIntersectParams = 0; + + // Find the larger and smaller of the two: + Object * cLg = c1, * cSm = c2; + + if (c2->radius[0] > c1->radius[0]) + cLg = c2, cSm = c1; + + // Get the distance between the point and the center of the circle, the + // length, and the angle. + Vector centerLine(cLg->p[0], cSm->p[0]); + double d = centerLine.Magnitude(); + double clAngle = centerLine.Angle(); + + // If one circle is completely inside the other, there are no tangents. + if ((d + cSm->radius[0]) <= cLg->radius[0]) + return; + // Subtract the radius of the smaller from the larger, and use the point-circle method to find the extangent: + double a = acos((cLg->radius[0] - cSm->radius[0]) / d); + + // Finally, find the points of intersection by using +/- the angle found + // from the centerline's angle + Global::intersectPoint[0].x = cLg->p[0].x + (cos(clAngle + a) * cLg->radius[0]); + Global::intersectPoint[0].y = cLg->p[0].y + (sin(clAngle + a) * cLg->radius[0]); + Global::intersectPoint[1].x = cSm->p[0].x + (cos(clAngle + a) * cSm->radius[0]); + Global::intersectPoint[1].y = cSm->p[0].y + (sin(clAngle + a) * cSm->radius[0]); + + Global::intersectPoint[2].x = cLg->p[0].x + (cos(clAngle - a) * cLg->radius[0]); + Global::intersectPoint[2].y = cLg->p[0].y + (sin(clAngle - a) * cLg->radius[0]); + Global::intersectPoint[3].x = cSm->p[0].x + (cos(clAngle - a) * cSm->radius[0]); + Global::intersectPoint[3].y = cSm->p[0].y + (sin(clAngle - a) * cSm->radius[0]); + Global::numIntersectPoints = 4; + + // If the circles overlap, there are no intangents. + if (d <= (cLg->radius[0] + cSm->radius[0])) + return; + + // Add the radius of the smaller from the larger, and use the point-circle method to find the intangent: + a = acos((cLg->radius[0] + cSm->radius[0]) / d); + + // Finally, find the points of intersection by using +/- the angle found + // from the centerline's angle + Global::intersectPoint[4].x = cLg->p[0].x + (cos(clAngle + a) * cLg->radius[0]); + Global::intersectPoint[4].y = cLg->p[0].y + (sin(clAngle + a) * cLg->radius[0]); + Global::intersectPoint[5].x = cSm->p[0].x + (cos(clAngle - a) * cSm->radius[0]); + Global::intersectPoint[5].y = cSm->p[0].y + (sin(clAngle - a) * cSm->radius[0]); + + Global::intersectPoint[6].x = cLg->p[0].x + (cos(clAngle - a) * cLg->radius[0]); + Global::intersectPoint[6].y = cLg->p[0].y + (sin(clAngle - a) * cLg->radius[0]); + Global::intersectPoint[7].x = cSm->p[0].x + (cos(clAngle + a) * cSm->radius[0]); + Global::intersectPoint[7].y = cSm->p[0].y + (sin(clAngle + a) * cSm->radius[0]); + Global::numIntersectPoints = 8; +} + +// +// Parameter 1: point in question +// Parameter 2, 3: points we are comparing to +// +Point Geometry::NearestTo(Point point, Point p1, Point p2) +{ + double l1 = Vector::Magnitude(point, p1); + double l2 = Vector::Magnitude(point, p2); + + return (l1 < l2 ? p1 : p2); +}