快速2D有符号距离

Question

我需要一种计算点与多边形边界距离的方法。

• 如果点在多边形外部，距离将为正数
• 如果点在多边形内部，距离将为负数

这被称为 有符号距离场/函数 Signed Distance Field/Function。

该多边形由多个路径组成，可以是凹形的，带有空洞，但不能自交，并且有很多顺时针排序的点（10000+）。

我发现了一些现有解决方案，但它们需要对每个多边形边缘测试点，这不够高效。

以下是生成的可视结果（绿色为正，红色为负）：

所以我尝试了以下方法：

将多边形的边放入四叉树中

为了计算距离，需要找到最接近该点的边，并根据该点位于边的哪一侧改变符号。

遗憾的是，当该点与多个边缘处于相同距离时（例如角落），该方法无效。

我尝试添加条件，如果一个点在所有边的外部，则它在多边形外部，但这并不能解决内部问题，反之亦然。

我无法理解这个问题...

如果有人感到好奇，这个想法是之后使用一些着色器来生成这样的图像：

编辑

为了澄清问题，这里是在拐角处出现的问题的近距离照片：

• 对于区域A中的所有点，最近的线段是S1，因此没有问题
• 对于区域E中的所有点，最近的线段是S2，因此也没有问题
• 区域B、C和D中的所有点与S1和S2的距离相同
  • 区域B中的点位于S1的外侧和S2的内侧
  • 区域D中的点位于S1的内侧和S2的外侧
  • 区域C中的点位于两个线段的外侧

有人可能认为一个点必须在两个线段的内侧才能被视为“在内部”。这解决了角度小于180°的问题，但是对于角度大于180°的问题则恰好相反。

更糟糕的是，两个或更多的角落可以共享相同的位置（例如第一张图中低部的四路口）...

- Nicolas Repiquet

---

看一下自适应采样距离场。我记得他们的论文之一包括了他们八叉树实现的示例源代码。 - RaffleBuffle

孔洞是否按逆时针顺序？ - David Eisenstat

是的，你已经说过了。但我想让你回答我的问题。 - Ripi2

好的。我认为你的四叉树是可行的方案。你说你在角落处发现了问题。这不应该出现（请检查你的代码）。也许如果你将一条线分成若干段，使每一段都适合于四叉树中的一个矩形，那么就可以避免错误的最近边缘。 - Ripi2

在OpenCV中，有一个名为pointPolygonTest的函数。 - dhanushka

Answer 1

希望这能解决你的问题。

这是用Python实现的。

首先，我们使用imageio将图像导入为数组。 我们需要使用修改后的版本的图像（我用白色填充了内部区域）。

然后，我们将RGBA矩阵转换为二进制矩阵，并使用0轮廓定义接口（代码片段中的phi）

以下是来自代码片段的phi（内部区域值= +0.5，外部区域值= -0.5）:

import imageio
import numpy as np
import matplotlib.pyplot as plt
import skfmm

# Load image
im = imageio.imread("0WmVI_filled.png")
ima = np.array(im)

# Differentiate the inside / outside region
phi = np.int64(np.any(ima[:, :, :3], axis = 2))
# The array will go from - 1 to 0. Add 0.5(arbitrary) so there 's a 0 contour.
phi = np.where(phi, 0, -1) + 0.5

# Show phi
plt.imshow(phi)
plt.xticks([])
plt.yticks([])
plt.colorbar()
plt.show()

# Compute signed distance
# dx = cell(pixel) size
sd = skfmm.distance(phi, dx = 1)

# Plot results
plt.imshow(sd)
plt.colorbar()
plt.show()

最后，我们使用scikit-fmm模块计算带符号距离。

这是生成的带符号距离场：

- Robin Thibaut

---

谢谢Robin。它并没有真正解决我的问题：我试图表示的地面非常巨大（1平方公里的工业区，具有相当详细的分辨率），所以我没有奢侈的渲染它全尺寸并对其进行一些行进算法。它将被平铺并按需呈现。无论如何，你的方法非常有趣。再次感谢你的帮助。 - Nicolas Repiquet

Answer 2

对于闭合、不相交且定向良好的多边形，您可以通过仅限于基于 this paper 的特征挤出来加速有符号距离场的计算。

如您在图像中所示（区域A和E），线上最近的点位于边缘挤压内。而对于B、C和D中的点，最近的特征不是边缘而是顶点。

算法如下：

- 对于每个边和顶点构建负面和正面的挤出 - 对于每个点，确定它们在哪些挤出内，并找到正确符号的最小幅度距离。

这样可以将工作量减少到点与多边形的测试以及线段和点的距离计算。为了减少工作量，您可以考虑使用相同大小的有限挤出来定义一个薄壳，其中计算距离值。这似乎是您光晕着色示例所需的功能。

虽然您仍然必须迭代所有特征，但两种挤出类型始终是凸的，因此您可以从四叉树、半平面测试和其他优化中提前退出，尤其是在有限挤出距离的情况下。

边缘的挤出物在表面法线方向上是矩形（对于内部距离来说，法线为负）。

来自1。

顶点的挤出物是楔形，其侧面是相遇于该顶点的边缘的法线。根据边缘之间的角度，顶点具有正或负的挤出物。平坦的顶点将没有挤出物，因为空间被边缘的挤出物覆盖了。

来自1。

- dubious