X-Git-Url: http://shamusworld.gotdns.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=src%2Fgeometry.cpp;h=eacaec7feabc20ee4b8cddce4a15e538f2905bd4;hb=fd5a80446b2abfdfb9d8951fcc03fb1b55ad707c;hp=5f9a30b964f07348db24af44482508c52bacf668;hpb=c58b8a9f8b1ae5494857fc423ed8e33b2bbcf329;p=architektonas diff --git a/src/geometry.cpp b/src/geometry.cpp index 5f9a30b..eacaec7 100644 --- a/src/geometry.cpp +++ b/src/geometry.cpp @@ -15,6 +15,9 @@ #include "geometry.h" #include +#include "line.h" +#include "circle.h" + Point Geometry::IntersectionOfLineAndLine(Point p1, Point p2, Point p3, Point p4) { @@ -41,7 +44,8 @@ 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 @@ -49,9 +53,9 @@ double Geometry::ParameterOfLineAndPoint(Point lp1, Point lp2, Point point) // 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; } @@ -86,3 +90,164 @@ 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); +} + + +/* +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 +} + +