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.
19 Point Geometry::IntersectionOfLineAndLine(Point p1, Point p2, Point p3, Point p4)
21 // Find the intersection of the lines by formula:
22 // px = (x1y2 - y1x2)(x3 - x4) - (x1 - x2)(x3y4 - y3x4)
23 // py = (x1y2 - y1x2)(y3 - y4) - (y1 - y2)(x3y4 - y3x4)
24 // d = (x1 - x2)(y3 - y4) - (y1 - y2)(x3 - x4) = 0 if lines are parallel
25 // Intersection is (px / d, py / d)
27 double d = ((p1.x - p2.x) * (p3.y - p4.y)) - ((p1.y - p2.y) * (p3.x - p4.x));
29 // Check for parallel lines, and return sentinel if so
31 return Point(0, 0, -1);
33 double px = (((p1.x * p2.y) - (p1.y * p2.x)) * (p3.x - p4.x))
34 - ((p1.x - p2.x) * ((p3.x * p4.y) - (p3.y * p4.x)));
35 double py = (((p1.x * p2.y) - (p1.y * p2.x)) * (p3.y - p4.y))
36 - ((p1.y - p2.y) * ((p3.x * p4.y) - (p3.y * p4.x)));
38 return Point(px / d, py / d, 0);
42 // Returns the parameter of a point in space to this vector. If the parameter
43 // is between 0 and 1, the normal of the vector to the point is on the vector.
44 double Geometry::ParameterOfLineAndPoint(Point lp1, Point lp2, Point point)
46 // Geometric interpretation:
47 // The parameterized point on the vector lineSegment is where the normal of
48 // the lineSegment to the point intersects lineSegment. If the pp < 0, then
49 // the perpendicular lies beyond the 1st endpoint. If pp > 1, then the
50 // perpendicular lies beyond the 2nd endpoint.
52 Vector lineSegment = lp1 - lp2;
53 double magnitude = lineSegment.Magnitude();
54 Vector pointSegment = point - lp2;
55 double t = lineSegment.Dot(pointSegment) / (magnitude * magnitude);
60 Point Geometry::MirrorPointAroundLine(Point point, Point p1, Point p2)
62 // Get the vector of the intersection of the line and the normal on the
63 // line to the point in question.
64 double t = ParameterOfLineAndPoint(p1, p2, point);
65 Vector v = Vector(p1, p2) * t;
67 // Get the point normal to point to the line passed in (p2 is the tail)
68 Point normalOnLine = p2 + v;
70 // Make our mirrored vector (head - tail)
71 Vector mirror = -(point - normalOnLine);
73 // Find the mirrored point
74 Point mirroredPoint = normalOnLine + mirror;
80 Point Geometry::RotatePointAroundPoint(Point point, Point rotationPoint, double angle)
82 Vector v = Vector(point, rotationPoint);
83 double px = (v.x * cos(angle)) - (v.y * sin(angle));
84 double py = (v.x * sin(angle)) + (v.y * cos(angle));
86 return Vector(rotationPoint.x + px, rotationPoint.y + py, 0);