determinate: is point on line segment

Question

I am trying to code a java methods which returns a Boolean true if a point(x,y) is on a line segment and false if not.

I tried this:

public static boolean OnDistance(MyLocation a, MyLocation b, MyLocation queryPoint) {

    double value = java.lang.Math.signum((a.mLongitude - b.mLongitude) * (queryPoint.mLatitude - a.mLatitude)
            - (b.mLatitude - a.mLatitude) * (queryPoint.mLongitude - a.mLongitude));
    double compare = 1;
    if (value == compare) {
        return true;
    }

    return false;
}

but it doesn't work.

i found a solution with 12 if-conditions - but i think thats not the smart way ... — Dennis, Sep 24 '15 at 13:19
Since the fields are called `mLongitude` and `mLatitude`, do you want to do this on a sphere? — Henry, Sep 25 '15 at 06:25

Spektre · Accepted Answer · 2019-07-19T11:08:27.230

I am not JAVA coder so I stick to math behind ... For starters let assume you are on plane (not sphere surface)

I would use Vector math so let:

a,b - be the line endpoints
q - queried point
c=q-a - queried line direction vector
d=b-a - line direction vector
use dot product for parameter extraction
```
t=dot(c,d)/(|c|*|d|)
```
t is line parameter <0,1> if out of range q is not inside line
|c|=sqrt(c.x*c.x+c.y*c.y) size of vector
dot(c,d)=c.x*d.x+c.y*d.y scalar vector multiply
now compute corresponding point on line
```
e=a+(t*d)
```
e is the closest point to q on the line ab
compute perpendicular distance of q and ab
```
l=|q-e|;
```
if (l>treshold) then q is not on line ab else it is on the line ab. The threshold is the max distance from line you are still accepting as inside line. No need to have l sqrt-ed the threshold constant can be powered by 2 instead for speed.
if you add all this to single equation

then some things will simplify itself (hope did not make some silly math mistake)
```
l=|(q-a)-(b-a)*(dot(q-a,b-a)/|b-a|^2)|;
return (l<=treshold);
```
or
```
l=|c-(d*dot(c,d)/|d|^2)|;
return (l<=treshold);
```
As you can see we do not even need sqrt for this :)

[Notes]

If you need spherical or ellipsoidal surface instead then you need to specify it closer which it is what are the semi axises. The line become arc/curve and need some corrections which depends on the shape of surface see

Projecting a point onto a path

but can be done also by approximation and may be also by binary search of point e see:

mine approx class in C++

The vector math used can be found here at the end:

Understanding 4x4 homogenous transform matrices

Here 3D C++ implementation (with different names):

double distance_point_axis(double *p,double *p0,double *dp)
    {
    int i;
    double l,d,q[3];
    for (i=0;i<3;i++) q[i]=p[i]-p0[i];                  // q = p-p0
    for (l=0.0,i=0;i<3;i++) l+=dp[i]*dp[i];             // l = |dp|^2
    for (d=0.0,i=0;i<3;i++) d+=q[i]*dp[i];              // d = dot(q,dp)
    if (l<1e-10) d=0.0; else d/=l;                      // d = dot(q,dp)/|dp|^2
    for (i=0;i<3;i++) q[i]-=dp[i]*d;                    // q=q-dp*dot(q,dp)/|dp|^2
    for (l=0.0,i=0;i<3;i++) l+=q[i]*q[i]; l=sqrt(l);    // l = |q|
    return l;
    }

Where p0[3] is any point on axis and dp[3] is direction vector of axis. The p[3] is the queried point you want the distance to axis for.

determinate: is point on line segment

1 Answers1

Linked