X-Git-Url: http://shamusworld.gotdns.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=src%2Fgeometry.cpp;h=e572fab6bbc64d93e8a6e1d85a01dfd6edf2bf2a;hb=f507d97c1b1118834a70332f5f79d8479a6964c0;hp=eacaec7feabc20ee4b8cddce4a15e538f2905bd4;hpb=fd5a80446b2abfdfb9d8951fcc03fb1b55ad707c;p=architektonas diff --git a/src/geometry.cpp b/src/geometry.cpp index eacaec7..e572fab 100644 --- a/src/geometry.cpp +++ b/src/geometry.cpp @@ -15,8 +15,10 @@ #include "geometry.h" #include -#include "line.h" #include "circle.h" +#include "dimension.h" +#include "line.h" +#include "mathconstants.h" Point Geometry::IntersectionOfLineAndLine(Point p1, Point p2, Point p3, Point p4) @@ -61,15 +63,15 @@ double Geometry::ParameterOfLineAndPoint(Point tail, Point head, Point point) } -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); @@ -84,6 +86,7 @@ Point Geometry::MirrorPointAroundLine(Point point, Point p1, Point p2) 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)); @@ -123,23 +126,63 @@ bool Geometry::Intersects(Object * obj1, Object * obj2, double * t, double * s) } #endif +#if 0 // 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; - + Vector v1 = l2->position - l1->position; // q - p +// Vector v2 = l1->position - l2->position; // p - q +//printf("l1: (%lf, %lf) (%lf, %lf), l2: (%lf, %lf) (%lf, %lf)\n", l1->position.x, l1->position.y, l1->endpoint.x, l1->endpoint.y, l2->position.x, l2->position.y, l2->endpoint.x, l2->endpoint.y); 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); + +//printf(" --> R x S = 0! (q - p) x r = %lf\n", qpxr); +//printf(" -->(q - p) . r = %lf, r . r = %lf\n", v1.Dot(r), r.Dot(r)); +//printf(" -->(p - q) . s = %lf, s . s = %lf\n", v2.Dot(s), s.Dot(s)); +//printf(" -->(q - p) . s = %lf, (p - q) . r = %lf\n", v1.Dot(s), v2.Dot(r)); - double t = ((v1.x * s.y) - (s.x * v1.y)) / rxs; - double u = ((v1.x * r.y) - (r.x * v1.y)) / rxs; + // Lines are parallel, so no intersection... + if (qpxr != 0) + return 0; + +#if 0 +//this works IFF the vectors are pointing in the same direction. everything else +//is fucked! + // If (q - p) . r == r . r, t = 1, u = 0 + if (v1.Dot(r) == r.Dot(r)) + t = 1.0, u = 0; + // If (p - q) . s == s . s, t = 0, u = 1 + else if (v2.Dot(s) == s.Dot(s)) + t = 0, u = 1.0; + else + return 0; +#else + // Check to see which endpoints are connected... Four possibilities: + if (l1->position == l2->position) + t = 0, u = 0; + else if (l1->position == l2->endpoint) + t = 0, u = 1.0; + else if (l1->endpoint == l2->position) + t = 1.0, u = 0; + else if (l1->endpoint == l2->endpoint) + t = 1.0, u = 1.0; + else + return 0; +#endif + } + else + { + t = ((v1.x * s.y) - (s.x * v1.y)) / rxs; + u = ((v1.x * r.y) - (r.x * v1.y)) / rxs; + } /* -Now there are five cases: +Now there are five cases (NOTE: only valid if vectors face the same way!): 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. @@ -166,7 +209,15 @@ Now there are five cases: } -// Finds the intesection(s) between a line and a circle (if any) +// Finds the intersection between two lines (if any) +int Geometry::Intersects(Line * l1, Dimension * d1, double * tp/*= 0*/, double * up/*= 0*/) +{ + Line l2(d1->position, d1->endpoint); + return Intersects(l1, &l2, tp, up); +} + + +// Finds the intersection(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 @@ -214,7 +265,16 @@ I'm thinking a better approach to this might be as follows: // Now we have to check for intersection points. // Tangent case: (needs to return something) if ((distance == c->radius) && (t >= 0.0) && (t <= 1.0)) + { + // Need to set tp & up to something... !!! FIX !!! + if (tp) + *tp = t; + + if (up) + *up = Vector(c->position, p).Angle(); + return 1; + } // The line intersects the circle in two points (possibly). Use Pythagorus // to find them for testing. @@ -251,3 +311,116 @@ I'm thinking a better approach to this might be as follows: } +// Finds the intersection(s) between a circle and a circle (if any) +// There can be 0, 1, or 2 intersections. +// Returns the angles of the points of intersection in tp thru wp, with the +// angles returned as c1, c2, c1, c2 (if applicable--in the 1 intersection case, +// only the first two angles are returned: c1, c2). +int Geometry::Intersects(Circle * c1, Circle * c2, double * tp/*= 0*/, double * up/*= 0*/, double * vp/*= 0*/, double * wp/*= 0*/, Point * p1/*= 0*/, Point * p2/*= 0*/) +{ + // Get the distance between centers. If the distance plus the radius of the + // smaller circle is less than the radius of the larger circle, there is no + // intersection. If the distance is greater than the sum of the radii, + // there is no intersection. If the distance is equal to the sum of the + // radii, they are tangent and intersect at one point. Otherwise, they + // intersect at two points. + Vector centerLine(c1->position, c2->position); + double d = centerLine.Magnitude(); +//printf("Circle #1: pos=<%lf, %lf>, r=%lf\n", c1->position.x, c1->position.y, c1->radius); +//printf("Circle #2: pos=<%lf, %lf>, r=%lf\n", c2->position.x, c2->position.y, c2->radius); +//printf("Distance between #1 & #2: %lf\n", d); + + // Check to see if we actually have an intersection, and return failure if not + if ((fabs(c1->radius - c2->radius) > d) || ((c1->radius + c2->radius) < d)) + return 0; + + // There are *two* tangent cases! + if (((c1->radius + c2->radius) == d) || (fabs(c1->radius - c2->radius) == d)) + { + // Need to return something in tp & up!! !!! FIX !!! [DONE] + if (tp) + *tp = centerLine.Angle(); + + if (up) + *up = centerLine.Angle() + PI; + + return 1; + } + + // Find the distance from the center of c1 to the perpendicular chord + // (which contains the points of intersection) + double x = ((d * d) - (c2->radius * c2->radius) + (c1->radius * c1->radius)) + / (2.0 * d); + // Find the the length of the perpendicular chord +// Not needed...! + double a = sqrt((-d + c2->radius - c1->radius) * (-d - c2->radius + c1->radius) * (-d + c2->radius + c1->radius) * (d + c2->radius + c1->radius)) / d; + + // Now, you can use pythagorus to find the length of the hypotenuse, but we + // already know that length, it's the radius! :-P + // What's needed is the angle of the center line and the radial line. Since + // there's two intersection points, there's also four angles (two for each + // circle)! + // We can use the arccos to find the angle using just the radius and the + // distance to the perpendicular chord...! + double angleC1 = acos(x / c1->radius); + double angleC2 = acos((d - x) / c2->radius); + + if (tp) + *tp = centerLine.Angle() - angleC1; + + if (up) + *up = (centerLine.Angle() + PI) - angleC2; + + if (vp) + *vp = centerLine.Angle() + angleC1; + + if (wp) + *wp = (centerLine.Angle() + PI) + angleC2; + + if (p1) + *p1 = c1->position + (centerLine.Unit() * x) + (Vector::Normal(Vector(), centerLine) * (a / 2.0)); + + if (p2) + *p2 = c1->position + (centerLine.Unit() * x) - (Vector::Normal(Vector(), centerLine) * (a / 2.0)); + + return 2; +} +#endif + +// should we just do common trig solves, like AAS, ASA, SAS, SSA? +// Law of Cosines: +// c^2 = a^2 + b^2 -2ab*cos(C) +// Solving for C: +// cos(C) = (c^2 - a^2 - b^2) / -2ab = (a^2 + b^2 - c^2) / 2ab +// Law of Sines: +// a / sin A = b / sin B = c / sin C + +// 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); + + // Check for a valid triangle + if ((cosine1 < -1.0) || (cosine1 > 1.0)) + return; + + double angle1 = acos(cosine1); + + // Use law of sines to find 2nd & 3rd angles +// sin A / a = sin B / b +// sin B = (sin A / a) * b + 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; +} +