logo标签列表

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

javagraphicscomputational-geometry
8
我正在尝试创建一个方法，该方法将接受两个任意节点列表，用于主题和剪切多边形，并输出以下内容之一：
a) 重叠区域的面积 b) 剪切后的多边形的节点列表，以便我可以计算面积
我找到了许多使用矩形窗口（在图形中相当标准）裁剪任意多边形的示例，但这不是我需要的。我理解它相当复杂，特别是当你有孔，凸多边形之类的时候。我唯一能做出的简化假设是任意多边形不会包含任何孔。
我对这个领域一窍不通，那么Sutherland-Hodgman算法之类的东西会起作用吗？是否已经有库可以做到这一点，或者我的最佳选择是按照Wikipedia上的伪代码实现算法呢？
感谢您的帮助！
那个算法不能正确处理凹多边形裁剪，对吧？ - thejh
是的，那是我的理解。 - ahugenerd
5个回答
5
2

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

1

听起来Weiler-Atherton是您需要的算法：

该算法要求多边形为顺时针方向且不具有自交 (自相交)。该算法可以支持孔洞（即逆时针多边形完全在其父多边形内），但需要其他算法来决定哪些多边形是孔洞。

您的多边形是否符合这些条件？我不确定具体的实现方式，但如果您的任意一个多边形是凹多边形，那么使用W-A算法比使用S-H算法更好。

1
我找到了GPC，但是Java端口似乎已经失效（链接失效）。 - ahugenerd
Java端口链接现在似乎已经恢复了：http://sourceforge.net/projects/geom-java/files/gpcj/ - mooreds
0

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

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接