快速二维符号距离

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

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

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

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

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

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

所以我尝试了以下方法：

将多边形边放在四叉树中

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

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

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

无法绕过它...

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

编辑

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

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

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

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