Find point farthest from line

Question

I have an array of points, as well as two more points (A and B). The last two points form a line, and I'm trying to find which of the points in my array are furthest from the line. How would I do this in Java?

I'm wondering if it's something along the lines of finding the distance from A and B, but that doesn't sit well in my head.

Additional info: I think it's a line segment. Given this is QuickHull, I don't know if it makes a difference. I've never been the greatest when it comes to math and formulas, so more explanation is better. Thanks!

Answer 1

Note that each 3 points [a,b,p] for each p in the array form a trianle, whose area is denoted by: (ab) * h /2 [where h is the distance from p to ab]

You can compute the area these trianles create, and select the minimal. Since ab is constant for all - it guarantees that the trianle with the minimal area will also have the minimal h.

You can find it [the area of each triangle] using

T=(1/2)* abs((x_a - x_p) * (y_b-y_a) - (x_a - x_b)* (y_p - y_a))

[where x_a,x_b,x_p and y_a,y_b,y_p are the x,y coordinates of a,b,p respectively].

• Though I find this method very elegant, I believe there are better ways to do it.

Answer 2

    ArrayList<Point> points=new ArrayList();//YOUR POINTS


    Point a=new Point(1,1);
    Point b=new Point(1,1);
    Point ABcenter=new Point((a.x+b.x)/2,(a.y+b.y)/2);//THE CENTER OF THE A AND B POINTS ,USE A OR B IF YOU WANT
    int furthestid=0;
    float furthestdis=0;
    for(int c=0;c<points.size();c++)
    {
        if(calculate_distance(ABcenter.x,ABcenter.y,points.get(c).x,points.get(c).y)>furthestdis)
        {
            furthestid=c;
        }
    }

//closestid  now contains the id of the furthest point ,use it like this points.get(c).x ...




public static double calculate_distance (float x1,float y1,float x2 ,float y2){
        return Math.sqrt((((x1-x2) * (x1-x2)) + ((y1- y2) * (y1- y2))));
}

Answer 3

I'm assuming you talking about line segment not line. First you should find your points distance from your line segment, and you can do it, as the way suggested in this similar question, after that find minimum/maximum distance over all inputs.

Edit: Also from this top coder article you can find distance simply:

//Compute the dot product AB ⋅ BC
int dot(int[] A, int[] B, int[] C){
    AB = new int[2];
    BC = new int[2];
    AB[0] = B[0]-A[0];
    AB[1] = B[1]-A[1];
    BC[0] = C[0]-B[0];
    BC[1] = C[1]-B[1];
    int dot = AB[0] * BC[0] + AB[1] * BC[1];
    return dot;
}
//Compute the cross product AB x AC
int cross(int[] A, int[] B, int[] C){
    AB = new int[2];
    AC = new int[2];
    AB[0] = B[0]-A[0];
    AB[1] = B[1]-A[1];
    AC[0] = C[0]-A[0];
    AC[1] = C[1]-A[1];
    int cross = AB[0] * AC[1] - AB[1] * AC[0];
    return cross;
}
//Compute the distance from A to B
double distance(int[] A, int[] B){
    int d1 = A[0] - B[0];
    int d2 = A[1] - B[1];
    return sqrt(d1*d1+d2*d2);
}
//Compute the distance from AB to C
//if isSegment is true, AB is a segment, not a line.
double linePointDist(int[] A, int[] B, int[] C, boolean isSegment){
    double dist = cross(A,B,C) / distance(A,B);
    if(isSegment){
        int dot1 = dot(A,B,C);
        if(dot1 > 0)return distance(B,C);
        int dot2 = dot(B,A,C);
        if(dot2 > 0)return distance(A,C);
    }
    return abs(dist);
}

I think code has self explanation, if you are familiar with basic geometry, but if you aren't familiar, you should to read the article, if there is any problem for you we can help you.

Answer 4

I'm assuming you mean the Euclidean distance. If you're working in the plane, then the answer is simple.

First, compute the equation of the line in the form

ax + by + c = 0

In slope-intercept form, this is the same as

y = (-a/b)x + (-c/b)

Now compute the distance from any point (p,q) to the line by

|a*p + b*q + c| / (a^2 + b^2)^(1/2)

For more than 2 dimensions, it's probably easiest to think in terms of parametrized vectors. This means think of points on the line as

p(t) = (A1 + (B1-A1)*t, A2 + (B2-A2)*t, ..., An + (Bn-An)*t)

where the two points are A = (A1,...,An) and B = (B1,...,Bn). Let X = (X1,...,Xn) be any other point. Then the distance between X and p(t), the point on the line corresponding to t, is the square root of

[(A1-X1) + (B1-A1)t]^2 + ... + [(An-Xn) + (Bn-An)t]^2

The distance to the line is the distance to p(t) where t is the unique value minimizing this distance. To compute that, just take the derivative with respect to t and set it to 0. It's a very straightforward problem from here, so I'll leave that bit to you.

If you want a further hint, then check out this link for the 3-dimensional case which reduces nicely.

Answer 5

If the problem is as you have stated it, you can't do much better then computing the distance for each point and choosing the smallest of these.

However you can simplify the calculation of the distance a bit by using a generalized line equation for the line passing through A and B. This would be an equation of the form ax + by + c = 0

You can compute such equation for a line passing through two arbitrary points quite easily:

x * (A.y - B.y) + y * (B.x - A.x) + A.x * B.y - A.y * B.x,

i.e. a = A.y - B.y, b = B.x - A.x and c = A.x * B.y - A.y * B.x

Now that you have computed such equation for the line, you can compute the distance from an arbitrary point P in the plane to the line a * x + b * y + c by substituting x and y with the coordinates of P:

abs(a * P.x + b * P.y + c) / sqrt(a * a + b * b). But as the denominator will be the same for all points, you may igonore it and simply choose the point for which abs(a * P.x + b * P.y + c) is smallest

Here is a link that explains how to compute 2-d distance to a line once you have it's generalized equation.