如何使用其直形骨架计算多边形的斜接偏移量 [英] How to compute the mitered offset of a polygon using its Straight Skeleton
问题描述
我有一个用Python实现的Straight Skeleton算法，想用它来抵消多边形的边缘.
不幸的是，我已经看到了几篇论文暗示这种抵消方法，但没有一篇提供有关如何实现的具体信息.其中:
-
(较高质量的
问题:使用多边形的直线骨架"来计算多边形的斜接偏移的正确方法是什么?
解决方案我不确定您在第二张图片中显示的偏移量是怎么回事，但是一旦您计算出偏移量，应该很简单有骨架.
骨架的每个弧形都可以看作是3空间中的线段(或射线)，第3个坐标是时间.也就是说，它在某个时间t_s(在事件中创建它或作为入射到输入点的初始波前顶点)开始，并在某个波前事件的某个时间t_v(如果它是有界边)结束.
现在，要找到距离为t的偏移曲线，遍历所有圆弧，对于时间t处存在的尚未访问的每个圆弧(即t_s< t< t_e)，在一个圆弧段中开始一个偏移段两个入射面中的一个.让这个弧成为一个.
当然，问题是此段在哪里结束.要找到其端点，请沿着笔直的骨架面行走，首先沿波前传播的方向移动.也就是说，您看到的下一个弧在a的t_e处入射.沿着脸走，直到找到在t期间还活着的另一个弧a'.这是您的细分受众群停止的地方.如果您以前从未看过a'，那么您可以以相同的方式在a'的另一侧找到另一个偏移量段.
查看完笔直骨架的所有圆弧后，您将拥有一组线段，这些线段代表您在时间t处的偏移曲线.
这可能是您要尝试执行的操作，但是从动画中并不清楚.
此外，您显示的骨架似乎是正确的(由于动画，很难看到)，但偏移的线段却看起来像是笔直的骨架弧线.每个偏移段都应始终限于一个笔直的骨架面(它将平行于入射到该面并产生该面的输入边).
也请参见.P.和举行:基于直形骨骼的斜切偏移曲线的计算(CADA，12(4)，2015).
I have a Straight Skeleton algorithm implemented in Python and would like to use it to offset the edges of a polygon.
I have seen several papers suggesting this offsetting approach unfortunately none of them provides specific information on how to achieve it. Among them:
Since the very definition of a Straight Skeleton is based on the continuous wavefront or grassfire propagation of the edges, it is specially suited for polygon offsetting. In particular, it can be used to obtain the so-called "mitered" offsetting were corners remain as such in the offset polygon
If the skeleton of P is already known then the computation of a single offset curve for any given radius r is simple, efficient (linear time) and numerically stable. All one has to do is to traverse the skeleton in a certain way and insert element by element of the offset curve.
I tried for each edge to constrain the offsets to their surrounding "bones" but found that the output was not satisfactory: some offsets are not matching and I see gaps where lines should be touching each other.
(higher quality here)
Question: What is the correct way to compute the mitered offset of a polygon using its Straight Skeleton?
解决方案I'm not exactly sure what is going on with the offsets you show in your second image, however it should be quite straight forward to compute the offsets once you have the skeleton.
Each arc of the skeleton can be seen as a line segment (or ray) in 3space, with the 3rd coordinate being time. That is, it starts at some time t_s (when it was created in an event or as an initial wavefront vertex that is incident to an input point) and ends at some time t_v (if it is a bounded edge) in some wavefront event.
Now, to find an offset curve of distance t, iterate over all arcs, and for each arc you have not yet visited that exists at time t (i.e. t_s < t < t_e), start an offset segment in one of the two incident faces. Let this arc be a.
The question, of course, then is where does this segment end. To find its endpoint, walk along the straight skeleton face, initially moving along the direction of the wavefront propagation. That is, the next arc you look at is incident to a at t_e of a. Walk along the face until you find another arc, a', that is alive during t. This is where your segment stops. If you have not seen a' before, then there is another offset segment on the other side of a' that you can find in the same way.
Once you have looked at all the arcs of the straight skeleton, you will have a set of line segments that represents your offset curve(s) at time t.
This might be what you're trying to do, but it's not exactly clear from your animation.
Also, the skeleton you show appears to be correct (it's hard to see, because animation), but it appears your offset segments cross straight skeleton arcs. Each offset segment should always be confined to exactly one straight skeleton face (and it will be parallel to the input edge that is incident to and which emanated this face).
Also cf. P. and Held: Computing Mitered Offset Curves Based on Straight Skeletons (CADA, 12(4), 2015).
这篇关于如何使用其直形骨架计算多边形的斜接偏移量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
