c++ - 计算任意多边形的符号距离变换

Question

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

更新

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

谁能想出一个有效的方法来做到这一点？

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

Answer 1

坏消息:在最坏的情况下，一条线段可以在 N 点与多边形相交，并且所有 M 线段都可能出现这种情况。因此，在最坏的情况下，不可避免地要对片段与侧面进行详尽的比较。这有利于蛮力方法。

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