我有一个形状(下图中的黑色部分)和一个在该形状内的点(下图中的红色部分)。如何计算出红点与形状边界之间的最短距离(即图中的绿点)?
形状边界不是一系列直线,而是一个随机绘制的形状。
形状边界不是一系列直线,而是一个随机绘制的形状。
您的形状被定义为位图,可以访问像素。
您可以在点周围扫描越来越大的正方形以查找边界像素。首先检查像素本身。然后检查一个宽度为2的正方形,覆盖点的八个相邻像素。接下来是宽度为4的下一个16个像素等等。当您找到边界像素时,请记录其距离并与找到的最小距离进行比较。当正方形的一半宽度大于当前最小距离时,可以停止搜索。
另一种方法是在点周围绘制不断增长半径的Bresenham圆。该方法类似于正方形方法,但是当您有一个命中时,可以立即停止,因为所有点都应该与您的点具有相同的距离。缺点是这种方法有些不准确,因为圆只是近似值。您还将错过沿着对角线的某些像素,因为Bresenham圆具有伪影。
(两种方法仍然非常暴力,在完全黑色位图的最坏情况下将访问每个节点。)
您需要一个边界像素的标准。您的形状是抗锯齿的,因此边界上的像素通过使它们成为灰色来平滑。如果您的标准是不是黑色的像素,则会选择略微在形状内部的点。如果您选择纯白色,则会落在稍微外面。也许最好选择灰度值大于0.5的像素作为边框。
如果您必须为相同形状的许多点找到最近的边界点,则可以预处理数据并使用其他[最近邻搜索]方法。
编辑:最后一个优化:由于对称性,您只需要计算第一象限的圆点(构成圆形边界的点),然后镜像它们。这应该能大大减少计算时间。