+//
// geometry.cpp: Algebraic geometry helper functions
//
// Part of the Architektonas Project
#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).
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
+ // unit vector of the line, a is the tail and t is a parameter which
+ // describes the line, the distance of a point p to the line is given by:
+ // || (a - p) - ((a - p) • u) u ||
+ // We go an extra step: we set the sign to reflect which side of the line
+ // it's on (+ == to the left if head points away from you, - == to the
+ // right)
+ Vector line(tail, head);
+ Vector u = line.Unit();
+ Vector a_p = tail - point;
+ Vector dist = a_p - (u * (a_p).Dot(u));
+
+ double angle = Vector::Angle(tail, point) - line.Angle();
+
+ if (angle < 0)
+ angle += TAU;
+
+ return dist.Magnitude() * (angle < HALF_TAU ? +1.0 : -1.0);
+}
Point Geometry::MirrorPointAroundLine(Point point, Point tail, Point head)
{
return mirroredPoint;
}
-
//
// point: The point we're rotating
// rotationPoint: The point we're rotating around
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;
CheckLineToCircleIntersection(obj2, obj1);
}
-
/*
Intersecting line segments:
An easier way:
double rxs = (r.x * s.y) - (s.x * r.y);
double t, u;
+ // The angle is zero, so the lines probably overlap, or are parallel. Either way, there is either INFINITE intersections, or zero. Either way, the result is useless to us. It does present a bit of an inconsistency though: lines connected at their endpoints that aren't at a zero angle will show as overlapping (the only case this could even REMOTELY be useful is when the angle between is 180°--not zero, as zero is the degenerate case). :-P
if (rxs == 0)
{
- double qpxr = (v1.x * r.y) - (r.x * v1.y);
+// WHY would you do this??? The lines overlap at an INFINITE number of points!
+// The assumption is that the angle is 180°, not 0°.
+ // If we want to detect the degenerate case, we can check the parameter of the endpoints of the one line to the other. If any of the parameters are in (0, 1), then it's the degenerate case (we would check the endpoints of the shorter segment against the longer).
+/* double qpxr = (v1.x * r.y) - (r.x * v1.y);
- // Lines are parallel, so no intersection...
+ // Line segments are parallel, so no intersection...
if (qpxr != 0)
return;
+ // Otherwise, the segments are colinear. Need to check for the 0° (degenerate) vs the 180° (OK) case.
+ Object * larger = l1;
+ Object * smaller = l2;
+
+ if (r->Magnitude() < s->Magnitude())
+ {
+ larger = l2;
+ smaller = l1;
+ }
+
+ double param1 = ParameterOfLineAndPoint(larger->p[0], larger->p[1], smaller->p[0]);
+ double param2 = ParameterOfLineAndPoint(larger->p[0], larger->p[1], smaller->p[1]);
+
+ // Check for the degenerate case, and return if found
+ if ((param1 > 0 && param1 < 1.0) || (param2 > 0 && param2 < 1.0))
+ return;
+
+//// or just use AngleBetween: Nah, won't work...
+
// Check to see which endpoints are connected... Four possibilities:
if (l1->p[0] == l2->p[0])
t = 0, u = 0;
t = 1.0, u = 0;
else if (l1->p[1] == l2->p[1])
t = 1.0, u = 1.0;
- else
+ else*/
return;
}
else
u = ((v1.x * r.y) - (r.x * v1.y)) / rxs;
}
+ // Check that the parameters are above the epsilon, otherwise clamp them to
+ // zero or one, as the case may be
+ if (fabs(t) < EPSILON)
+ t = 0;
+ else if (fabs(1.0 - t) < EPSILON)
+ t = 1.0;
+
+ if (fabs(u) < EPSILON)
+ u = 0;
+ else if (fabs(1.0 - u) < EPSILON)
+ u = 1.0;
+
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;
+ Global::numIntersectParams = 2;
}
-
void Geometry::CheckCircleToCircleIntersection(Object * c1, Object * c2)
{
// Set up global vars
Global::numIntersectPoints = 2;
}
-
//
// N.B.: l is the line, c is the circle
//
}
}
-
// should we just do common trig solves, like AAS, ASA, SAS, SSA?
// Law of Cosines:
// c² = a² + b² - 2ab * cos(C)
*a3 = angle3;
}
-
Point Geometry::GetPointForParameter(Object * obj, double t)
{
if (obj->type == OTLine)
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);
+}
+
+Vector Geometry::GetNormalOfPointAndLine(Point p, Line * l)
+{
+ Vector normal = Vector::Normal(l->p[0], l->p[1]);
+ normal.Unit();
+ double dir = Vector::Dot(p - l->p[0], normal);
+
+ if (dir < 0)
+ normal = -normal;
+
+ return normal;
+}
projects / architektonas / blobdiff