Detecting if a point is of a line segment

Question

If I have a line, with the points x,y,endx and endy how can I detect if another point is on the line? A simple equation, or example functions in JavaScript or pseudocode will be most helpful.

EDIT: This is for a game I'm working on, I'm trying to detect if a laser is colliding with an object, Here is the sample http://jefnull.com/references/lasers/ The file that will be most descriptive is http://jefnull.com/references/lasers/lasers.js

Reba

what do you mean by another point point inside that box, or ? – Ammann

Answer 1

Since my previous answer said how to determine if a point was on the line, and the real question appears to be "how can I tell if the point is near the line segment", I'm adding a new answer.

Here's the trick: first find the distance from your obstacle to each of the two endpoints of your line segment. These two distances don't uniquely determine the location of the obstacle, but they do uniquely determine a triangle with three specific side lengths, and then we can immediately use a bunch of geometry.

I fiddled with the colors a little. Anyway, I mentioned in a comment above that you should use the point-line distance formula to find the distance between the obstacle and the line. But that won't actually work. The reason is that is is the point-line distance. So, for both examples below, the formula will calculate the bold distance H in the picture.

That isn't right!!

So instead, here is the pseudocode for finding the distance from your obstacle to the line segment formed by the laser:

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

Here is the math you can use to implement the above pseudocode:

• To see if the angle at (x,y) is obtuse, find whether B^2 > A^2 + C^2. If so, the angle is obtuse.
• To see if the angle at (endx, endy) is obtuse, find whether A^2 > B^2 + C^2. If so, the angle is obtuse.
• To calculate H, use two different methods for finding the area of the triangle -- the usual base*height/2 and Heron's Formula.

This means you should:

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

The end result is something like:

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

I think that should give you enough to accomplish what you are actually setting out to do. Good luck, and don't give up!

Evvoia

Answer 2

First of all, the answer provided by Razack was the most mathematically sound answer, though highly theoretical. If you are upvoting this answer, please consider upvoting his answer too.

I have implemented his methods in the following useful javascript functions. Have a look in particular at function calcIsInsideThickLineSegment(...). Use as you please.

//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);
    }
}

To see some of this code in action using a nice SVG, see this fiddle which I used to debug: https://jsfiddle.net/c06zdxtL/2/

Interrogator

Can you describe more about the variable names? What does L2 and s mean? – Orrery

@florian can this be modified to accept a circle instead of a point? i am using this in mobile devices where the finger tap will return the x,y, + radius. i tried to add the radius of the circle to the line thickness but im not really sure if this is the right approach. it works in ios but in android devices it does not work. – Qktp

@ChanwooPark L2 stands for length of line segment squared (not yet square rooted). s dont actually know, see Razack's answer. – Interrogator

@Qktp Im not going to answer your specific code problem here, but it sounds like that is the correct thinking for a solution. – Interrogator

Answer 3

You want to check whether the slopes are the same between the pairs of points. But you should be careful not to ever divide by zero, so check by checking the cross-multiplied version of the equations.

More explicitly, if your points are A = (Ax, Ay), B = (Bx, By), C = (Cx, Cy), then you would like to check that

(Cy - Ay)  / (Cx - Ax) = (By - Ay) / (Bx - Ax)

But instead you should check that

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

Evvoia

I'm not sure if this matters very much. Infinity == Infinity, so that would not cause real errors (though it's not mathematically correct). – Ricercare

@Ricercare That is excellent and awesome. Here's another possible problem though -- if point C is actually ON point A, then the first approach asks whether 0/0 equals something. The second approach gets it right. – Evvoia

Do you know how I could add some lenience? – Reba

@Jef Null: This is probably the right page to look at instead: Point-Line Distance It gives a formula for the distance from a point (x0, y0) to the line ax+by+c = 0. It's labelled "equation 11." – Evvoia

@Jef Null My new answer lets you calculate the distance from your obstacle to the laser, so the "lenience" is built in. You could also test out replacing my last = with a "is within 0.05 of"... but I'm not sure what that will do. – Evvoia

