检测一个点是否在线段上

6
如果我有一条线,其点为x,y,endx和endy,如何检测另一个点是否在该线上?一个简单的方程,或者JavaScript中的示例函数或伪代码将非常有帮助。
编辑:这是我正在开发的游戏,我正在尝试检测激光是否与物体碰撞,这里是样本http://jefnull.com/references/lasers/。最具描述性的文件是http://jefnull.com/references/lasers/lasers.js

你是指那个盒子内另一个点,对吗? - Senad Meškin
8个回答

15

由于我的先前答案说明了如何确定一点是否在该线上,而实际问题似乎是“我如何判断该点是否靠近线段”,因此我添加了一个新答案。

这是一个技巧:首先找到障碍物到线段两个端点的距离。这两个距离不能唯一地确定障碍物的位置,但它们确实可以唯一确定一个三角形,该三角形有三个特定的边长,然后我们可以立即使用几何学进行计算。

Triangle with sides A, B, C

我稍微改变了颜色。无论如何,我在上面的评论中提到,您应该使用点-直线距离公式来查找障碍物与线之间的距离。但这并不会真正起作用。原因是这是点到线的距离。因此,对于下面的两个示例,该公式将计算图片中的粗体距离H

Acute and Obtuse Triangle Diagrams

那不对!!

因此,这里是查找由激光形成的线段与障碍物之间距离的伪代码:

Find the distance from my point to the line segment!

if the angle at (x,y) is obtuse
    return A
else if the angle at (endx,endy) is obtuse
    return B
else
    return H

