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

您将如何计算多边形的有符号距离函数，由任意一组点描述。多边形可以是凹形或凸形的。假设这些点以逆时针方向缠绕在std::vector中。计算任意多边形的有符号距离变换

更新

让我更具体。这不是网格上的采样函数。我需要能够检测沿通过（不一定相交）多边形绘制的任意线段的符号变化，而不检查每个线段的单个交点。问题是，我可能有成千上万的线段。

任何人都可以想到一个有效的方法吗？

如果我可以参数化表达SDF，我可以计算一个导数来完成这个。

来源

2017-01-23 Jacques Nel

我会用数学。 – deW1

你现在做了什么？ – max66

到目前为止，我已经玩过使用set操作来创建来自不同线段的参数SDF。建设性实体几何似乎是一个很好的起点。 https://en.wikipedia.org/wiki/Constructive_solid_geometry 问题是，最终会出现一堆来自'min'' max'操作的分段方程。也许我可以将边界描述为平滑插值的贝塞尔或其他东西。 –

首先旋转所有点，使线与x轴平行。然后转换，以便该线是x轴。然后作为测试整合。直线x0y0 x1y1下的面积非常易于计算。您可以对所有表达式进行求和以得到不确定积分或有符号区域，该区域应独立于轴（因为曲线下的点相减）。现在要回答具体问题，按x排序，以便您可以在给定的x处找到点值。因此，创建两个“事件”，节开始和节“结束”与指针或引用回到开始事件。然后为了在任何时刻获得距离变换，我们计算所有与x相关的事件。如果你想为每个事件间隔分段函数，那实际上可以稍微简单一些，因为你可以从头到尾遍历队列。

来源

2017-01-23 20:47:50

坏消息：在最坏的情况下，一条线段可以与N点中的多边形相交，并且这可能对于所有M线段都会产生。因此，在最糟糕的情况下，细分与侧面的详尽比较是不可避免的。这有利于暴力方法。

幸运的是，输出敏感的解决方案以使用扫描线方法的N线段交点问题而闻名。复杂度可降至O((N+K) log N)或O(N log N + K)其中K是找到的交点数。

来源

2017-01-24 13:28:34

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

回答

相关问题