nearest Manhattan distance between a point and lin

问题:

I want to find the point on a line segment drawn in an image which is at smallest Manhattan distance from a given point.

Obvious method is to get the pixels on the line segment and for each pixel calculate the distance to get the minimum. But can we do better than this ?

回答1:

This is a search problem. You need to start from your point and apply a breadth first search, grow until you hit a line pixel. The children states for any pixel should be right - up - left - down neighbors. The manhattan distance will be nothing but the depth of the goal.

EDIT: Remember to add some heuristics for faster search, for e.g. if all line pixels are to the left of the starting point; you don't need to visit right. The angle of the line would be another thing to consider, for further reduction of states.