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

有志者，事竟成！如果你在学习Golang，那么本文《什么算法可以用来检测多边形之间的间隙？》，就很适合你！文章讲解的知识点主要包括，若是你对本文感兴趣，或者是想搞懂其中某个知识点，就请你继续往下看吧~

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

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

解决方案

这可能不是您想要的，但类似的东西可能会完成工作。

假设您可以计算两个多边形周长之间所有交点 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 中的点顺时针旋转并使用相同的规则来判断。

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

1. 获取向量（例如，c1 或 c2 中相邻点的交点）

2. 将向量带到候选点（例如前面描述的三角形的中心）

3. 计算 3 维叉积

4. 结果向量的 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

终于介绍完啦！小伙伴们，这篇关于《什么算法可以用来检测多边形之间的间隙？》的介绍应该让你收获多多了吧！欢迎大家收藏或分享给更多需要学习的朋友吧~golang学习网公众号也会发布Golang相关知识，快来关注吧！