geometry - 查找多边形之间的共享顶点

Question

我很快就会遇到一个有趣的问题，我已经开始考虑算法了。我越想越害怕，因为我认为它会扩展得非常可怕 (O(n^4))，除非我能变聪明。我很难理解这个。这是问题的简化描述。

我有 N 个多边形(其中 N 可以大于 10,000,000)，它们存储为 M 个顶点的列表(其中 M 大约为 100)。我需要做的是为每个多边形创建一个在其他多边形之间共享的任何顶点的列表(将多边形视为周围感兴趣的区域，有时是区域但彼此相对)。我看到了这样的东西

Polygon i | Vertex | Polygon j | Vertex
   1          1         2          2
   1          2         2          3
   1          5         3          1
   1          6         3          2
   1          7         3          3

这意味着多边形 1 中的顶点 1 与多边形 2 中的顶点 2 相同，多边形 1 中的顶点 2 与多边形 2 中的顶点 3 相同。同样，多边形 1 中的顶点 5 与顶点相同1 在多边形 3....

为简单起见，我们可以假设多边形从不重叠，它们最接近的是在边缘接触，并且所有顶点都是整数(以便于测试相等性)。

我现在唯一能做的就是对于每个多边形，我必须遍历所有的多边形和顶点，给我一个 O(N^2*M^2) 的缩放比例，这在我的情况。我可以拥有非常大的多边形文件，所以我什至不能将它们全部存储在 RAM 中，所以这意味着要多次读取文件。

这是我到目前为止的伪代码

for i=1 to N
  Pi=Polygon(i)
  for j = i+1 to N
    Pj=Polygon(j)
    for ii=1 to Pi.VertexCount()
      Vi=Pi.Vertex(ii)
      for jj=1 to Pj.VertexCount()
        Vj=Pj.Vertex(jj)
        if (Vi==Vj) AddToList(i,ii,j,jj)
      end for
    end for
  end for
end for

我假设这已经出现在图形社区中(我在那里花的时间不多，所以我不了解相关文献)。有任何想法吗？

Answer 1

这是一个经典的迭代与内存问题。如果您将每个多边形与其他所有多边形进行比较，您将遇到 O(n^2) 解决方案。如果您在遍历所有多边形时构建一个表，然后再遍历该表，您将获得一个不错的 O(2n) 解决方案。我在采访中也问过类似的问题。

假设您有可用内存，您想要创建一个多图(一个键，多个条目)，每个顶点作为键，多边形作为条目。然后您可以只走一次每个多边形，将顶点和多边形插入到 map 中。如果顶点已经存在，则将多边形添加为该顶点键的附加条目。

一旦你击中了所有的多边形，你就可以遍历整个 map 一次，并对具有多个多边形条目的任何顶点做任何你需要做的事情。