我有一个形状（下图中的黑色部分）和一个在该形状内的点（下图中的红色部分）。如何计算出红点与形状边界之间的最短距离（即图中的绿点）？
形状边界不是一系列直线，而是一个随机绘制的形状。
形状边界不是一系列直线，而是一个随机绘制的形状。
最靠近形状边界的距离
4
- Laurent Crivello
6
1边界如何指定？您能枚举边界上的所有点吗？ - timrau
你说的"边界不是一系列线条，而是随机绘制的形状"是什么意思？这就像你说你有一辆不是沃尔沃的橙色汽车。你说的"算法是什么"是什么意思？最简单的方法很直接——遍历所有点并找到最近的点。可以想象有数千种优化、巧妙的结构等来提高此搜索的性能，但覆盖所有内容太广泛了。 - BartoszKP
基本上，边框不是由我链接在一起然后填充的一系列点绘制的，而是由计算机软件随机混合其他形状绘制的。 - Laurent Crivello
我想这些人试图询问的（方式较差）是在你的算法上下文中如何定义形状？它是从屏幕截图得来的位图，一个封闭区域上的一组点，一系列形状的列表或函数/样条曲线的交集？我理解你的意思，但知道你如何在代码中描述形状对于这个问题很重要。 - JasonN
感谢您的澄清，JasonN。这是从位图中截取的屏幕截图。 - Laurent Crivello
我认为我们有一张黑白位图，并且我们可以访问像素值。点是位图中的整数坐标，对吧？ - M Oehm
3个回答
5
您的形状被定义为位图，可以访问像素。
您可以在点周围扫描越来越大的正方形以查找边界像素。首先检查像素本身。然后检查一个宽度为2的正方形，覆盖点的八个相邻像素。接下来是宽度为4的下一个16个像素等等。当您找到边界像素时，请记录其距离并与找到的最小距离进行比较。当正方形的一半宽度大于当前最小距离时，可以停止搜索。
另一种方法是在点周围绘制不断增长半径的Bresenham圆。该方法类似于正方形方法，但是当您有一个命中时，可以立即停止，因为所有点都应该与您的点具有相同的距离。缺点是这种方法有些不准确，因为圆只是近似值。您还将错过沿着对角线的某些像素，因为Bresenham圆具有伪影。
（两种方法仍然非常暴力，在完全黑色位图的最坏情况下将访问每个节点。）
您需要一个边界像素的标准。您的形状是抗锯齿的，因此边界上的像素通过使它们成为灰色来平滑。如果您的标准是不是黑色的像素，则会选择略微在形状内部的点。如果您选择纯白色，则会落在稍微外面。也许最好选择灰度值大于0.5的像素作为边框。
如果您必须为相同形状的许多点找到最近的边界点，则可以预处理数据并使用其他[最近邻搜索]方法。
- M Oehm
2
像往常一样，这取决于数据，本例中是您的形状以及有关起始点的任何有用信息（它是否经常靠近边界，它是否经常靠近重心等）。
如果它们与您展示的类似，我可能会逐个测试边界点与起点。现在的问题是如何找到边界而不必检测整个形状的边缘。
问题在于似乎您可以拥有急剧凹陷的边界（想象一个圆形，上面突出一个微小的尖峰）。在这种情况下，您只需要检测形状的边缘并测试每个点。
我认为这些方法都有效，但不能保证。计算几何似乎非常容易理解，因此您可能可以在某个地方找到专家： 方法一 如果形状表现良好或您不介意错误，请尝试以下操作：
1- 画4条线（将形状分成四个象限）。并检查到每个边框的距离。我的意思是继续向北走，直到你碰到白色像素，然后向南，西和东走。
2- 取到目前为止已经画出来的两条最接近交点的线，平分它们创建的角度，并将新线添加到您的集合中。
3- 重复步骤二，直到您可以满意的误差范围。
实际上，您可以在此之前停止，并在足够小的间隔内沿两个接近点之间的边框进行追踪，检查它们之间的每个点以细化最终答案。 方法二（这适用于表现不佳的形状，并且与反锯齿兼容）：
1- 沿任何方向画一条线，直到它碰到边界（从黑色到白色）。这将是您的起始距离。
2- 在此距离处画一个圆圈，注意每次从黑色到白色或从白色到黑色时的交点。这些是您的交叉点。
只要您有两个以上的点，请将半径除以二并再次尝试。
如果您没有点，请将半径增加50％并再次尝试（基本上是二进制搜索，直到您获得两个点-如果您获得一个点，则很幸运地找到了答案）。
3- 您最近的点位于两个点之间的区域。沿着边框运行并检查每个点。
如果您想减少步骤3的成本，可以继续执行步骤2，直到获得足够小的范围以在步骤3中进行暴力搜索。
另外，为了防止非常不幸的开端，请画出四条初始线（也是东，南和西）并从最小距离开始。这些很容易绘制，并大大降低了选择确切最长距离并意外地认为单个像素是答案的机会。
如果它们与您展示的类似，我可能会逐个测试边界点与起点。现在的问题是如何找到边界而不必检测整个形状的边缘。
问题在于似乎您可以拥有急剧凹陷的边界（想象一个圆形，上面突出一个微小的尖峰）。在这种情况下，您只需要检测形状的边缘并测试每个点。
我认为这些方法都有效，但不能保证。计算几何似乎非常容易理解，因此您可能可以在某个地方找到专家： 方法一 如果形状表现良好或您不介意错误，请尝试以下操作：
1- 画4条线（将形状分成四个象限）。并检查到每个边框的距离。我的意思是继续向北走，直到你碰到白色像素，然后向南，西和东走。
2- 取到目前为止已经画出来的两条最接近交点的线，平分它们创建的角度，并将新线添加到您的集合中。
3- 重复步骤二，直到您可以满意的误差范围。
实际上，您可以在此之前停止，并在足够小的间隔内沿两个接近点之间的边框进行追踪，检查它们之间的每个点以细化最终答案。 方法二（这适用于表现不佳的形状，并且与反锯齿兼容）：
1- 沿任何方向画一条线，直到它碰到边界（从黑色到白色）。这将是您的起始距离。
2- 在此距离处画一个圆圈，注意每次从黑色到白色或从白色到黑色时的交点。这些是您的交叉点。
只要您有两个以上的点，请将半径除以二并再次尝试。
如果您没有点，请将半径增加50％并再次尝试（基本上是二进制搜索，直到您获得两个点-如果您获得一个点，则很幸运地找到了答案）。
3- 您最近的点位于两个点之间的区域。沿着边框运行并检查每个点。
如果您想减少步骤3的成本，可以继续执行步骤2，直到获得足够小的范围以在步骤3中进行暴力搜索。
另外，为了防止非常不幸的开端，请画出四条初始线（也是东，南和西）并从最小距离开始。这些很容易绘制，并大大降低了选择确切最长距离并意外地认为单个像素是答案的机会。
编辑：最后一个优化：由于对称性，您只需要计算第一象限的圆点（构成圆形边界的点），然后镜像它们。这应该能大大减少计算时间。
- JasonN
2
非常好。我喜欢使用圆形的二分搜索方法，这应该比我提出的方法更有效。 - M Oehm
@MOehm 更好的是使用三角形进行镶嵌。不要使用圆圈（这种方式是你的正方形和我的圆圈的混合物吗？），而是用三条相互间隔120度的线段来勾勒三角形，并找到交点。利用交点继续制作三角形，直到找到答案为止。如果没有交点，请从原点绘制更多线条并重试。我认为答案就在其中。 - JasonN
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接