#include "geometry.h"
#include <math.h>
+#include "line.h"
+#include "circle.h"
+
Point Geometry::IntersectionOfLineAndLine(Point p1, Point p2, Point p3, Point p4)
{
// 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.
-double Geometry::ParameterOfLineAndPoint(Point lp1, Point lp2, Point point)
+// Note: lp1 is the tail, lp2 is the head of the line (vector).
+double Geometry::ParameterOfLineAndPoint(Point tail, Point head, Point point)
{
// Geometric interpretation:
// The parameterized point on the vector lineSegment is where the normal of
// the perpendicular lies beyond the 1st endpoint. If pp > 1, then the
// perpendicular lies beyond the 2nd endpoint.
- Vector lineSegment = lp1 - lp2;
+ Vector lineSegment = head - tail;
double magnitude = lineSegment.Magnitude();
- Vector pointSegment = point - lp2;
+ Vector pointSegment = point - tail;
double t = lineSegment.Dot(pointSegment) / (magnitude * magnitude);
return t;
}
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);
+}
+
+
+/*
+Intersecting line segments:
+An easier way:
+Segment L1 has edges A=(a1,a2), A'=(a1',a2').
+Segment L2 has edges B=(b1,b2), B'=(b1',b2').
+Segment L1 is the set of points tA'+(1-t)A, where 0<=t<=1.
+Segment L2 is the set of points sB'+(1-s)B, where 0<=s<=1.
+Segment L1 meet segment L2 if and only if for some t and s we have
+tA'+(1-t)A=sB'+(1-s)B
+The solution of this with respect to t and s is
+
+t=((-b?'a?+b?'b?+b?a?+a?b?'-a?b?-b?b?')/(b?'a?'-b?'a?-b?a?'+b?a?-a?'b?'+a?'b?+a?b?'-a?b?))
+
+s=((-a?b?+a?'b?-a?a?'+b?a?+a?'a?-b?a?')/(b?'a?'-b?'a?-b?a?'+b?a?-a?'b??+a?'b?+a?b?'-a?b?))
+
+So check if the above two numbers are both >=0 and <=1.
+*/
+
+
+#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*/)
+{
+ Vector r(l1->position, l1->endpoint);
+ Vector s(l2->position, l2->endpoint);
+ Vector v1 = l2->position - l1->position;
+// Vector v1 = l1->position - l2->position;
+
+ double rxs = (r.x * s.y) - (s.x * r.y);
+
+ if (rxs == 0)
+ return 0;
+
+ 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:
+
+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 (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;
+}
+
+
+// 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);
+
+ double discriminant = ((c->radius * c->radius) * (dr * dr)) - (determinant * determinant);
+
+ if (discriminant < 0)
+ return false;
+
+
+
+ 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))
+ 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))
+ {
+ intersections++;
+ }
+
+ return intersections;
+#endif
+}
+
+
projects / architektonas / blobdiff