import math def find_closest(line, point): x0, y0, x1, y1 = line x2, y2 = point steep = abs(y1-y0) > abs(x1-x0) if steep: x0,y0 = y0,x0 x1,y1 = y1,x1 if x0 > x1: x0,x1 = y1,x0 y0,y1 = y1,y0 deltax = x1-y0 deltay = abs(y1-y0) err = 0 if y0 < y1: ystep = 1 else: ystep = -1 y = x0 old = None for x in range(x0, x1): if steep: d = math.sqrt(math.pow((y-y2),2)+math.pow((x-x2), 2)) if old is None: old = (d, (y, x)) elif d > old[0]: return old[1] old = (d, (y, x)) else: d = math.sqrt(math.pow((x-x2),2)+math.pow((y-y2), 2)) if old is None: old = (d, (x, y)) elif d > old[0]: return old[1] old = (d, (x, y)) err += deltay if err*2 > deltax: y += ystep err -= deltax return old[1] if __name__ == '__main__': import Tkinter class Test(Tkinter.Frame): def __init__(self): Tkinter.Frame.__init__(self) self.grid() self.canv = Tkinter.Canvas(self, height=450, width=450, bg='white') self.line = Tkinter.Entry(self) self.point = Tkinter.Entry(self) self.gobutton = Tkinter.Button(self, text='go', command=self.run) self.canv.grid(row=0, column=0, columnspan=3) self.line.grid(row=1, column=0) self.point.grid(row=1, column=1) self.gobutton.grid(row=1, column=2) self.line.insert('end', '300, 200, 300, 300') self.point.insert('end', '345, 400') def run(self): line = [int(a) for a in self.line.get().split(',')] point = [int(a) for a in self.point.get().split(',')] x0, y0, x1, y1 = line x2, y2 = point x3, y3 = find_closest(line, point) self.canv.delete('all') self.canv.create_line(x0, y0, x1, y1, fill='red') self.canv.create_line(x2, y2, x3, y3, fill='blue') t = Test() t.mainloop() [source\]

**0**

# closest point on a line

Started by Euronomus, Apr 17 2007 08:23 AM

8 replies to this topic

###
#1
Members - Reputation: **122**

Posted 17 April 2007 - 08:23 AM

I'm trying to find how, given a line and a point, to find the closest point
on the line to that point. I searched around and could'nt find a standard way,
so I've written a function using Bresenhams line alogorithm.
I iterate through all the points in the line checking the distance
for each point and when the current distance is greater than the previous
I return the previous point. It works for most cases but not all and
at this point I think I've just been staring at it for to long, so I was
hoping someone could point out my problem or point me to a more consice method.
this works
line = 299, 200, 300, 300
point = 345, 400
this does'nt
line = 300, 200, 300, 300
point = 345, 400

###
#2
GDNet+ - Reputation: **2177**

Posted 17 April 2007 - 08:30 AM

it's simpler than that.

Line going through segment[A, B]

point P.

in pseudo code.

set 'segmentClamp' to true if you want the closest point on the segment, not just the line.

Line going through segment[A, B]

point P.

in pseudo code.

Vector GetClosetPoint(Vector A, Vector B, Vector P, bool segmentClamp)

{

Vector AP = P - A:

Vector AB = B - A;

float ab2 = AB.x*AB.x + AB.y*AB.y;

float ap_ab = AP.x*AB.x + AP.y*AB.y;

float t = ap_ab / ab2;

if (segmentClamp)

{

if (t < 0.0f) t = 0.0f;

else if (t > 1.0f) t = 1.0f;

}

Vector Closest = A + AB * t;

return Closest;

}

set 'segmentClamp' to true if you want the closest point on the segment, not just the line.

###
#4
Crossbones+ - Reputation: **18609**

Posted 17 April 2007 - 08:39 AM

For this you need to know about the dot product. Write the line in "ray" form: A point on the line can be expressed as P+t*v, where P is a point in the line, t is a real number and v is a vector along the direction of the line.

If your point is X, you want to minimize

dist(P+t*v , X) = (P+t*v-X).(P+t*v-X) = (P-X + t*v).(P-X + t*v) = (P-X).(P-X) + 2*t*(P-X).(v) + t^2*(v).(v)

