Обнаружение, если точка принадлежит отрезку - PullRequest
Новая
       46

Обнаружение, если точка принадлежит отрезку

3 голосов
/ 29 июля 2011

Если у меня есть линия с точками x, y, endx и endy, как я могу определить, находится ли другая точка на линии? Простое уравнение или примеры функций в JavaScript или псевдокоде будут наиболее полезны.

EDIT: Это для игры, над которой я работаю. Я пытаюсь определить, сталкивается ли лазер с объектом. Вот пример http://jefnull.com/references/lasers/. Наиболее описательный файл - http://jefnull.com/references/lasers/lasers.js

.

Ответы [ 8 ]

12 голосов
/ 29 июля 2011

Поскольку в моем предыдущем ответе говорилось, как определить, была ли точка на линии, и реальный вопрос выглядит так: "Как я могу определить, находится ли точка рядом с линией сегмент", я добавляю новый ответ.

Вот хитрость: сначала найдите расстояние от вашего препятствия до каждой из двух конечных точек вашего отрезка.Эти два расстояния не однозначно определяют местоположение препятствия, но они однозначно определяют треугольник с тремя конкретными длинами сторон, и тогда мы можем сразу использовать связку геометрии.

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 и Формула Герона .

Это означает, что вы должны: 

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))

Я думаю, что этого должно быть достаточно для достижения того, что вына самом деле намереваемся сделать.Удачи и не сдавайся!

7 голосов
/ 29 июля 2011

Вы хотите проверить, одинаковы ли наклоны между парами точек. Но вы должны быть осторожны, чтобы никогда не делить на ноль, поэтому проверяйте, проверяя умноженную версию уравнений.

Более конкретно, если ваши очки 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).
4 голосов
/ 15 августа 2016

Прежде всего, ответ, предоставленный Разаком , был наиболее математически обоснованным, хотя и очень теоретическим.Если вы голосуете против этого ответа, пожалуйста, рассмотрите возможность его голосования тоже.

Я реализовал его методы в следующих полезных функциях 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/

2 голосов
/ 29 июля 2011 
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 and endy - это точки, которые определяют линию, используя которую вы можете построить уравнение этой линии. Затем заполните px и посмотрите, если f(px) = py (на самом деле проверка достаточно мала из-за ошибок округления). Наконец, проверьте, определен ли сегмент линии в интервале x ... endx.

1 голос
/ 14 декабря 2013 
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 ));
1 голос
/ 29 июля 2011

Пусть точка будет 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.
1 голос
/ 29 июля 2011

В соответствии с уравнением прямой линии 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), чтобы увидеть, находится ли он на линии.хорошо рассчитать координату Y с помощью координаты х.т.е.

y = mx + b

y = 2 (1) + 0;// здесь x - координата x данной точки y = 2;которая точно такая же, как у-координата вашей заданной точки, поэтому мы можем заключить, что она лежит на прямой.Если точка имела значение (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;
    }
0 голосов
/ 29 апреля 2013

Вот моя реализация 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 p = dy/dx;
        var py = p * 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;
}
...