到形状边界的最近距离

Question

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

谢谢。

Answer 1

因此，您的形状被定义为位图，您可以访问像素。

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

另一种方法是围绕该点绘制半径不断增大的布雷森纳姆圆。该方法与平方法类似，但您可以在命中后立即停止，因为所有点到您的点的距离都应该相同。缺点是这种方法有些不准确，因为圆只是一个近似值。您还会错过沿二角线的一些像素，因为布雷森纳姆圆有伪影。

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

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

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