algorithm - 什么算法可以用来检测多边形之间的间隙？

Question

使用什么算法来查找相邻多边形之间的间隙(示例图片显示 2 个相邻多边形和它们之间的阴影“间隙”)，这种操作有通用名称吗？我输入中的多边形可能有重合的顶点、线段，或者两者都有，或者都没有。多边形表示为点的有序列表。相邻多边形被定义为具有至少一个重合点或线段。

我正在使用 Go 进行开发(并且可以访问 GEOS 库)，但是任何对算法步骤或常用语言实现的引用都会有所帮助。

Answer 1

这可能不是您想要的，但这样的事情可能会完成工作。

假设您可以计算两个多边形周长之间的所有交点 p1、p2、...、pk 的列表。令 v1, v2, ..., vn 为第一个多边形的顶点，w1, w2, ..., wm 为第二个多边形的顶点。

首先，创建两个有序集合 c1 和 c2，其中 c1 依次包含 p1、p2、...、pk 和 v1、v2、...、vn(这样如果沿顺时针方向绕多边形的周长，顶点就会出现在访问顺序的列表中)，并且 c2 包含 p1, p2, ... pk 和 w1, v2, ..., vm 以相同的方式排序。

现在，在每两个相邻的 p(i%k) 和 p((i+1)%k) 之间存在一些重叠或间隙。如果这两个交点之间出现在 c1 和 c2 中的顶点相同，则这种重叠或间隙可能是退化的；在这种情况下，绘制的多边形的面积为零，可能会被丢弃。否则，我们必须查看出现在交点之间的 c1 和 c2 中的顶点是否定义了间隙或重叠。

如果我们有一种简单/廉价的方法来测试一个点是否包含在原始多边形中，只需在空间中选择一个点(例如，由一个交点和每个相邻点形成的三角形的中心) c1 和 c2 保证在空间内)并查看该点是否包含在 c1 或 c2 中(它不能在一个而不是另一个；为什么？)。如果包含该点，则您有重叠；否则，你有一个差距。

事实上，我们确实有一个简单的方法。如果我们以顺时针顺序绕过第一个多边形，那么如果上面确定的点(如此描述的三角形的中间)位于由交点和与之相邻的 c1 中的顶点形成的线段的右侧，然后是重叠；否则，这是一个差距。或者，您可以围绕 c2 中的点顺时针旋转并使用相同的规则来判断。

要查看一个点是在向量的左侧还是右侧:

取向量(例如，与 c1 或 c2 中相邻点的交点)

将向量带到候选点(例如，前面描述的三角形的中心)

计算 3 维叉积

结果向量的 z 坐标的符号给出了答案。

在这个例子中:

p1, p2, p3 ~ (3.1, 5.5), (3.3, 4), (3.8, 2)
v1, v2, v3, v4, v5 ~ (1, 0), (1, 8), (4, 4.5), (2, 3), (3.8, 2)
w1, w2, w3, w4 ~ (4, 1), (3, 5), (4, 9), (9, 5)

c1 ~ (v1, v2, p1, v3, p2, v4, p3=v5)
c2 ~ (w1, p3, p2, w2, p1, w3, w4)

pairs of points of intersection adjacent in c1:
x1 = (p1, p2), x2 = (p2, p3), x3 = (p3, p1)

pairs of points of intersection adjacent in c2:
y1 = (p3, p2), y2 = (p2, p1), y3 = (p1, p3)

triangle for x1 has vertices (p1, v3, w2), middle is
~ ((3.1+4+3)/3, (5.5+4.5+5)/3) = (3.3, 5)

vector from p1 to v3 ~ (0.9, -1)
vector from p1 to middle of triangle ~ (0.2, -0.5)

cross product of p1-v3 x middle of triangle vector:

    +0.9    -1.0    +0.0
    +0.2    -0.5    +0.0
      i       j       k

=> -0.45k

this has a negative sign, so this is an overlap

triangle for x2 has vertices (p2, v4, p3=v5), middle is
~ ((3.3+2+3.8)/3, (4+3+2)/3) = (3, 3)

vector from p2 to v4: (-1.3, -1)
vector from p2 to middle of triangle: (-0.3, -1)

cross product of p2-v4 and middle of triangle vector:

    -1.3    -1.0    +0.0
    -0.3    -1.0    +0.0
      i       j       k

=> 1.3k

this has a positive sign, so this must be a gap