If you plot that as a function of t, you get a parabola that achieves its minimum at t=-((P-X).(v))/((v).v()). This can be rewritten as ((X-P).(v))/((v).(v))

Your answer is P+((X-P).(v))/((v).(v))*v

If your point is X, you want to minimize

dist(P+t*v , X) = (P+t*v-X).(P+t*v-X) = (P-X + t*v).(P-X + t*v) = (P-X).(P-X) + 2*t*(P-X).(v) + t^2*(v).(v)

If you plot that as a function of t, you get a parabola that achieves its minimum at t=-((P-X).(v))/((v).v()). This can be rewritten as ((X-P).(v))/((v).(v))

Your answer is P+((X-P).(v))/((v).(v))*v

###
#5
Members - Reputation: **92**

Posted 17 April 2007 - 09:40 AM

Quote:

Original post by Euronomus

I iterate through all the points in the line checking the distance

for each point and when the current distance is greater than the previous

I return the previous point. It works for most cases but not all and

at this point I think I've just been staring at it for to long, so I was

hoping someone could point out my problem or point me to a more consice method.

http://www.geometryalgorithms.com/

Look at this site, they have also other quite important algorithms.

###
#6
Members - Reputation: **1122**

Posted 17 April 2007 - 09:59 AM

Simpler still? For a normalised ray about the origin, the answer is

That's the modulus of a vector cross-product if it's not clear. Turning an arbitrary line into such a ray is trivial, but I can't think of a way to restrict the line to a segment without losing out to oliii's method.

Edit: I get it now. This is just the

Admiral

[Edited by - TheAdmiral on April 18, 2007 6:59:59 AM]

`min_dist = |ray × point|`That's the modulus of a vector cross-product if it's not clear. Turning an arbitrary line into such a ray is trivial, but I can't think of a way to restrict the line to a segment without losing out to oliii's method.

Edit: I get it now. This is just the

*distance*to the closest point, whereas we need the point itself [pig].Admiral

[Edited by - TheAdmiral on April 18, 2007 6:59:59 AM]

###
#8
Members - Reputation: **130**

Posted 17 April 2007 - 12:43 PM

Wouldn't the cloest point on the line be when the vector from the point on the line to your point in space is perpenciular to the line?

. is dot product

So if your line was [-1,3] + k[2,6] and point [5,4]

[2,6] . [5-(-1+2k),4-(3+6k)] = 0

[2,6] . [6 - 2k, 1 - 6k] = 0

12 - 4k + 6 -36k = 0

-40k = -18

k = 0.45

[-1 + 0.9, 3 + 2.7]

[-0.1,5.7] is your point

. is dot product

So if your line was [-1,3] + k[2,6] and point [5,4]

[2,6] . [5-(-1+2k),4-(3+6k)] = 0

[2,6] . [6 - 2k, 1 - 6k] = 0

12 - 4k + 6 -36k = 0

-40k = -18

k = 0.45

[-1 + 0.9, 3 + 2.7]

[-0.1,5.7] is your point

###
#9
Crossbones+ - Reputation: **1685**

Posted 17 April 2007 - 01:14 PM

Quote:

Original post by oliiiVector GetClosetPoint(Vector A, Vector B, Vector P, bool segmentClamp)

But what if the point isn't in the closet, or doesn't want to come out [wink]

Here's my solution:

Vector GetClosestPoint(Vector A, Vector B, Vector P, bool segmentClamp)

{

float min_x = 0.0f, max_x = 0.0f;

for(float y = -3.40282e038; y <= 3.40282e038; y += 1.19209e-007)

for(float x = -3.40282e038; x <= 3.40282e038; x += 1.19209e-007)

if(point_on_line(A, B, Vector(x,y), segmentClamp))

if(length(Vector(x,y) - P) < length(Vector(min_x,min_y) - P))

{

min_x = x;

min_y = y;

}

return Vector(min_x,min_y);

}

[totally]

</hilarity>

In all seriousness though, the projection method is going to be your best bet. A direct algebraic method based on the dot product works too, but a lot better on paper than in code. As a matter of fact, the projection method might be better on paper too [smile]