0

I have been trying to work out how to check if a point is on the same line and inbetween two other points. It seems to work if the line is diagonal but if its straight vertically or horizontally it fails.

This is my method:

public bool isBetween(Vector3 C, Vector3 A, Vector3 B)
{
    Vector3 sum = Vector3.Cross(A,B) + Vector3.Cross(A,C) + Vector3.Cross(B,C);

    if (sum.x == 0 && sum.z == 0 && sum.y == 0)
    {
        Vector3 min = Vector3.Min(A, B);
        Vector3 max = Vector3.Max(A, B);

        // only checking 2 dimensions
        if (C.x > min.x && C.x < max.x && C.z > min.z && C.z < max.z)
        {
            return true;
        }
    }
    return false;
}

It works for certain cases but not 100% for all cases. Not sure how to fix it to get it working.

Sir
  • 8,135
  • 17
  • 83
  • 146

1 Answers1

8

Assuming that point1 and point2 are different, first you check whether the point lies on the line. For that you simply need a "cross-product" of vectors point1 -> currPoint and point1 -> point2.

dxc = currPoint.x - point1.x;
dyc = currPoint.y - point1.y;

dxl = point2.x - point1.x;
dyl = point2.y - point1.y;

cross = dxc * dyl - dyc * dxl;

Your point lies on the line if and only if cross is equal to zero.

if (cross != 0)
 return false;

Now, as you know that the point does lie on the line, it is time to check whether it lies between the original points. This can be easily done by comparing the x coordinates, if the line is "more horizontal than vertical", or y coordinates otherwise

if (abs(dxl) >= abs(dyl))
 return dxl > 0 ? 
   point1.x <= currPoint.x && currPoint.x <= point2.x :
   point2.x <= currPoint.x && currPoint.x <= point1.x;
else
 return dyl > 0 ? 
   point1.y <= currPoint.y && currPoint.y <= point2.y :
   point2.y <= currPoint.y && currPoint.y <= point1.y;

Note that the above algorithm if entirely integral if the input data is integral, i.e. it requires no floating-point calculations for integer input. Beware of potential overflow when calculating cross though.

P.S. This algorithm is absolutely precise, meaning that it will reject points that lie very close to the line but not precisely on the line. Sometimes this is not what's needed. But that's a different story.

AKN
  • 416
  • 2
  • 5
  • I'll give your example a try. I originally tried something similar here: http://pastebin.com/xhCPaeSG but it failed to work. – Sir Mar 17 '17 at 22:56
  • Side note: you may want to move your answer to http://stackoverflow.com/questions/7050186/find-if-point-lays-on-line-segment. – Alexei Levenkov Mar 17 '17 at 23:00
  • Half of those answers are either not C# or calculating distances - i even used that answer page to formulate what i wrote in my pastebin but it didn't even work. – Sir Mar 17 '17 at 23:05