无退化边缘的凹多边形线裁剪
我最近几天在互联网上进行了搜索和研究，以找到适合我的问题的方法。
问题：
将凹多边形剪裁成没有方向的无限线（实际上是 3d 中的平面上的多边形，但我认为问题是类似的）。目前我使用 Sutherland-Hodgman，但生成的多边形有时包含从退化边缘创建的零面积部分，并且它也不支持包含孔的多边形。
我发现可以解决我的问题的最佳算法是 Weiler-Atherton 算法，但它是针对具有顺时针边缘的多边形进行裁剪的，而我所拥有的只是一条无限的线（在 3d 平面中）缺少方向信息。
问题：
是否有一种算法可以满足我的需要来裁剪凹多边形，或者有人对如何修改 Weiler-Atherton 算法以适用于这种情况有建议吗？有网页表明它可以推广以支持更多情况，但我无法弄清楚。
//问候 英肯
I have search and researched the internet last days to find a suitable method for my problem.
Problem:
Clip a concave polygon against an infinite line without direction (Actually a polygon against a plane in 3d but the problem is similar i think). Currently i use Sutherland-Hodgman but the resulting polygons sometimes contains zero-area parts created from degenerate edges and it also do not support polygons containing holes.
The best algorithm i have found that could solve my problem is the Weiler-Atherton algorithm but it is for clipping against a polygon with clockwise edges and all i have is an infinite line (in 3d a plane) missing direction info.
Question:
Is there a algorithm to clip a concave polygon that suits my needs or do anyone have a suggestion on how to modify the Weiler-Atherton algorithm to work for this case? There are webpages that suggests it can be generalized to support more cases but i can not figure it out.
//Regards
Eiken
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
在 Graphic Gems V 中找到了合适的算法来解决我的问题。如果有人遇到同样的问题，请参考：
Glassner, A., ''Clipping a Concave Polygon'' , in Graphics Gems V, A. Paeth, ed.,Academic Press, Cambridge, 1995
Found a suitable algorithm in Graphic Gems V which solves my problem. If someone have the same problem this is the reference:
Glassner, A., ''Clipping a Concave Polygon'' , in Graphics Gems V, A. Paeth, ed., Academic Press, Cambridge, 1995
您可以使用多边形裁剪器* 通过将线转换为裁剪多边形来解决此问题。假设您不在接近水平面中进行剪裁，只需确保剪裁多边形的关键（剪裁）边稍大于主题多边形的垂直尺寸（即，边缘在主题多边形的上方和下方延伸）。如果在接近水平面的地方进行剪裁，请确保关键边缘比拍摄对象稍宽。
*例如 Clipper - http://sourceforge.net/projects/polyclipping/
披露：我是Clipper 的作者，因此可能存在个人偏见。
You could use a polygon clipper* to solve this by converting the line into a clipping polygon. Assuming you aren't clipping in a near horizontal plane, just make sure the critical (clipping) edge of the clipping polygon is a little larger than the subject polygon's vertical dimensions (ie the edge extends a above and below the subject polygon). If clipping in a near horizontal plane, make sure the critical edge is a little wider than the subject.
*eg Clipper - http://sourceforge.net/projects/polyclipping/
Disclosure: I'm the author of Clipper, so there's the potential for a personal bias.