Original Post
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
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\]
