vectorparallel-processingdot-productcross-product

How do I know if two line segments are near collinear


I am having some trouble determining if two line segments are collinear because of floating point precision. How can I determine if the line segments are collinear with some tolerance?


Solution

  • EDITED:

    Line segments are colinear if they contain two of the same points. They are near-colinear if they share one point and are near-parallel.

    Vectors are effectively parallel if the angle between them is less than a threshold you state. Maybe less than .000027 degrees, which is the decimal equivalent of one tenth of a degree-second (which is in latitudinal distance, and equivalently of longitudinal distance at the equator, a difference of approximately ten feet; that's about the accuracy of civilian GPS).

    You didn't tell us what language or library you're using; in .NET's System.Windows.Media.3D library there is a Vector3D struct which has an AngleBetween() method, making this check a one-liner.

    The "basic" math (it's actually vector trig, not a "basic" concept by most definitions) is that θ=cos-1( A*B / |A||B| ); that is, the arc-cosine of the quantity of the scalar product of the two vectors divided by the product of their magnitudes.

    The dot product of vector A and vector B, both containing components X, Y, and Z, is XAXB + YAYB + ZAZB. The magnitude of a vector A is sqrt(XA2 + YA2 + ZA2).

    So, in pseudo-C-ish:

    //Vector is a simple immutable class or struct containing integer X, Y and Z components
    public bool CloseEnough(Vector a, Vector b, decimal threshold = 0.000027m)
    {
       int dotProduct = a.X*b.X + a.Y*b.Y + a.Z*b.Z;
       decimal magA = sqrt(a.X*a.X + a.Y*a.Y + a.Z*a.Z); //sub your own sqrt
       decimal magB = sqrt(b.X*b.X + b.Y*b.Y + b.Z*b.Z); //sub your own sqrt
    
       decimal angle = acos(dotProduct/(magA*magB)); //sub your own arc-cosine
    
       if(angle <= threshold
    }