Shamusworld >> Repos - architektonas/blob - src/geometry.cpp

   1 // geometry.cpp: Algebraic geometry helper functions
   2 //
   3 // Part of the Architektonas Project
   4 // (C) 2011 Underground Software
   5 // See the README and GPLv3 files for licensing and warranty information
   6 //
   7 // JLH = James Hammons <jlhamm@acm.org>
   8 //
   9 // WHO  WHEN        WHAT
  10 // ---  ----------  ------------------------------------------------------------
  11 // JLH  08/31/2011  Created this file
  12 //
  13 // NOTE: All methods in this class are static.
  14 //
  15
  16 #include "geometry.h"
  17
  18
  19 Point Geometry::IntersectionOfLineAndLine(Point p1, Point p2, Point p3, Point p4)
  20 {
  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)
  26
  27         double d = ((p1.x - p2.x) * (p3.y - p4.y)) - ((p1.y - p2.y) * (p3.x - p4.x));
  28
  29         // Check for parallel lines, and return sentinel if so
  30         if (d == 0)
  31                 return Point(0, 0, -1);
  32
  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)));
  37
  38         return Point(px / d, py / d, 0);
  39 }
  40
  41
  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)
  45 {
  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.
  51
  52         Vector lineSegment = lp1 - lp2;
  53         double magnitude = lineSegment.Magnitude();
  54         Vector pointSegment = point - lp2;
  55         double t = lineSegment.Dot(pointSegment) / (magnitude * magnitude);
  56         return t;
  57 }
  58
  59
  60 Point Geometry::MirrorPointAroundLine(Point point, Point p1, Point p2)
  61 {
  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;
  66
  67         // Get the point normal to point to the line passed in (p2 is the tail)
  68         Point normalOnLine = p2 + v;
  69
  70         // Make our mirrored vector (head - tail)
  71         Vector mirror = -(point - normalOnLine);
  72
  73         // Find the mirrored point
  74         Point mirroredPoint = normalOnLine + mirror;
  75
  76         return mirroredPoint;
  77 }
  78