凹面多边形线条裁剪不退化边缘

我有搜索和研究互联网最后几天找到适合我的问题的方法。凹面多边形线条裁剪不退化边缘

问题：

剪辑针对无限线凹多边形没有方向（事实上与一平面的多边形在3D但问题是类似我觉得）。目前我使用Sutherland-Hodgman，但生成的多边形有时包含由退化边创建的零面积零件，它也不支持包含孔的多边形。

我发现可以解决我的问题的最好的算法是Weiler-Atherton算法，但是它是针对具有顺时针边缘的多边形进行裁剪，并且我拥有的是一个无限长线（在3D平面中）缺少方向信息。

问：

是否有一个算法来剪辑适合我的需要凹多边形或做任何人对如何修改维勒 - 阿瑟顿算法建议，对于这种情况的工作？有网页表明它可以推广到支持更多的案例，但我无法弄清楚。

//问候英贤

来源

2010-10-07 Eiken

你可以使用一个多边形推剪*通过转换行成一个裁剪多边形来解决这个问题。假设你没有在近水平面上剪切，只要确保剪切多边形的临界（裁剪）边缘比主题多边形的垂直尺寸稍大（即边缘在目标多边形的上方和下方延伸）。如果在近水平面上剪裁，确保关键边缘比主体稍宽。

*如帆船 - http://sourceforge.net/projects/polyclipping/

披露：我剪的作者，所以有一个个人偏见的潜力。

来源

2010-10-07 19:15:59

。是的，我试图找出一个好方法来处理这个问题。我的多边形在三维空间中很难决定如何将线条转换为合适的多边形，因为主题多边形可以旋转怪异，这使得很难决定从线条（从平面/平面相交处）到哪个方向展开多边形。 – Eiken 2010-10-08 12:07:22

我认为你可以在2D空间中定义剪切线。如果其绝对斜率小于1（即接近水平），则剪切线段（和剪切多边形的一条边）需要延伸到主题多边形的左右范围之外。其他边缘可以轴对齐，只要确保水平边缘高于（或低于）主题多边形的范围即可。同样，如果剪切线的绝对斜率大于1，则使用相同的逻辑，但将其旋转90度。 – 2010-10-08 17:04:12

是的，这将基本上与我在图形宝石V中发现的算法基本相同的理论，除了它更加简化，正是我想要做的，我可以跳过表示我的飞机作为线的步骤。还是谢谢你的回答。 Stackoverflow是一个了不起的资源。 – Eiken 2010-10-09 16:16:59

在Graphic Gems V中找到了合适的算法来解决我的问题。如果有人有同样的问题，这是参考：

格拉斯纳，A '' 裁剪凹多边形'，在图形宝石V，A. Paeth编，学术出版社，剑桥，1995年

来源

2010-10-09 16:19:49 Eiken

凹面多边形线条裁剪不退化边缘

回答

相关问题