X-Git-Url: http://shamusworld.gotdns.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=src%2Fgeometry.cpp;h=e572fab6bbc64d93e8a6e1d85a01dfd6edf2bf2a;hb=f507d97c1b1118834a70332f5f79d8479a6964c0;hp=fdceb8eff6a332f618f83b2a334e6c38a84a4323;hpb=4b37ccbdf263a4798e53a62e33d869a728ace283;p=architektonas

diff --git a/src/geometry.cpp b/src/geometry.cpp
index fdceb8e..e572fab 100644
--- a/src/geometry.cpp
+++ b/src/geometry.cpp
@@ -14,6 +14,11 @@
 //
 
 #include "geometry.h"
+#include <math.h>
+#include "circle.h"
+#include "dimension.h"
+#include "line.h"
+#include "mathconstants.h"
 
 
 Point Geometry::IntersectionOfLineAndLine(Point p1, Point p2, Point p3, Point p4)
@@ -41,7 +46,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,23 +55,23 @@ 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;
 }
 
 
-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);
@@ -76,3 +82,345 @@ Point Geometry::MirrorPointAroundLine(Point point, Point p1, Point p2)
 	return mirroredPoint;
 }
 
+
+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));
+
+	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
+
+#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;	// 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)
+	{
+		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));
+
+		// 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 (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.
+
+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 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
+	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))
+	{
+		// 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.
+	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
+}
+
+
+// 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;
+}
+