2D line intersection

a couple 2D line intersection routines for C and Script.

in C:
mIntersectLineLine (Point2F, Point2F, Point2F, Point2F)
mIntersectLineSegmentLineSegment (Point2F, Point2F, Point2F, Point2F)

in script:
intersectLineLine2D (Point2F, Point2F, Point2F, Point2F)
intersectLineSegmentLineSegment2D(Point2F, Point2F, Point2F, Point2F)


if you find a need for intersections between
various other combinations of lines, rays, and line segments,
there's a shared core routine which should make those easy to write.

todo:
for segment vs. segment, there's really no way for script to tell if the intersection exists.
i'm not sure how best to do that, short of an awkward multi-field return string.


for implementing the resource, familiarity with C++ is assumed.


mMathFn.cc

// 2D line intersection routines
// orion elenzil 20080702

void mIntersectLineLineGetFactors(const Point2F& lineAPt1, const Point2F& lineAPt2, const Point2F& lineBPt1, const Point2F& lineBPt2, F32& numeratorA, F32& numeratorB, F32& denominator)
{
   F32 f1      = lineBPt2.y - lineBPt1.y;
   F32 f2      = lineAPt2.x - lineAPt1.x;
   F32 f3      = lineBPt2.x - lineBPt1.x;
   F32 f4      = lineAPt2.y - lineAPt1.y;

   F32 f5      = lineAPt1.y - lineBPt1.y;
   F32 f6      = lineAPt1.x - lineBPt1.x;

   numeratorA  = (f3 * f5)  - (f1 * f6);
   numeratorB  = (f2 * f5)  - (f4 * f6);
   denominator = (f1 * f2)  - (f3 * f4);
}

bool mIntersectLineLine(const Point2F& lineAPt1, const Point2F& lineAPt2, const Point2F& lineBPt1, const Point2F& lineBPt2, Point2F& result)
{
   F32 numeratorA ;
   F32 numeratorB ;
   F32 denominator;

   mIntersectLineLineGetFactors(lineAPt1, lineAPt2, lineBPt1, lineBPt2, numeratorA, numeratorB, denominator);

   if (mFabs(denominator) < 0.0001f)
   {
      // they're parallel

     if (mFabs(numeratorA) < 0.0001f && mFabs(numeratorB) < 0.0001f)
     {
        Con::warnf("mIntersectLineLine() - lines are the same, returning the first point of the first line.");
     }
     else
     {
        Con::warnf("mIntersectLineLine() - lines are parallel, returning the first point of the first line.");
     }
      
      result = lineAPt1;
      return false;
   }

   F32 uA = numeratorA / denominator;

   result = lineAPt1 + (lineAPt2 - lineAPt1) * uA;

   return true;
}

bool mIntersectLineSegmentLineSegment(const Point2F& lineAPt1, const Point2F& lineAPt2, const Point2F& lineBPt1, const Point2F& lineBPt2, Point2F& result)
{
   F32 numeratorA ;
   F32 numeratorB ;
   F32 denominator;

   mIntersectLineLineGetFactors(lineAPt1, lineAPt2, lineBPt1, lineBPt2, numeratorA, numeratorB, denominator);

   if (mFabs(denominator) < 0.0001f)
   {
      // they're parallel

     if (mFabs(numeratorA) < 0.0001f && mFabs(numeratorB) < 0.0001f)
     {
        Con::warnf("mIntersectLineSegmentLineSegment() - line segments are the same, returning the first point of the first line.");
     }
     else
     {
        Con::warnf("mIntersectLineSegmentLineSegment() - line segments are parallel, returning the first point of the first line.");
     }
      
      result = lineAPt1;
      return false;
   }

   F32 uA = numeratorA / denominator;
   F32 uB = numeratorB / denominator;

   if (uA < 0.0f || uA > 1.0f || uB < 0.0f || uB > 1.0f)
   {
     Con::warnf("mIntersectLineSegmentLineSegment() - line segments do not intersect, returning the first point of the first line.");

      result = lineAPt1;
      return false;
   }

   result = lineAPt1 + (lineAPt2 - lineAPt1) * uA;

   return true;
}

here's an example usage from script:

// given a sphere, a camera direction and a camera FOV,
// return the position of the camera so that the sphere snugly fits inside the viewCone.
// note the FOV is the angle subtended by the cone,
// not the angle subtended by the camera view axis and the cone.
// (the latter is half the former)
function fitCameraConeAroundSphere(%spherePosition, %sphereRadius, %camDirection, %camFOVRadians)
{
   // imagine a 2D circle of the given radius centered at the origin,
   // with a camera of the given FOV some distance down the Y axis.
   // we'll solve this situation,
   // then extrapolate to the actual cam direction & sphere position.
   // oxe 20080702
   
   %fovD2                 = %camFOVRadians * 0.5;
   
   // vector of the right-hand edge of the viewCone
   // this is the vector we must make tangent to the sphere
   %vConeEdge             =  mSin(%fovD2) SPC mCos(%fovD2);
   
   // perpendicular to previous.
   %vConeEdgePerp         = -mCos(%fovD2) SPC mSin(%fovD2);
   
   // point where the perpendicular intersects the sphere
   %pTangentPointA        = vectorScale(%vConeEdgePerp, -1 * %sphereRadius);
   
   // another point on the tangent line
   %pTangentPointB        = vectorAdd(%pTangentPointA, %vConeEdge);
   
   // intersection of the tangent line and the Y axis (our eye line in the 2D case)
   %pTangentInteresectY   = [b]intersectLineLine2D("0 0", "0 1", %pTangentPointA, %pTangentPointB)[/b];
   
   // We've now solved the setup for a 2D circle at the origin with the camera below it,
   // let's extrapolate to the 3D case.

   // X is zero, Y is the camera distance
   %sCamDist              = getWord(%pTangentInteresectY, 1);
   
   // move the camera backwards along its eye vector by camDist (we know camDist is negative)
   %pCamPos               = vectorScale(%camDirection, %sCamDist);
   
   // offset by the sphere center
   %pCamPos               = vectorAdd  (%pCamPos, %spherePosition);
      
   return %pCamPos;
}