algorithm - 到形状边界的最近距离

Question

我有一个形状(下方黑色)和形状内的一个点(下方红色)。找到我的红点和形状边界(图形上的绿点)之间最近距离的算法是什么？
形状边框不是一系列线条，而是随机绘制的形状。

谢谢。

Answer 1

所以你的形状被定义为位图，你可以访问像素。

您可以扫描点周围不断增长的正方形以寻找边界像素。首先，检查像素本身。然后检查覆盖该点八个相邻像素的宽度为 2 的正方形。接下来，接下来的 16 个像素的宽度为 4，依此类推。当您找到边界像素时，记录它的距离并检查找到的最小距离。当正方形的一半宽度大于当前最小距离时，可以停止搜索。

另一种方法是绘制 Bresenham circles围绕该点增加半径。该方法类似于平方方法，但是当您命中时可以立即停止，因为所有点都应该与您的点具有相同的距离。缺点是这种方法有些不准确，因为圆只是一个近似值。您还会错过一些沿斜线的像素，因为 Bresenham 圆有人工制品。

(这两种方法仍然相当暴力，在全黑位图的最坏情况下将访问每个节点。)

您需要一个边界像素的标准。你的形状是抗锯齿的，所以边界上的像素通过使它们成为灰色阴影来平滑。如果您的标准是不是黑色的像素，您将选择形状内部的一点。如果你选择纯白色，你会落在外面一点。也许最好选择灰度值大于0.5的像素作为边框。

如果对于相同的形状，你必须找到与许多点最近的边界点，你可以预处理数据并使用[最近邻搜索]的其他方法。