algorithm - 快速 2D 有符号距离

Question

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

如果该点在多边形之外，则距离将为正

如果点在多边形内，距离将为负

这称为 Signed Distance Field/Function 的 SDF
多边形本身由多条路径组成，可以是凹的，有孔，但不能自相交，并且有很多顺时针排列的点(10000+)。

我找到了一些 existing solutions ，但他们需要针对每个多边形边缘测试该点，这不够有效。
这是产生的视觉结果(绿色为正，红色为负):

所以我尝试了以下方法:
将多边形边放在四叉树中

要计算距离，请找到距离该点最近的边缘，并根据该点位于边缘的哪一侧更改符号。
可悲的是，当该点与多个边缘(例如角落)的距离相同时，它不起作用。
我已经尝试添加条件，如果一个点位于所有边缘的外侧，则它位于多边形之外，但它不能解决内部问题，反之亦然。
无法绕开我的头...

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

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

对于区域A中的所有点，最近的段是S1，所以没问题

对于区域E中的所有点，最近的段是S2，所以也没有问题

区域 B、C 和 D 中的所有点与 S1 和 S2 的距离相同

区域 B 中的点位于 S1 的外侧和 S2 的内侧

区域 D 中的点位于 S1 的内侧和 S2 的外侧

区域 C 中的点位于两条线段的外侧

有人可能会认为一个点必须在两个段的内侧才能被认为是“在”。它解决了角度 < 180° 的问题，但问题反射(reflect)了角度 > 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 模块来计算有符号距离。
这是生成的有符号距离场: