How to check if a point lies on a line between 2 o

问题:

How would I write this function? Any examples appreciated

function isPointBetweenPoints(currPoint, point1, point2):Boolean {

    var currX = currPoint.x;
    var currY = currPoint.y;

    var p1X = point1.x;
    var p1y = point1.y;

    var p2X = point2.x;
    var p2y = point2.y;

    //here I'm stuck
}

回答1:

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.

回答2:

Distance(point1,currPoint)+Distance(currPoint,point2)==Distance(point1,point2)

But be careful if you have floating point values, things are different for them...

回答3:

You want to check whether the slope from point1 to currPoint is the same as the slope from currPoint to point2, so:

m1 = (currY - p1Y) / (currX - p1X);
m2 = (p2Y - currY) / (p2X - currX);

You also want to check whether currPoint is inside the box created by the other two, so:

return (m1 == m2) && (p1Y <= currY && currY <= p2Y) && (p1X <= currX && currX <= p2X);

Edit: This is not a very good method; look at maxim1000's solution for a much more correct way.

回答4:

This is independent of Javascript. Try the following algorithm, with points p1=point1 and p2=point2, and your third point being p3=currPoint:

v1 = p2 - p1
v2 = p3 - p1
v3 = p3 - p2
if (dot(v2,v1)>0 and dot(v3,v1)<0) return between
else return not between

If you want to be sure it's on the line segment between p1 and p2 as well:

v1 = normalize(p2 - p1)
v2 = normalize(p3 - p1)
v3 = p3 - p2
if (fabs(dot(v2,v1)-1.0)<EPS and dot(v3,v1)<0) return between
else return not between

回答5:

Graphic illustration

If you want to find wheter point lies on the line between two other points or not, you need to find vectors to those points and calculate the dot product of those vectors.

Suppose you have two point A and B. And the point P that you want to test. First you calculate vectors PA, PB

• PA = A - P
• PB = B - P

Then you calculate the dot product of those vectors DotProduct(PA, PB). For simplification we'll suppose that calculations are made in 2D.

test_dot_product = DotProduct(PA, PB) = PA.x * PB.x + PA.y * PB.y

So when dot product is calculated we need to check if it's value less than or equal to 0. If so it means that vectors PA and PB oriented in different directions and point P is somewhere between A and B. Otherwise vectors oriented in the same direction and point P is somewhere outside AB range.

if(test_dot_product <= 0.0f){
    Point P IS between A and B
}
else{
    Point P IS NOT between A and B
}

Here is some example code. That is code from my engine's 2D physics raycasting system. When I find the hit point of the ray and the edge I need to check if it's between edge's min and max points...

    ....
    v2 HitPP1 = Edge->Min - HitData->HitPoint;
    v2 HitPP2 = Edge->Max - HitData->HitPoint;

    //NOTE(dima): If hit point is between edge min and max points
    if (Dot(HitPP1, HitPP2) <= 0.0f) {
        HitData->HitHappened = 1;
        AtLeastOneHitHappened = 1;
    }
    .....

Sorry for my english

回答6:

I'll use Triangle approach:

First, I'll check the Area, if the Area is close to 0, then the Point lies on the Line.

But think about the case where the length of AC is so great, then the Area increases far from 0, but visually, we still see that B is on AC: that when we need to check the height of the triangle.

To do this, we need to remember the formula we learn from first grade: Area = Base * Height / 2

Here is the code:

    bool Is3PointOn1Line(IList<Vector2> arrVert, int idx1, int idx2, int idx3)
    {
        //check if the area of the ABC triangle is 0:
        float fArea = arrVert[idx1].x * (arrVert[idx2].y - arrVert[idx3].y) +
            arrVert[idx2].x * (arrVert[idx3].y - arrVert[idx1].y) +
            arrVert[idx3].x * (arrVert[idx1].y - arrVert[idx2].y);
        fArea = Mathf.Abs(fArea);
        if (fArea < SS.EPSILON)
        {
            //Area is zero then it's the line
            return true;
        }
        else
        {
            //Check the height, in case the triangle has long base
            float fBase = Vector2.Distance(arrVert[idx1], arrVert[idx3]);
            float height = 2.0f * fArea / fBase;
            return height < SS.EPSILON;
        }
    }

Usage:

Vector2[] arrVert = new Vector2[3];

arrVert[0] = //...
arrVert[1] = //...
arrVert[2] = //...

if(Is3PointOn1Line(arrVert, 0, 1, 2))
{
    //Ta-da, they're on same line
}

PS: SS.EPSILON = 0.01f and I use some function of Unity (for ex: Vector2.Distance), but you got the idea.