以下是您可以使用的数学公式来实现上述伪代码:

  • 要查看在 (x,y) 处的角度是否是钝角,请找出是否满足条件 B^2 > A^2 + C^2。如果是,则该角度是钝角。
  • 要查看在 (endx,endy) 处的角度是否是钝角,请找出是否满足条件 A^2 > B^2 + C^2。如果是,则该角度是钝角。
  • 为了计算 H,使用两种不同的方法来找到三角形的面积 - 通常的 base*height/2海龙公式(Heron's Formula)

这意味着你应该:

set s = (A+B+C)/2
The area of the triangle is C*H/2
The area of the triangle is also sqrt(s*(s-A)*(s-B)*(s-C)) 
So H = 2/C * sqrt(s*(s-A)*(s-B)*(s-C)).

最终结果是这样的:

if B^2 > A^2 + C^2
    return A
else if A^2 > B^2 + C^2
    return B
else
    s = (A+B+C)/2
    return 2/C * sqrt(s*(s-A)*(s-B)*(s-C))

我认为这应该足以帮助你实现你真正想要做的事情。祝好运,不要放弃!


9
你想要检查点对之间的斜率是否相同。但是,你应该小心不要除以零,因此通过检查等式的交叉乘积版本来进行检查。
更明确地说,如果你的点是 A = (Ax, Ay), B = (Bx, By), C = (Cx, Cy),那么你想要检查以下内容:
(Cy - Ay)  / (Cx - Ax) = (By - Ay) / (Bx - Ax)

相反,您应该检查

(Cy - Ay)  * (Bx - Ax) = (By - Ay) * (Cx - Ax).

1
我不确定这是否非常重要。Infinity == Infinity,因此这不会导致实际错误(尽管在数学上不正确)。 - pimvdb
@pimvdb 非常出色和令人敬畏。然而,这里还有另一个可能的问题——如果点C实际上在点A上,那么第一种方法会问0/0是否等于某个值。第二种方法是正确的。 - Chris Cunningham
你知道怎么增加一些灵活性吗? - Jef Null
@Jef Null:这可能是查看正确页面的链接:点到直线距离。它提供了从点(x0,y0)到线ax + by + c = 0的距离公式。它被标记为“方程11”。 - Chris Cunningham
@Jef Null 我的新答案可以让你计算从障碍物到激光的距离,因此“宽容度”已经内置。你也可以尝试将我的最后一个 = 替换为“在0.05范围内”...但我不确定那会有什么影响。 - Chris Cunningham

9

首先,Razack提供的答案是最数学上正确的答案,尽管高度理论化。如果您支持这个答案,请考虑同时支持他的答案。

我已经在以下有用的JavaScript函数中实现了他的方法。特别注意calcIsInsideThickLineSegment(...)函数。随意使用。

//Returns {.x, .y}, a projected point perpendicular on the (infinite) line.
function calcNearestPointOnLine(line1, line2, pnt) {
    var L2 = ( ((line2.x - line1.x) * (line2.x - line1.x)) + ((line2.y - line1.y) * (line2.y - line1.y)) );
    if(L2 == 0) return false;
    var r = ( ((pnt.x - line1.x) * (line2.x - line1.x)) + ((pnt.y - line1.y) * (line2.y - line1.y)) ) / L2;

    return {
        x: line1.x + (r * (line2.x - line1.x)), 
        y: line1.y + (r * (line2.y - line1.y))
    };
}

//Returns float, the shortest distance to the (infinite) line.
function calcDistancePointToLine(line1, line2, pnt) {
    var L2 = ( ((line2.x - line1.x) * (line2.x - line1.x)) + ((line2.y - line1.y) * (line2.y - line1.y)) );
    if(L2 == 0) return false;
    var s = (((line1.y - pnt.y) * (line2.x - line1.x)) - ((line1.x - pnt.x) * (line2.y - line1.y))) / L2;
    return Math.abs(s) * Math.sqrt(L2);
}

//Returns bool, whether the projected point is actually inside the (finite) line segment.
function calcIsInsideLineSegment(line1, line2, pnt) {
    var L2 = ( ((line2.x - line1.x) * (line2.x - line1.x)) + ((line2.y - line1.y) * (line2.y - line1.y)) );
    if(L2 == 0) return false;
    var r = ( ((pnt.x - line1.x) * (line2.x - line1.x)) + ((pnt.y - line1.y) * (line2.y - line1.y)) ) / L2;

    return (0 <= r) && (r <= 1);
}

//The most useful function. Returns bool true, if the mouse point is actually inside the (finite) line, given a line thickness from the theoretical line away. It also assumes that the line end points are circular, not square.
function calcIsInsideThickLineSegment(line1, line2, pnt, lineThickness) {
    var L2 = ( ((line2.x - line1.x) * (line2.x - line1.x)) + ((line2.y - line1.y) * (line2.y - line1.y)) );
    if(L2 == 0) return false;
    var r = ( ((pnt.x - line1.x) * (line2.x - line1.x)) + ((pnt.y - line1.y) * (line2.y - line1.y)) ) / L2;

    //Assume line thickness is circular
    if(r < 0) {
        //Outside line1
        return (Math.sqrt(( (line1.x - pnt.x) * (line1.x - pnt.x) ) + ( (line1.y - pnt.y) * (line1.y - pnt.y) )) <= lineThickness);
    } else if((0 <= r) && (r <= 1)) {
        //On the line segment
        var s = (((line1.y - pnt.y) * (line2.x - line1.x)) - ((line1.x - pnt.x) * (line2.y - line1.y))) / L2;
        return (Math.abs(s) * Math.sqrt(L2) <= lineThickness);
    } else {
        //Outside line2
        return (Math.sqrt(( (line2.x - pnt.x) * (line2.x - pnt.x) ) + ( (line2.y - pnt.y) * (line2.y - pnt.y) )) <= lineThickness);
    }
}

要查看一些使用漂亮的SVG图形的代码示例,请参见我用于调试的此链接: https://jsfiddle.net/c06zdxtL/2/


你能更详细地描述一下变量名吗? L2和s代表什么? - Chanwoo Park
@florian,这个能修改一下接受圆而不是点吗?我在移动设备上使用它,手指点击会返回x、y和半径。我尝试将圆的半径添加到线条厚度中,但我不确定这是否是正确的方法。它在iOS上可以工作,但在Android设备上无法工作。 - chitgoks
@ChanwooPark L2代表线段长度的平方(尚未开根号)。s实际上不知道,可以参考Razack的答案。 - Florian Mertens
@chitgoks 我不会在这里回答你的具体代码问题,但是听起来那是解决方案的正确思路。 - Florian Mertens

2
function isOnLine(x, y, endx, endy, px, py) {
    var f = function(somex) { return (endy - y) / (endx - x) * (somex - x) + y; };
    return Math.abs(f(px) - py) < 1e-6 // tolerance, rounding errors
        && px >= x && px <= endx;      // are they also on this segment?
}

x、y、endx和endy是定义直线的点,可以用它们来建立该直线的方程。然后,填入px,检查f(px) = py是否成立(实际上要检查足够小以避免舍入误差)。最后,检查线段是否在区间x ... endx内定义。


它似乎总是返回true。我马上会添加更多细节。 - Jef Null
@Jef Null 如果 endx = xendy = y,那么我猜你会遇到一些有趣而不愉快的行为。你应该将 pimvdb 的出色完整答案与我的吹毛求疵的答案结合起来,以得到正确的答案。 :) - Chris Cunningham
我可以增加容差吗? - Jef Null
isOnLine(0, 1, 1, 0, 0.5, 0.5) 返回 true,但 isOnLine(1, 0, 0, 1, 0.5, 0.5) 返回 false。 - asdjfiasd
isOnLine(0,100,0,200,0,150) 返回 false。应该是 true。 - emorling

