点与线之间的最近曼哈顿距离 [英] nearest Manhattan distance between a point and line

问题描述

我想要在图片中绘制的线段上找到最小的点

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 ?

推荐答案

这是一个搜索问题。您需要从您的观点出发，应用广度优先搜索，直到您点击行像素。任何像素的孩子状态应该是右 - 上 - 左 - 下邻居。曼哈顿距离只是目标的深度。

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.

编辑：记住要添加一些启发式搜索，以便更快地搜索。如果所有行像素都在起点的左边;您不需要访问右。线的角度是另一件需要考虑的事情，以便进一步减少状态。

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.

这篇关于点与线之间的最近曼哈顿距离的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！