如何找到两个任意多边形

Question

我试图创建将在节点的任意两个列表的方法，对主题和裁剪多边形和输出要么之间的重叠区域：

一个）重叠
b）对于所得到的（限幅）的多边形，使我可以计算面积节点的列表的区域

我发现许多实例，其夹使用矩形的任意多边形窗口（这是相当标准的图形），但这不是我所需要的。我知道这很复杂，特别是当你有洞，凸多边形等等。我可以做出的唯一简化假设是任意多边形不会包含任何空洞。

我不是这方面的专家，所以像Sutherland-Hodgman算法的工作？是否有任何图书馆已经这样做，或者是我最好的办法是简单地实现Wikipedia上的伪代码中描述的算法？

感谢您的帮助！

Answer 1

我发现使用JavaGeom库工作得很好。它集成了来自GPC的Java端口（不再可用）的代码，因此允许任意多边形操作。使用SimplePolygon2D和Polygon2DUtils.intersection（）我能够得到所需的操作。

Answer 2

是否有任何图书馆那里它已经做到这一点...

多边形裁剪是一项复杂的任务。我不会推荐你自己去做，除非你想花很多个月。 维基百科列出了一些剪辑库（和IIRC该列表中只有快船是免费的，在商业应用）： http://en.wikipedia.org/wiki/Boolean_operations_on_polygons#External_links

PS：我承认我个人偏向于快船，因为我是作者:) 这里更多的信息：http://angusj.com/delphi/clipper.php

Answer 3

听起来Weiler-Atherton是一个你需要的：

该算法要求多边形是 顺时针也不能重入（个体经营 相交） 。该算法可以支持孔（逆时针方向 多边形完全位于其父 多边形内），但需要额外的 算法才能决定哪些多边形 是空洞。

你的多边形符合这些标准，对吗？ 我不知道有关实现，但是如果你的多边形中的任何一个都可能是凹形的，那么你觉得实现W-A会比S-H更好。

Answer 4

尝试gpc。

Answer 5

我试了很多不同的库，最好的工作是JTS Topological Suite，它是纯Java和LGPL2许可的。