如何找到两个任意多边形之间的重叠区域
我正在尝试创建一种方法，该方法将接受两个任意节点列表（用于主题和剪切多边形），并输出：
a) 重叠面积
b）生成的（剪切的）多边形的节点列表，以便我可以计算面积
我发现了很多使用矩形窗口（这在图形中相当标准）剪切任意多边形的示例，但这不是我需要的。我知道它相当复杂，特别是当你遇到孔、凸多边形等时。我可以做出的唯一简化假设是任意多边形不会包含任何孔。
我根本不是这个领域的专家，那么像 Sutherland-Hodgman 算法这样的算法行得通吗？是否有任何库已经做到了这一点，或者我最好的选择是简单地实现 维基百科？
感谢您的帮助！
I'm trying to create a method that will take in two arbitrary lists of nodes, for a subject and a clipping polygon, and output either:
a) the area of the overlap
b) a list of nodes for the resulting (clipped) polygon so that I can calculate the area
I've found lots of examples which clip an arbitrary polygon using a rectangular window (which is fairly standard in graphics) but that's not what I need. I understand that it's fairly complex, particularly when you get holes, convex polygons and the like. The only simplifying assumption which I can make is that the arbitrary polygons will not contain any holes.
I'm not at all an expert in this field, so would something like the Sutherland-Hodgman algorithm work? Are there any libraries out there which already do this, or is my best bet to simply implement the algorithm as described in pseudo-code on Wikipedia?
Thanks for the help!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
多边形裁剪是一项复杂的任务。我不建议您尝试自己做，除非您想花几个月的时间。
维基百科列出了许多剪辑库（IIRC 在该列表中只有 Clipper 可以免费用于商业应用程序）：
http://en.wikipedia.org/wiki/Boolean_operations_on_polygons#External_links
ps：我承认由于我是作者，因此对 Clipper 有个人偏见:)
更多信息请参见：http://angusj.com/delphi/clipper.php
Polygon clipping is a complex task. I wouldn't recommend trying to do it yourself unless you want to spend many months on it.
Wikipedia lists a number of clipping libraries (and IIRC in that list only Clipper is free for use in commercial applications):
http://en.wikipedia.org/wiki/Boolean_operations_on_polygons#External_links
ps: I admit to a personal bias for Clipper since I'm the author :)
More info here: http://angusj.com/delphi/clipper.php
我发现使用 JavaGeom 库效果很好。它集成了 GPC 的 Java 端口（不再可用）的代码，因此允许任意多边形操作。使用 SimplePolygon2D 和 Polygon2DUtils.intersection() 我能够获得所需的操作。
I found that using the JavaGeom library worked very well. It integrates the code from the Java port of GPC (which is no longer available) and thus allows arbitrary polygon operations. Using SimplePolygon2D and Polygon2DUtils.intersection() I was able to get the desired operation.
听起来 Weiler-Atherton 就是您需要的：
你的多边形符合这些标准，对吗？
我不知道实现，但听起来如果你的任何一个多边形可以是凹的，那么你最好实现 WA 而不是 SH。
Sounds like Weiler-Atherton is the one you need:
Your polygons fit those criteria, right?
I don't know about implementations, but it sounds like you would be better off implementing W-A than S-H if either of your polygons could be concave.
尝试gpc。
Try gpc.
我尝试了很多不同的库，效果最好的一个是 JTS 拓扑套件这是纯 Java 和 LGPL2 许可的。
I've tried a lot of different libraries and the one that worked best was the JTS Topological Suite which is pure Java and LGPL2 licensed.