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

Question

我在Python中实现了直骨架算法，并希望将其用于多边形边缘的偏移。

我看过几篇文章建议采用这种抵消方法，但不幸的是，它们中没有一篇提供如何实现的具体信息。 其中：

• 带孔简单2D多边形的CGAL直骨架实现

由于直骨架的定义基于边缘的连续波前或草火传播，因此它特别适用于多边形抵消。特别地，它可以用来获得所谓的“斜接”抵消，其中角落保持为偏移多边形的角落。

• 骨架和抵消：拓扑观点

如果已经知道P的骨架，则为任何给定半径r计算单个偏移曲线是简单的、高效的（线性时间）和数值稳定的。所有需要做的就是以一定的方式遍历骨架，并逐个插入偏移曲线元素。

我尝试限制每个边缘的偏移量到它们周围的“骨头”，但发现输出结果不尽如人意：有些偏移没有匹配，我看到应该接触的线之间有间隙。

(更高质量此处)

问题: 如何使用多边形的直线骨架计算其斜角偏移的正确方法？

- solub

---

飞机轮廓的输入（即）是否可在任何地方（以自由许可证形式）获得，并且您使用了什么偏移距离（想要使用）？ - weasel - Peter Palfrader

正如@weasel所提到的，已知骨架后获取偏移量应该是微不足道的。在您的下图中，在偏移量的问题部分（左侧）开始时，似乎偏移量“穿透”了相反的一侧，直线骨架应该有助于避免这种问题。您可以将输出与https://github.com/cgalab/surfer2进行比较--这是一个允许偏移量的直线骨架代码。 - gue

感谢你们两位的回复。在@ gue的建议下，我尝试使用另一个库测试输出结果，发现我的实现并不完全正确。骨架上微小的角度差异导致偏移量之间存在小的不匹配。我现在明白了偏移方法是正确的，但应用于不适当的骨架上。 - solub

Answer 1

我不确定你第二张图片中展示的偏移量是什么意思，但是一旦有了骨架，计算偏移量应该很简单。

骨架的每个弧可以看作是三维空间中的线段（或射线），其中第三个坐标是时间。也就是说，它从某个时间t_s开始（在事件中创建或作为与输入点相交的初始波前顶点）并在某个波前事件中以时间t_e结束（如果它是一个有界边）。

现在，要找到距离t的偏移曲线，迭代所有弧，并对于每个弧，在时间t存在且尚未访问的情况下（即t_s < t < t_e），在两个相邻面之一开始一个偏移线段。让这条弧是a。

当然，问题是这个分段的终点在哪里。为了找到它的端点，请沿着直线骨架面走，最初沿着波前传播的方向移动。也就是说，您看到的下一条弧是与a的t_e相接的。沿着面行走，直到您找到另一个弧a'，该弧在t时仍然存在。这就是您的片段停止的地方。如果您以前没有看过a'，那么在a'的另一侧会有另一个偏移段，您可以以同样的方式找到它。

一旦您查看了直线骨架的所有弧，您将获得一组线段，表示时间t的偏移曲线。

这可能是您想要做的事情，但从您的动画中并不完全清楚。

此外，您展示的骨架似乎是正确的（因为动画很难看），但是您的偏移段穿过了直线骨架弧。每个偏移段应始终局限于一个直线骨架面（它将与与之相接和发出该面的输入边平行）。

另请参阅P. and Held：基于直线骨架计算斜角偏移曲线的计算（CADA，12（4），2015）。

- weasel - Peter Palfrader

---

正如我在上面的另一条评论中提到的，我错误地假设我的实现是正确的，但实际上并不是。骨架中的轻微扭曲导致偏移量不匹配。话虽如此，您的答案正确回答了原始问题，并且解释得很好（+1）。感谢您的时间。 - solub