#include "geometry.h"
#include <math.h>
-#include "line.h"
-#include "circle.h"
-
-
-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);
-}
+#include <stdio.h>
+#include "global.h"
+#include "mathconstants.h"
// Returns the parameter of a point in space to this vector. If the parameter
}
-Point Geometry::MirrorPointAroundLine(Point point, Point p1, Point p2)
+Point Geometry::MirrorPointAroundLine(Point point, Point tail, Point head)
{
// Get the vector of the intersection of the line and the normal on the
// line to the point in question.
- double t = ParameterOfLineAndPoint(p1, p2, point);
- Vector v = Vector(p1, p2) * t;
+ double t = ParameterOfLineAndPoint(tail, head, point);
+ Vector v = Vector(tail, head) * t;
- // Get the point normal to point to the line passed in (p2 is the tail)
- Point normalOnLine = p2 + v;
+ // Get the point normal to point to the line passed in
+ Point normalOnLine = tail + v;
// Make our mirrored vector (head - tail)
Vector mirror = -(point - normalOnLine);
}
+//
+// point: The point we're rotating
+// rotationPoint: The point we're rotating around
+//
Point Geometry::RotatePointAroundPoint(Point point, Point rotationPoint, double angle)
{
- Vector v = Vector(point, rotationPoint);
+ Vector v = Vector(rotationPoint, point);
double px = (v.x * cos(angle)) - (v.y * sin(angle));
double py = (v.x * sin(angle)) + (v.y * cos(angle));
}
+void Geometry::Intersects(Object * obj1, Object * obj2)
+{
+ Global::numIntersectPoints = Global::numIntersectParams = 0;
+
+ if ((obj1->type == OTLine) && (obj2->type == OTLine))
+ 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);
+}
+
+
/*
Intersecting line segments:
An easier way:
*/
-#if 0
-// Finds the intesection between two objects (if any)
-bool Geometry::Intersects(Object * obj1, Object * obj2, double * t, double * s)
-{
-}
-#endif
-
// Finds the intersection between two lines (if any)
-int Geometry::Intersects(Line * l1, Line * l2, double * tp/*= 0*/, double * up/*= 0*/)
+void Geometry::CheckLineToLineIntersection(Object * l1, Object * l2)
{
- Vector r(l1->position, l1->endpoint);
- Vector s(l2->position, l2->endpoint);
- Vector v1 = l2->position - l1->position;
-// Vector v1 = l1->position - l2->position;
+ 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
double rxs = (r.x * s.y) - (s.x * r.y);
+ double t, u;
if (rxs == 0)
- return 0;
+ {
+ double qpxr = (v1.x * r.y) - (r.x * v1.y);
+
+ // Lines are parallel, so no intersection...
+ if (qpxr != 0)
+ return;
+
+ // Check to see which endpoints are connected... Four possibilities:
+ if (l1->p[0] == l2->p[0])
+ t = 0, u = 0;
+ else if (l1->p[0] == l2->p[1])
+ t = 0, u = 1.0;
+ else if (l1->p[1] == l2->p[0])
+ t = 1.0, u = 0;
+ else if (l1->p[1] == l2->p[1])
+ t = 1.0, u = 1.0;
+ else
+ return;
+ }
+ else
+ {
+ t = ((v1.x * s.y) - (s.x * v1.y)) / rxs;
+ u = ((v1.x * r.y) - (r.x * v1.y)) / rxs;
+ }
+
+ 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;
+}
+
+
+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]))
+ {
+ 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;
+ }
- double t = ((v1.x * s.y) - (s.x * v1.y)) / rxs;
- double u = ((v1.x * r.y) - (r.x * v1.y)) / rxs;
/*
-Now there are five cases:
+ 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));
+
+ // 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;
+}
-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.
+//
+// N.B.: l is the line, c is the circle
+//
+void Geometry::CheckLineToCircleIntersection(Object * l, Object * c)
+{
+ // 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();
+
+ // Step 2: See if we have 0, 1, or 2 intersection points
+
+ // 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;
+ }
+
+ return;
+ }
-3. If r × s = 0 and (q − p) × r ≠ 0, then the two lines are parallel and non-intersecting.
+ // Case #3: Two intersection points (possibly--secant)
-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.
+ // 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));
-5. Otherwise, the two line segments are not parallel but do not intersect.
-*/
- // Return parameter values, if user passed in valid pointers
- if (tp)
- *tp = t;
+ // Now, find the intersection points using the length...
+ Vector lineUnit = Vector(l->p[0], l->p[1]).Unit();
+ Point i1 = p + (lineUnit * perpendicularLength);
+ Point i2 = p - (lineUnit * perpendicularLength);
- if (up)
- *up = u;
+ // 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);
- // If the parameters are in range, we have overlap!
- if ((t >= 0) && (t <= 1.0) && (u >= 0) && (u <= 1.0))
- return 1;
+ if ((u >= 0.0) && (u <= 1.0))
+ {
+ Global::intersectPoint[Global::numIntersectPoints] = i1;
+ Global::numIntersectPoints++;
+ }
- return 0;
+ if ((v >= 0.0) && (v <= 1.0))
+ {
+ Global::intersectPoint[Global::numIntersectPoints] = i2;
+ Global::numIntersectPoints++;
+ }
}
-// Finds the intesection(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);
+// should we just do common trig solves, like AAS, ASA, SAS, SSA?
+// Law of Cosines:
+// c² = a² + b² - 2ab * cos(C)
+// Solving for C:
+// cos(C) = (c² - a² - b²) / -2ab = (a² + b² - c²) / 2ab
+// Law of Sines:
+// a / sin A = b / sin B = c / sin C
- double discriminant = ((c->radius * c->radius) * (dr * dr)) - (determinant * determinant);
+// Solve the angles of the triangle given the sides. Angles returned are
+// opposite of the given sides (so a1 consists of sides s2 & s3, and so on).
+void Geometry::FindAnglesForSides(double s1, double s2, double s3, double * a1, double * a2, double * a3)
+{
+ // Use law of cosines to find 1st angle
+ double cosine1 = ((s2 * s2) + (s3 * s3) - (s1 * s1)) / (2.0 * s2 * s3);
- if (discriminant < 0)
- return false;
+ // Check for a valid triangle
+ if ((cosine1 < -1.0) || (cosine1 > 1.0))
+ return;
-
+ double angle1 = acos(cosine1);
- return true;
-#else
+ // Use law of sines to find 2nd & 3rd angles
+// sin A / a = sin B / b
+// sin B = (sin A / a) * b
+// B = arcsin( sin A * (b / a))
+// ??? ==> B = A * arcsin(b / a)
/*
-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.
+Well, look here:
+sin B = sin A * (b / a)
+sin B / sin A = b / a
+arcsin( sin B / sin A ) = arcsin( b / a )
+
+hmm... dunno...
*/
- 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))
- return 1;
-
- // 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))
- {
- intersections++;
- }
- if ((t2 >= 0) && (t2 <= 1.0))
+ double angle2 = asin(s2 * (sin(angle1) / s1));
+ double angle3 = asin(s3 * (sin(angle1) / s1));
+
+ if (a1)
+ *a1 = angle1;
+
+ if (a2)
+ *a2 = angle2;
+
+ if (a3)
+ *a3 = angle3;
+}
+
+
+Point Geometry::GetPointForParameter(Object * obj, double t)
+{
+ if (obj->type == OTLine)
{
- intersections++;
+ // Translate line vector to the origin, then add the scaled vector to
+ // initial point of the line.
+ Vector v = obj->p[1] - obj->p[0];
+ return obj->p[0] + (v * t);
}
- return intersections;
-#endif
+ return Point(0, 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
+ • 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
+
+*/
+
projects / architektonas / blobdiff