1 // geometry.cpp: Algebraic geometry helper functions
3 // Part of the Architektonas Project
4 // (C) 2011 Underground Software
5 // See the README and GPLv3 files for licensing and warranty information
7 // JLH = James Hammons <jlhamm@acm.org>
10 // --- ---------- ------------------------------------------------------------
11 // JLH 08/31/2011 Created this file
13 // NOTE: All methods in this class are static.
20 #include "mathconstants.h"
23 // Returns the parameter of a point in space to this vector. If the parameter
24 // is between 0 and 1, the normal of the vector to the point is on the vector.
25 // Note: lp1 is the tail, lp2 is the head of the line (vector).
26 double Geometry::ParameterOfLineAndPoint(Point tail, Point head, Point point)
28 // Geometric interpretation:
29 // The parameterized point on the vector lineSegment is where the normal of
30 // the lineSegment to the point intersects lineSegment. If the pp < 0, then
31 // the perpendicular lies beyond the 1st endpoint. If pp > 1, then the
32 // perpendicular lies beyond the 2nd endpoint.
34 Vector lineSegment = head - tail;
35 double magnitude = lineSegment.Magnitude();
36 Vector pointSegment = point - tail;
37 double t = lineSegment.Dot(pointSegment) / (magnitude * magnitude);
42 double Geometry::DistanceToLineFromPoint(Point tail, Point head, Point point)
44 // Interpretation: given a line in the form x = a + tu, where u is the
45 // unit vector of the line, a is the tail and t is a parameter which
46 // describes the line, the distance of a point p to the line is given by:
47 // || (a - p) - ((a - p) . u) u ||
48 // We go an extra step: we set the sign to reflect which side of the line
49 // it's on (+ == to the left if head points away from you, - == to the
51 Vector line(tail, head);
52 Vector u = line.Unit();
53 Vector a_p = tail - point;
54 Vector dist = a_p - (u * (a_p).Dot(u));
56 double angle = Vector::Angle(tail, point) - line.Angle();
61 return dist.Magnitude() * (angle < HALF_TAU ? +1.0 : -1.0);
65 Point Geometry::MirrorPointAroundLine(Point point, Point tail, Point head)
67 // Get the vector of the intersection of the line and the normal on the
68 // line to the point in question.
69 double t = ParameterOfLineAndPoint(tail, head, point);
70 Vector v = Vector(tail, head) * t;
72 // Get the point normal to point to the line passed in
73 Point normalOnLine = tail + v;
75 // Make our mirrored vector (head - tail)
76 Vector mirror = -(point - normalOnLine);
78 // Find the mirrored point
79 Point mirroredPoint = normalOnLine + mirror;
86 // point: The point we're rotating
87 // rotationPoint: The point we're rotating around
89 Point Geometry::RotatePointAroundPoint(Point point, Point rotationPoint, double angle)
91 Vector v = Vector(rotationPoint, point);
92 double px = (v.x * cos(angle)) - (v.y * sin(angle));
93 double py = (v.x * sin(angle)) + (v.y * cos(angle));
95 return Vector(rotationPoint.x + px, rotationPoint.y + py, 0);
99 double Geometry::Determinant(Point p1, Point p2)
101 return (p1.x * p2.y) - (p2.x * p1.y);
105 void Geometry::Intersects(Object * obj1, Object * obj2)
107 Global::numIntersectPoints = Global::numIntersectParams = 0;
109 if ((obj1->type == OTLine) && (obj2->type == OTLine))
110 CheckLineToLineIntersection(obj1, obj2);
111 else if ((obj1->type == OTCircle) && (obj2->type == OTCircle))
112 CheckCircleToCircleIntersection(obj1, obj2);
113 else if ((obj1->type == OTLine) && (obj2->type == OTCircle))
114 CheckLineToCircleIntersection(obj1, obj2);
115 else if ((obj1->type == OTCircle) && (obj2->type == OTLine))
116 CheckLineToCircleIntersection(obj2, obj1);
121 Intersecting line segments:
123 Segment L1 has edges A=(a1,a2), A'=(a1',a2').
124 Segment L2 has edges B=(b1,b2), B'=(b1',b2').
125 Segment L1 is the set of points tA'+(1-t)A, where 0<=t<=1.
126 Segment L2 is the set of points sB'+(1-s)B, where 0<=s<=1.
127 Segment L1 meet segment L2 if and only if for some t and s we have
128 tA'+(1-t)A=sB'+(1-s)B
129 The solution of this with respect to t and s is
131 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?))
133 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?))
135 So check if the above two numbers are both >=0 and <=1.
139 // Finds the intersection between two lines (if any)
140 void Geometry::CheckLineToLineIntersection(Object * l1, Object * l2)
142 Global::numIntersectPoints = Global::numIntersectParams = 0;
144 Vector r(l1->p[0], l1->p[1]);
145 Vector s(l2->p[0], l2->p[1]);
146 Vector v1 = l2->p[0] - l1->p[0]; // q - p
148 double rxs = (r.x * s.y) - (s.x * r.y);
153 double qpxr = (v1.x * r.y) - (r.x * v1.y);
155 // Lines are parallel, so no intersection...
159 // Check to see which endpoints are connected... Four possibilities:
160 if (l1->p[0] == l2->p[0])
162 else if (l1->p[0] == l2->p[1])
164 else if (l1->p[1] == l2->p[0])
166 else if (l1->p[1] == l2->p[1])
173 t = ((v1.x * s.y) - (s.x * v1.y)) / rxs;
174 u = ((v1.x * r.y) - (r.x * v1.y)) / rxs;
177 Global::intersectParam[0] = t;
178 Global::intersectParam[1] = u;
180 // If the parameters are in range, we have overlap!
181 if ((t >= 0) && (t <= 1.0) && (u >= 0) && (u <= 1.0))
182 Global::numIntersectParams = 1;
186 void Geometry::CheckCircleToCircleIntersection(Object * c1, Object * c2)
188 // Set up global vars
189 Global::numIntersectPoints = Global::numIntersectParams = 0;
191 // Get the distance between the centers of the circles
192 Vector centerLine(c1->p[0], c2->p[0]);
193 double d = centerLine.Magnitude();
194 double clAngle = centerLine.Angle();
196 // If the distance between centers is greater than the sum of the radii or
197 // less than the difference between the radii, there is NO intersection
198 if ((d > (c1->radius[0] + c2->radius[0]))
199 || (d < fabs(c1->radius[0] - c2->radius[0])))
202 // If the distance between centers is equal to the sum of the radii or
203 // equal to the difference between the radii, the intersection is tangent
205 if (d == (c1->radius[0] + c2->radius[0]))
207 Global::intersectPoint[0].x = c1->p[0].x + (cos(clAngle) * c1->radius[0]);
208 Global::intersectPoint[0].y = c1->p[0].y + (sin(clAngle) * c1->radius[0]);
209 Global::numIntersectPoints = 1;
212 else if (d == fabs(c1->radius[0] - c2->radius[0]))
214 double sign = (c1->radius[0] > c2->radius[0] ? +1 : -1);
215 Global::intersectPoint[0].x = c1->p[0].x + (cos(clAngle) * c1->radius[0] * sign);
216 Global::intersectPoint[0].y = c1->p[0].y + (sin(clAngle) * c1->radius[0] * sign);
217 Global::numIntersectPoints = 1;
222 c² = a² + b² - 2ab·cos µ
223 2ab·cos µ = a² + b² - c²
224 cos µ = (a² + b² - c²) / 2ab
226 // Use the Law of Cosines to find the angle between the centerline and the
227 // radial line on Circle #1
228 double a = acos(((c1->radius[0] * c1->radius[0]) + (d * d) - (c2->radius[0] * c2->radius[0])) / (2.0 * c1->radius[0] * d));
230 // Finally, find the points of intersection by using +/- the angle found
231 // from the centerline's angle
232 Global::intersectPoint[0].x = c1->p[0].x + (cos(clAngle + a) * c1->radius[0]);
233 Global::intersectPoint[0].y = c1->p[0].y + (sin(clAngle + a) * c1->radius[0]);
234 Global::intersectPoint[1].x = c1->p[0].x + (cos(clAngle - a) * c1->radius[0]);
235 Global::intersectPoint[1].y = c1->p[0].y + (sin(clAngle - a) * c1->radius[0]);
236 Global::numIntersectPoints = 2;
241 // N.B.: l is the line, c is the circle
243 void Geometry::CheckLineToCircleIntersection(Object * l, Object * c)
245 // Set up global vars
246 Global::numIntersectPoints = Global::numIntersectParams = 0;
248 // Step 1: Find shortest distance from center of circle to the infinite line
249 double t = ParameterOfLineAndPoint(l->p[0], l->p[1], c->p[0]);
250 Point p = l->p[0] + (Vector(l->p[0], l->p[1]) * t);
251 Vector radial = Vector(c->p[0], p);
252 double distance = radial.Magnitude();
254 // Step 2: See if we have 0, 1, or 2 intersection points
256 // Case #1: No intersection points
257 if (distance > c->radius[0])
259 // Case #2: One intersection point (possibly--tangent)
260 else if (distance == c->radius[0])
262 // Only intersects if the parameter is on the line segment!
263 if ((t >= 0.0) && (t <= 1.0))
265 Global::intersectPoint[0] = c->p[0] + radial;
266 Global::numIntersectPoints = 1;
272 // Case #3: Two intersection points (possibly--secant)
274 // So, we have the line, and the perpendicular from the center of the
275 // circle to the line. Now figure out where the intersection points are.
276 // This is a right triangle, though do we really know all the sides?
277 // Don't need to, 2 is enough for Pythagoras :-)
278 // Radius is the hypotenuse, so we have to use c² = a² + b² => a² = c² - b²
279 double perpendicularLength = sqrt((c->radius[0] * c->radius[0]) - (distance * distance));
281 // Now, find the intersection points using the length...
282 Vector lineUnit = Vector(l->p[0], l->p[1]).Unit();
283 Point i1 = p + (lineUnit * perpendicularLength);
284 Point i2 = p - (lineUnit * perpendicularLength);
286 // Next we need to see if they are on the line segment...
287 double u = ParameterOfLineAndPoint(l->p[0], l->p[1], i1);
288 double v = ParameterOfLineAndPoint(l->p[0], l->p[1], i2);
290 if ((u >= 0.0) && (u <= 1.0))
292 Global::intersectPoint[Global::numIntersectPoints] = i1;
293 Global::numIntersectPoints++;
296 if ((v >= 0.0) && (v <= 1.0))
298 Global::intersectPoint[Global::numIntersectPoints] = i2;
299 Global::numIntersectPoints++;
304 // should we just do common trig solves, like AAS, ASA, SAS, SSA?
306 // c² = a² + b² - 2ab * cos(C)
308 // cos(C) = (c² - a² - b²) / -2ab = (a² + b² - c²) / 2ab
310 // a / sin A = b / sin B = c / sin C
312 // Solve the angles of the triangle given the sides. Angles returned are
313 // opposite of the given sides (so a1 consists of sides s2 & s3, and so on).
314 void Geometry::FindAnglesForSides(double s1, double s2, double s3, double * a1, double * a2, double * a3)
316 // Use law of cosines to find 1st angle
317 double cosine1 = ((s2 * s2) + (s3 * s3) - (s1 * s1)) / (2.0 * s2 * s3);
319 // Check for a valid triangle
320 if ((cosine1 < -1.0) || (cosine1 > 1.0))
323 double angle1 = acos(cosine1);
325 // Use law of sines to find 2nd & 3rd angles
326 // sin A / a = sin B / b
327 // sin B = (sin A / a) * b
328 // B = arcsin( sin A * (b / a))
329 // ??? ==> B = A * arcsin(b / a)
332 sin B = sin A * (b / a)
333 sin B / sin A = b / a
334 arcsin( sin B / sin A ) = arcsin( b / a )
339 double angle2 = asin(s2 * (sin(angle1) / s1));
340 double angle3 = asin(s3 * (sin(angle1) / s1));
353 Point Geometry::GetPointForParameter(Object * obj, double t)
355 if (obj->type == OTLine)
357 // Translate line vector to the origin, then add the scaled vector to
358 // initial point of the line.
359 Vector v = obj->p[1] - obj->p[0];
360 return obj->p[0] + (v * t);
367 Point Geometry::Midpoint(Line * line)
369 return Point((line->p[0].x + line->p[1].x) / 2.0,
370 (line->p[0].y + line->p[1].y) / 2.0);
375 How to find the tangent of a point off a circle:
377 • Calculate the midpoint on the point and the center of the circle
378 • Get the length of the line segment from the and the center divided by two
379 • Use that length to construct a circle with the point at the center and the
380 radius equal to that length
381 • The intersection of the two circles are the tangent points