计算任意多边形的有符号距离变换

Question

如何计算由任意点集描述的多边形的有符号距离函数？该多边形可能是凸的或凹的。假设这些点以逆时针方向存储在std :: vector中。

更新

让我更具体一些。这不是在网格上采样的函数。我需要能够检测通过多边形的任意线段上的符号变化，而不必检查每个线段的交点，这条线段不一定与多边形相交。问题是，我可能有数千条线段。

有人能想到一种有效的方法吗？

如果我可以参数化表达SDF，我就可以计算导数来实现这一点。

- Jacques Nel

---

我会使用数学。 - deW1

你目前做了什么？ - max66

到目前为止，我已经尝试使用集合运算从不同的线段创建参数化SDF。建设性固体几何似乎是一个不错的起点。https://en.wikipedia.org/wiki/Constructive_solid_geometry问题是，你最终会得到许多由“min”和“max”操作形成的分段函数。也许我可以将边界描述为平滑插值的贝塞尔曲线或其他类型的曲线。 - Jacques Nel

另一个选择是使用基函数来逼近曲线。可能类似于2D泰勒级数，但是由于吉布斯现象，在尖角处会出现振铃。对于项目的这一部分，尖锐特征并不重要。 - Jacques Nel

这不是个好主意，有两个原因。1. 因为符号函数无论如何被评估，都必须包括多边形的2N个自由度，并且将不可避免地需要O(N)的计算时间。 2. 因为搜索符号变化将需要在几个位置（最少2个但可能更多）评估符号函数，无论搜索算法如何。 因此，对于M个段而言，总成本可能超过O(N.M)。 - user1196549

Answer 1

不好的消息是，在最坏情况下，一条线段可以在多达N个点处与多边形相交，而这可能发生在所有M条线段上。因此，在最坏情况下，无法避免对线段与边缘进行详尽的比较。这有利于暴力方法。

幸运的是，对于相交N条线段的问题，使用扫描线方法已知有输出敏感型解决方案。复杂度可以降低到O((N+K) log N)或O(N log N + K)，其中K是找到的相交数。

- user1196549

Answer 2

首先将所有点旋转，使得直线与x轴平行。然后平移，使得直线成为x轴。接着进行测试积分。一条直线x0y0 x1y1下的面积计算起来非常简单。您可以对所有表达式求和以获得无限积分或有符号面积，这应该与轴无关（因为曲线下的点会相互抵消）。现在回答具体问题，按x排序以便您可以找到给定x处的点值。因此，创建两个“事件”，即“部分开始”和“部分结束”，并带有指向开始事件的指针或引用。然后，要获取任何点的距离变换，我们计算所有穿过感兴趣的x的事件。如果您想要每个事件间隔的分段函数，那实际上会更容易，因为您可以从开始到结束通过队列。

- Malcolm McLean