如何找到两个任意多边形之间的重叠区域

Question

我正在尝试创建一个方法,它将接收两个任意节点列表,一个主题和一个剪切多边形,并输出:

a)重叠区域
b)结果(剪切)多边形的节点列表,以便我可以计算区域

我发现了许多使用矩形窗口剪切任意多边形的例子(图形中相当标准),但这不是我需要的.我知道它相当复杂,特别是当你得到洞,凸多边形等时.我可以做的唯一简化假设是任意多边形不包含任何孔.

我不是这个领域的专家,那么Sutherland-Hodgman算法会起作用吗？是否有任何已经执行此操作的库,或者我最好的选择是简单地实现维基百科上伪代码中描述的算法？

谢谢您的帮助!

Answer 1

那里有没有图书馆已经做过这个...

多边形裁剪是一项复杂的任务.除非你想花上很多个月,否则我不建议你自己动手.维基百科列出了许多剪辑库(和该列表中的IIRC只有Clipper可以在商业应用程序中免费使用):http: //en.wikipedia.org/wiki/Boolean_operations_on_polygons#External_links

ps:我承认Clipper的个人偏见,因为我是作者:)更多信息在这里:http://angusj.com/delphi/clipper.php

Answer 2

我发现使用JavaGeom库效果非常好。它集成了 GPC 的 Java 端口（不再可用）的代码，因此允许任意多边形操作。使用 SimplePolygon2D 和 Polygon2DUtils.intersection() 我能够获得所需的操作。