两个多边形之间的重叠检查

Question

我有一个使用HTML5画布（GWT）的两个多边形形状绘制。我有两个多边形形状的所有点。意味着我有绘制这种类型的多边形的点列表。

下图显示两个多边形相互交叉或重叠。现在我正在寻找一个解决方案如何使用java找到两个“相交或不相交”多边形？我使用纯Java编程而不使用任何第三个库。

我有另外一个问题。为了解释这个问题，我在下面附上另一张图片。

这是另一种情况下，当另一多边形的内部的一个多边形。在这种情况下如何计算两个多边形之间的最小距离为负？

Answer 1

使用Postgis Api使用您可以获得两个多边形相交或不相交的信息。查找以下链接作为参考 http://www.postgis.net/docs/ST_Intersection.html

Answer 2

您可以使用sweepline范例。

考虑水平线穿过任一多边形的顶点。连续两行切出厚片（梯形）。

由于板坯是简单的，凸多边形，检查它们交集是直接的：它足以检测碱基（在那里它们形成X横介意的情况下）的重叠。

现在整个过程可以分解为

• 通过增加坐标排序两个多边形的顶点;对于每个顶点，请记住它属于哪个多边形，以及它的邻居有多少个纵坐标（无，一个或两个）;

• 通过增加纵坐标，同时保持相交边缘的列表扫描顶点（它被称为活动列表）。每次移动到另一个顶点时，更新活动列表;

• 相交测试的板坯。