2

假设点C的坐标为(Cx,Cy),直线AB的两个端点分别为(Ax,Ay)和(Bx,By)。 设P为点C在直线AB上的垂足。参数r表示P在直线AB上的位置,可以通过向量AC与向量AB的点积除以向量AB长度的平方来计算:

(1)     AC dot AB
r = ---------  
||AB||^2

r has the following meaning:

r=0      P = A
r=1      P = B
r<0      P is on the backward extension of AB
r>1      P is on the forward extension of AB
0<r<1    P is interior to AB

The length of a line segment in d dimensions, AB is computed by:

L = sqrt( (Bx-Ax)^2 + (By-Ay)^2 + ... + (Bd-Ad)^2)

so in 2D:   

L = sqrt( (Bx-Ax)^2 + (By-Ay)^2 )

and the dot product of two vectors in d dimensions, U dot V is computed:

D = (Ux * Vx) + (Uy * Vy) + ... + (Ud * Vd)

so in 2D:   

D = (Ux * Vx) + (Uy * Vy) 

So (1) expands to:

(Cx-Ax)(Bx-Ax) + (Cy-Ay)(By-Ay)
r = -------------------------------
L^2

The point P can then be found:

Px = Ax + r(Bx-Ax)
Py = Ay + r(By-Ay)

And the distance from A to P = r*L.

Use another parameter s to indicate the location along PC, with the 
following meaning:
s<0      C is left of AB
s>0      C is right of AB
s=0      C is on AB

Compute s as follows:

(Ay-Cy)(Bx-Ax)-(Ax-Cx)(By-Ay)
s = -----------------------------
L^2


Then the distance from C to P = |s|*L.

你有個什麼參考資料可以推薦嗎? 我不太理解如何得到 'r' 的整個過程。 (AC dot AB / sqr(length AB) ) - Chanwoo Park
1
请查看以下网址:https://brilliant.org/wiki/dot-product-distance-between-point-and-a-line/ - Razack
很高兴它有帮助! - Razack

1
function is_point_on_segment (startPoint, checkPoint, endPoint) {

    return ((endPoint.y - startPoint.y) * (checkPoint.x - startPoint.x)).toFixed(0) === ((checkPoint.y - startPoint.y) * (endPoint.x - startPoint.x)).toFixed(0) &&
            ((startPoint.x > checkPoint.x && checkPoint.x > endPoint.x) || (startPoint.x < checkPoint.x && checkPoint.x < endPoint.x)) &&
            ((startPoint.y >= checkPoint.y && checkPoint.y >= endPoint.y) || (startPoint.y <= checkPoint.y && checkPoint.y <= endPoint.y));


}

