Java - Polar Coordinates. Given a line segment AB and a point P, find the closest point on the polar line AB to point P

Question

I'm given a line segment with two endpoints: (x1,y1) (x2,y2) and a random point: (x3,y3).

If I convert the line segment to polar coordinates, I need to be able to figure out, programmatically, a point on the line segment that is the closest to point (x3,y3).

EDIT: I made a mistake in my question. The problem isn't trying to find the closest point between the three. The problem is... given a line AB with a start and an end... find ANY point on the line that is closest to point (x3,y3).

Answer 1

This question involves elementary school level algebra: There are only 3 options for the closest point:

• one of the points (x1,y1) (x2,y2)
• another point between them on the line segment

It's easy to find the distance between (x3,y3) to the two points using Pythagoras:

d1 = d(<x1,y1>,<x3,y3>) = sqrt( (x1-x3)^2 + (y1-y3)^2)

and

d2 = d(<x2,y2>,<x3,y3>) = sqrt( (x2-x3)^2 + (y2-y3)^2)

and now for the "more complicated" part: if there's another point on the segment which is closer to (x3,y3) - if we connect these points - we'll have a new segment that will be diagonal to the original segment - we have to use that together with a first degree equation (for a line) to find that third point and see if it's on the segment or outside (if it's outside of the segment then we'll take the minimum distance between (x3,y3) to the other two points.

The line equation (excuse my English - I learnt it in my native language so bear with me) is:

(I) y = mx + d 

where m is easy to calculate:

m = (y1-y2)/(x1-x2)

and now that we know the value of m in order to find d we'll use the values of one of the first two points, for example:

y1 = mx1 +d  =>   d = y1 - mx1

the diagonal line will have m' which is -1/m and if we'll use the values of (x3,y3) we'll find d'. So now we know both the values of (I) as well as the equation for the diagonal line:

(II) y=m'x + d'

and if we'll use these two equations we can find the point on the line through which the original segment goes through which is the closest to (x3,y3) - if this point lies on the segment - we're done, otherwise, like earlier mentioned - we'll take the minimum between d1 and d2

Answer 2

I guess this is too late, just in case someone needs it, I just convert back to cartesian coordinates so the formula is easier to look at:

 public static double distance(double r1,double t1,double r2,double t2,double r3,double t3)
 {
   double x1 = (r1*Math.cos(t1));
   double x2 = (r1*Math.cos(t2));
   double x3 = (r1*Math.cos(t3));
   double y1 = (r1*Math.sin(t1));
   double y2 = (r1*Math.sin(t2));
   double y3 = (r1*Math.sin(t3));

   return Math.abs((x2-x1)*(y1-y3)-(x1-x3)*(y2-y1))/Math.sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
 }

Answer 3

public static Location closest(double x1, double y1, double x2, double y2, double x3, double y3){
    Location a = new Location("provider");
    Location b = new Location("provider");
    Location c = new Location("provider");

    //I can't remember which one goes where, you may need to swap all the x/ys around
    //Do conversion or something here. 

    a.setLongitude(x1);
    a.setLatitude(y1);

    b.setLongitude(x2);
    b.setLatitude(y2);

    c.setLongitude(x3);
    c.setLongitude(y3);

    return closest(a, b, c);
}

public static Location closest(Location a, Location b, Location c){
    return a.distanceTo(c) < b.distanceTo(c) ? a : b;
}