如何使用多边形的直形骨架计算斜接的偏移量

我有一个用Python实现的Straight Skeleton算法，想用它来抵消多边形的边缘。

不幸的是，我见过几篇论文暗示了这种抵消方法，但没有一篇提供有关如何实现的具体信息。其中：

由于直形骨架的定义基于连续的波前或边缘的草火传播，这是特别适用于多边形偏移。特别是可以使用以获得所谓的“偏斜”偏移量例如在偏移多边形中

如果P的骨架是已知的，则计算单个任何给定半径r的偏移曲线简单，有效（线性时间）并且数值稳定。要做的就是遍历骨骼以某种方式并逐条插入偏移曲线。

[我尝试将每个边缘的偏移量限制在其周围的“骨骼”，但发现输出效果不理想：某些偏移量不匹配，并且我看到线应该相互接触的间隙。

（更高质量here）

问题：使用多边形的直形骨架来计算其斜切偏移的正确方法是什么？

3
投票

我不确定您在第二张图片中显示的偏移量是怎么回事，但是一旦有了骨架，计算偏移量应该很简单。

骨骼的每个弧线都可以看作是3空间中的线段（或射线），第3个坐标是时间。也就是说，它在某个时间t_s（在事件中创建它或作为入射到输入点的初始波前顶点）开始，并在某个波前事件的某个时间t_v（如果它是边界边）结束。

现在，要找到距离t的偏移曲线，遍历所有圆弧，对于在时间t存在的尚未访问的每个圆弧（即t_s

当然，问题是此段在哪里结束。要找到其端点，请沿着笔直的骨架面行走，首先沿波前传播的方向移动。也就是说，您看到的下一个弧在a的t_e处入射。沿着脸走动，直到找到在t期间还活着的另一个弧a'。这是您的细分受众群停止的地方。如果您以前从未看过a'，则可以用相同的方式在a'的另一侧找到另一个偏移线段。

一旦查看了笔直骨架的所有圆弧，您将拥有一组线段，这些线段代表您在时间t处的偏移曲线。

这可能是您要尝试执行的操作，但是从动画中并不清楚。

而且，您显示的骨骼似乎是正确的（这很难看，因为有动画效果，但是它的偏移线段似乎是跨直的骨骼弧。每个偏移段都应始终限于一个笔直的骨架面（它将平行于入射到该面并产生该面的输入边）。