Answer 4

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 are the points that define the line, using which you can build the equation of that line. Then, fill in px and see if f(px) = py (in fact checking for small enough due to rounding errors). Lastly, check whether the line segment is defined on the interval x ... endx.

Ricercare

It seems to always return true. I'll add more details momentarily. – Reba

@Jef Null If endx = x and endy = y then I suspect you'll run into some interestingly unpleasant behavior here. You should probably combine the pimvdb's excellent, complete answer with my nitpicky answer to get the right one. :) – Evvoia

Could I perhaps increase the tolerance? – Reba

isOnLine(0, 1, 1, 0, 0.5, 0.5) returns true, but isOnLine(1, 0, 0, 1, 0.5, 0.5) returns false – Boney

isOnLine(0,100,0,200,0,150) returns false. Should be true – Facelifting

Answer 5

Let the point be C (Cx,Cy) and the line be AB (Ax,Ay) to (Bx,By). Let P be the point of perpendicular projection of C on AB. The parameter r, which indicates P's position along AB, is computed by the dot product of AC and AB divided by the square of the length of 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.

Debauchery

Do you have any recommendations for the reference? I couldn't understand the whole process of getting the 'r'. (AC dot AB / sqr(length AB) ) – Orrery

Please have a look at brilliant.org/wiki/… – Debauchery

Happy that it helped! – Debauchery

Answer 6

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


}

Test:

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

Silique

Answer 7

According to the straight line equation y = mx + b where m is slope, x is value of point at x axis and b is y intercept (the point where line intercept y axis).

m(slope) = endy - y/endx - x; e.g. if a line starts at (0, 0) and ends (4,2) then m = 4-0/2-0 = 2;

b (y intercept) = 0 ;

now for example you are provided with a point(1,2) to see if it lies on line. okay calculate your y coordinate with the help of x coordinate. i.e.

y = mx+b

y= 2(1) + 0; // here x is the x coordinate of the given point y = 2; which is exactly the same as the y- coordinate of your given point so we can conclude this lies on the line. If the point had value (2,2) according to equation it will evaluate to y= 4 which is not equal to the y-coordinate of the point you were given so it doesn't lie on the line.

    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;
    }

Phalarope

Do you know how I would add tolerance? – Reba

depends on your value of tolerance. let your value be in a variable tolerate then you will check if your computed value of y is in the range of supplied y-coordinate+-toleance. I have updated the post see. – Phalarope

Again, there is going to be a serious problem here where you sometimes multiply Infinity times other things. – Evvoia

Chris above has a point, thus the function above returns faulty value in some cases – Salted

isOnLine(1, 0, 0, 1, 0.5, 0.5, 0.001) returns false – Boney

for (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)); } } not work with same values has given params as: initial_x: 1, initial_y: 6 return false, with pointx: 1, pointy:6 – Gaines

Answer 8

Here is a JavaScript helper based on pimvdb's answer that also works for horizontal or vertical point-on-line checks.

1. Does the point coincide with either the starting or end point of the line?
2. If the point is within the bounding box of the line (enlarged due to a tolerance value). If not we can quit and return false.
3. If a point is within the bbox but either horizontal or vertical we can return true
4. Otherwise we're using the same calculation for the condtion

let isOnline = Math.abs(((y2 - y1) / (x2 - x1)) * (pt.x - x1) + y1) - pt.y <= tolerance &&
pt.x >= x1 &&
pt.x <= x2; 

By increasing the tolerance value, we can find points that are only nearby the line.

// just a demo rendering
let lines = document.querySelectorAll("line");
let tolerance = 3;
lines.forEach((line) => {
  let x1 = +line.getAttribute("x1");
  let y1 = +line.getAttribute("y1");
  let x2 = +line.getAttribute("x2");
  let y2 = +line.getAttribute("y2");
  let circle = line.nextElementSibling;
  let pt = { x: +circle.getAttribute("cx"), y: +circle.getAttribute("cy") };
  isPointOnline = pointIsOnline(x1, y1, x2, y2, pt, tolerance);
  

  if (isPointOnline) {
    circle.setAttribute("fill", "green");
  }
});