测试:

var startPoint = {x:30,y:30};
var checkPoint = {x:40,y:40};
var endPoint = {x:50,y:50};

console.log(is_point_on_segment(startPoint ,checkPoint ,endPoint ));

0

根据直线方程y = mx + b,其中m是斜率,x是x轴上点的值,b是y截距(即直线与y轴相交的点)。

m(斜率)= endy - y / endx - x; 例如,如果一条线从(0,0)开始并结束于(4,2),则m = 4-0 / 2-0 = 2;

b(y截距)= 0;

现在举个例子,假设你提供了一个点(1,2),要判断它是否在直线上。可以通过x坐标计算出y坐标,即

y = mx+b

y = 2(1)+ 0; //这里x是给定点的x坐标 y = 2; 这恰好与给定点的y坐标相同,因此我们可以得出结论:该点在直线上。如果该点的值为(2,2),根据方程式计算结果为y = 4,而这与给定点的y坐标不相等,因此它不在直线上。

    function isOnLine(initial_x, initial_y, endx, endy, pointx, pointy, tolerate) {
         var slope = (endy-initial_y)/(endx-initial_x);
         var y = slope * pointx + initial_y;

         if((y <= pointy+tolerate && y >= pointy-tolerate) && (pointx >= initial_x && pointx <= endx)) {
             return true;
         }
         return false;
    }

你知道我该如何添加容差吗? - Jef Null
取决于您的容忍度值。将您的容忍度值赋给变量tolerate,然后检查计算出的y值是否在提供的y坐标加减tolerance的范围内。我已经更新了帖子,请查看。 - Ehtesham
1
这里将会出现一个严重的问题,有时您会将“无穷大”乘以其他数值。 - Chris Cunningham
Chris 上面的观点是正确的,因此上面的函数在某些情况下返回错误的值。 - Hakan Bilgin
isOnLine(1, 0, 0, 1, 0.5, 0.5, 0.001) 返回 false。 - asdjfiasd
对于(let x = 0; x < 10; x++) { for (let y = 0; y < 10; y++) { console.log("x : "+x +", y : "+y+ " ::" + isOnLine(1, 6, 8, 2, x, y, 0.5)); } } 不适用于给定参数相同的值: initial_x: 1, initial_y: 6 返回false,点坐标为:pointx: 1, pointy:6 - Adrien Parrochia

-1

这是我的isOnLine实现

function isOnLine(a, b, p, tolerance) {
    var dy = a.y - b.y;
    var dx = a.x - b.x;
    if(dy == 0) { //horizontal line
        if(p.y == a.y) {
            if(a.x > b.x) {
                if(p.x <= a.x && p.x >= b.x)
                    return true;
            }
            else {
                if(p.x >= a.x && p.x <= b.x)
                    return true;
            }
        }
    }
    else if(dx == 0) { //vertical line
        if(p.x == a.x) {
            if(a.y > b.y) {
                if(p.y <= a.y && p.y >= b.y)
                    return true;
            }
            else {
                if(p.y >= a.y && p.y <= b.y)
                    return true;
            }
        }
    }
    else { //slope line
        var s = dy/dx;
        var py = s * p.x;
        if(py <= p.y + tolerance && py >= p.y - tolerance) {
            if(a.x > b.x) {
                if(p.x <= a.x && p.x >= b.x)
                    return true;
            }
            else {
                if(p.x >= a.x && p.x <= b.x)
                    return true;
            }
        }
    }
    return false;
}

for (let x = 0; x < 10; x++) { for (let y = 0; y < 10; y++) { console.log("x : "+x +", y : "+y+ " ::" + isOnLine({'x': 1, 'y':6}, {'x':8, 'y':2}, {'x':x, 'y':y}, 0.5)); } } > 永远不会工作 - Adrien Parrochia

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接