到形状边界的最近距离
Closest distance to border of shape
我有一个形状（下方黑色）和形状内的一个点（下方红色）。找到我的红点和形状边界（图形上的绿点）之间最近距离的算法是什么？
形状边框不是一系列线条，而是随机绘制的形状。
谢谢。
如果您根据“从起始像素到达边距上的任何像素所需采取的最小步数”来定义距离，则此可以使用任何最短路径搜索算法解决问题，例如 bread first search or even better if you use A* search algorithm.
所以你的形状被定义为位图，你可以访问像素。
您可以扫描点周围不断增长的方块以寻找边界像素。首先，检查像素本身。然后检查覆盖该点八个相邻像素的宽度为 2 的正方形。接下来，接下来的 16 个像素的宽度为 4，依此类推。当您找到边界像素时，记录它的距离并检查找到的最小距离。当正方形的一半宽度大于当前最小距离时，可以停止搜索。
另一种方法是在该点周围绘制 Bresenham circles 逐渐增大的半径。该方法类似于平方方法，但是当您命中时可以立即停止，因为所有点都应该与您的点具有相同的距离。缺点是这种方法有些不准确，因为圆只是一个近似值。您还会错过一些沿斜线的像素，因为 Bresenham 圆有人工制品。
（这两种方法仍然相当暴力，在全黑位图的最坏情况下将访问每个节点。）
您需要一个边界像素的标准。你的形状是抗锯齿的，所以边界上的像素通过使它们成为灰色阴影来平滑。如果您的标准是不是黑色的像素，您将选择形状内部的一点。如果你选择纯白色，你会落在外面一点。也许最好选择灰度值大于0.5的像素作为边框。
如果对于同一个形状，需要找到距离多个点最近的边界点，可以对数据进行预处理，使用[最近邻搜索]的其他方法。
一如既往，这取决于数据，在这种情况下，你的形状是什么样的以及关于你的起点的任何有用信息（它是否经常靠近边界，它是否经常靠近质心， ETC）。
如果它们与您展示的相似，我可能会在开始时单独测试边界点。现在的问题是如何在不必对整个形状进行边缘检测的情况下找到边界。
问题是你的边界看起来很尖锐（想像一个圆圈，里面有一个尖刺状的细长条）。在这种情况下，您只需要边缘检测形状并测试每个点。
我认为这些会奏效，但请不要坚持。计算几何似乎很好理解，所以你可能会在某个地方找到专业人士：
方法一
如果形状很好或者你不介意错了试试这个：
1- 画 4 条线（将形状分成四个象限）。并检查到每个边界的距离。我所说的绘制的意思是继续向北直到你碰到一个白色像素，然后向南、向西和向东。
2- 将您到目前为止绘制的两条线的交点最近，平分它们创建的角度，然后将新线添加到您的集合中。
3- 不断重复第二步，直到达到可以满意的容忍度。
实际上你可以在此之前停下来，在足够小的间隔内追踪两个接近点之间的边界，检查它们之间的每个点以完善最终答案。
方法二（这将适用于表现不佳的形状并且可以很好地处理抗锯齿）：
1- 向任意方向画一条线，直到他碰到边界（黑到白）。这将是您的起始距离。
2- 在此距离处画一个圆圈，注意每次从黑到白或从白到黑。这些是你的交点。
只要你有两个以上的点，把半径分成两半再试一次。
如果你没有分数，将你的半径增加 50%，然后重试（基本上是二进制搜索，直到你得到两个点 - 如果你得到一个，你很幸运并找到了你的答案）。
3- 你的壁橱点位于你的两个点之间的区域。 运行 沿边界检查每一个。
如果你愿意，为了降低第 3 步的成本，你可以继续执行第 2 步，直到你在第 3 步中获得足够小的范围以进行暴力破解。
同时为了防止非常不幸的开始，绘制四条初始线（也是东、南和西）并从最小的距离开始。这些很容易画，大大减少了你选择最准确的最长距离和意外地认为单个像素就是答案的机会。
编辑：最后一个优化：由于对称性，你只需要计算第一象限的圆点（构成圆边界的那些点），然后镜像它们。应该大大减少计算时间。
我有一个形状（下方黑色）和形状内的一个点（下方红色）。找到我的红点和形状边界（图形上的绿点）之间最近距离的算法是什么？
形状边框不是一系列线条，而是随机绘制的形状。
谢谢。
如果您根据“从起始像素到达边距上的任何像素所需采取的最小步数”来定义距离，则此可以使用任何最短路径搜索算法解决问题，例如 bread first search or even better if you use A* search algorithm.
所以你的形状被定义为位图，你可以访问像素。
您可以扫描点周围不断增长的方块以寻找边界像素。首先，检查像素本身。然后检查覆盖该点八个相邻像素的宽度为 2 的正方形。接下来，接下来的 16 个像素的宽度为 4，依此类推。当您找到边界像素时，记录它的距离并检查找到的最小距离。当正方形的一半宽度大于当前最小距离时，可以停止搜索。
另一种方法是在该点周围绘制 Bresenham circles 逐渐增大的半径。该方法类似于平方方法，但是当您命中时可以立即停止，因为所有点都应该与您的点具有相同的距离。缺点是这种方法有些不准确，因为圆只是一个近似值。您还会错过一些沿斜线的像素，因为 Bresenham 圆有人工制品。
（这两种方法仍然相当暴力，在全黑位图的最坏情况下将访问每个节点。）
您需要一个边界像素的标准。你的形状是抗锯齿的，所以边界上的像素通过使它们成为灰色阴影来平滑。如果您的标准是不是黑色的像素，您将选择形状内部的一点。如果你选择纯白色，你会落在外面一点。也许最好选择灰度值大于0.5的像素作为边框。
如果对于同一个形状，需要找到距离多个点最近的边界点，可以对数据进行预处理，使用[最近邻搜索]的其他方法。
一如既往，这取决于数据，在这种情况下，你的形状是什么样的以及关于你的起点的任何有用信息（它是否经常靠近边界，它是否经常靠近质心， ETC）。
如果它们与您展示的相似，我可能会在开始时单独测试边界点。现在的问题是如何在不必对整个形状进行边缘检测的情况下找到边界。
问题是你的边界看起来很尖锐（想像一个圆圈，里面有一个尖刺状的细长条）。在这种情况下，您只需要边缘检测形状并测试每个点。
我认为这些会奏效，但请不要坚持。计算几何似乎很好理解，所以你可能会在某个地方找到专业人士：
方法一 如果形状很好或者你不介意错了试试这个：
1- 画 4 条线（将形状分成四个象限）。并检查到每个边界的距离。我所说的绘制的意思是继续向北直到你碰到一个白色像素，然后向南、向西和向东。
2- 将您到目前为止绘制的两条线的交点最近，平分它们创建的角度，然后将新线添加到您的集合中。
3- 不断重复第二步，直到达到可以满意的容忍度。
实际上你可以在此之前停下来，在足够小的间隔内追踪两个接近点之间的边界，检查它们之间的每个点以完善最终答案。
方法二（这将适用于表现不佳的形状并且可以很好地处理抗锯齿）：
1- 向任意方向画一条线，直到他碰到边界（黑到白）。这将是您的起始距离。
2- 在此距离处画一个圆圈，注意每次从黑到白或从白到黑。这些是你的交点。
只要你有两个以上的点，把半径分成两半再试一次。
如果你没有分数，将你的半径增加 50%，然后重试（基本上是二进制搜索，直到你得到两个点 - 如果你得到一个，你很幸运并找到了你的答案）。
3- 你的壁橱点位于你的两个点之间的区域。 运行 沿边界检查每一个。
如果你愿意，为了降低第 3 步的成本，你可以继续执行第 2 步，直到你在第 3 步中获得足够小的范围以进行暴力破解。
同时为了防止非常不幸的开始，绘制四条初始线（也是东、南和西）并从最小的距离开始。这些很容易画，大大减少了你选择最准确的最长距离和意外地认为单个像素就是答案的机会。
编辑：最后一个优化：由于对称性，你只需要计算第一象限的圆点（构成圆边界的那些点），然后镜像它们。应该大大减少计算时间。