快速二维符号距离

Question

我需要一种方法来计算点和多边形边界之间的距离。

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

这称为有符号距离场/函数的SDF

多边形本身由多条路径组成，可以是凹的，有孔，但不能自相交，并且有很多顺时针排序的点（10000+）。

我找到了一些现有的解决方案，但他们需要针对每个多边形边测试点，这不够高效。

这是产生的视觉结果（绿色为正，红色为负）：

所以我尝试了以下方法：

将多边形边放在四叉树中

要计算距离，请找到距离该点最近的边，并根据该点所在边的哪一侧更改符号。

遗憾的是，当该点与多个边（例如角）的距离相同时，它不起作用。

我试过添加条件，所以如果点在所有边的外侧，它就在多边形之外，但它不能解决内部问题，反之亦然。

无法绕过它...

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

编辑

为了澄清，这里是角落出现的问题的特写：

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

人们可能认为一个点必须在两个线段的内侧才能被视为“在”。它解决了角度 < 180° 的问题，但问题是角度 > 180° 的镜像

最糟糕的是，两个或多个角可以共享相同的位置（例如第一张图像下部的四向角）......

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 模块来计算有符号距离。

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