/**
 * based on pimvdb's answer
 * https://mcmap.net/q/1583367/-detecting-if-a-point-is-of-a-line-segment#6865851
 * optional: specify a bounding box for faster recurring intersection checks
 */
function pointIsOnline(x1, y1, x2, y2, pt, tolerance = 0.001) {
  // 1. coincides with start or end point
  if (
    (Math.abs(x1 - pt.x) < tolerance && Math.abs(y1 - pt.y) < tolerance) ||
    (Math.abs(x2 - pt.x) < tolerance && Math.abs(y2 - pt.y) < tolerance)
  ) {
    //console.log('is start or end point')
    return true;
  }
  // 2. test if point is in line boundaries
  let left = Math.min(x1, x2);
  let right = Math.max(x1, x2);
  let top = Math.min(y1, y2);
  let bottom = Math.max(y1, y2);

  let toleranceOffset = tolerance / 2;

  // 2.1 not in bbox - quit!
  if (
    left - toleranceOffset > pt.x ||
    top - toleranceOffset > pt.y ||
    bottom + toleranceOffset < pt.y ||
    right + toleranceOffset < pt.x
  ) {
    return false;
  }
  // 3. in bbox and horizontal or vertical
  let isHorizontal = Math.abs(x1 - x2) < tolerance;
  let isVertical = Math.abs(y1 - y2) < tolerance;
  if (isHorizontal || isVertical) {
    return true;
  }

  let isOnLine =
    Math.abs(((y2 - y1) / (x2 - x1)) * (pt.x - x1) + y1) - pt.y <= tolerance &&
    pt.x >= x1 &&
    pt.x <= x2;
  return isOnLine;
}

svg{
  overflow:visible;
}

.grd{
  display:grid;
  grid-template-columns: 1fr 1fr;
  gap:1em;
}

.col{
  border: 1px solid #ccc;
  padding:1em;
}

<p>Points on line are changed to green fill color</p>
<div class="grd">

  <div class="col">
    <h3>Point on line</h3>
    <svg viewBox="0 0 150 100">
      <line x1="0" y1="0" x2="100" y2="100" stroke="#000" />
      <circle id="c1" cx="50" cy="50" r="2" fill="#000" />
    </svg>
  </div>
  
  <div class="col">
    <h3>Point is starting point</h3>
    <svg viewBox="0 0 150 100">
      <line x1="0" y1="0" x2="100" y2="100" stroke="#000" />
      <circle id="c2" cx="0" cy="0" r="2" fill="#000" />
    </svg>
  </div>
  
  <div class="col">
    <h3>Line is vertical </h3>
    <svg viewBox="0 0 150 100">
      <line x1="50" y1="0" x2="50" y2="100" stroke="#000" />
      <circle id="c3" cx="50" cy="50" r="2" fill="#000" />
    </svg>
  </div>
  
 <div class="col">
    <h3>Line is horizontal </h3>
    <svg viewBox="0 0 150 100">
      <line x1="0" y1="50" x2="100" y2="50" stroke="#000" />
      <circle id="c4" cx="50" cy="50" r="2" fill="#000" />
    </svg>
  </div>
  
   <div class="col">
    <h3>Point not in boundaries of line </h3>
    <svg viewBox="0 0 150 100">
      <line x1="0" y1="0" x2="100" y2="100" stroke="#000" />
      <circle id="c5" cx="120" cy="50" r="2" fill="#000" />
    </svg>
  </div>
  
  
   <div class="col">
    <h3>Point is close line (detected due to higher tolerance)</h3>
    <svg viewBox="0 0 150 100">
      <line x1="0" y1="0" x2="100" y2="100" stroke="#000" />
      <circle class="tolerance3" id="c6" cx="53" cy="50" r="2" fill="#000" />
    </svg>
  </div>
  
  

</div>

Flatling

Answer 9

Here is my implementation of 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;
}

Girder

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)); } } > never working – Gaines