Aleksander K. Asked:2020-07-12 00:00:28 +0000 UTC2020-07-12 00:00:28 +0000 UTC 2020-07-12 00:00:28 +0000 UTC 用矩形划分二维空间以找到邻居 772 有一个位于平面上的具有不相交矩形的数组。有必要以这样一种方式划分空间，即可以为任何矩形找到相邻的矩形。 应该注意哪些算法？ алгоритм 1 个回答 Voted Best Answer AnT stands with Russia 2020-07-12T00:07:15Z2020-07-12T00:07:15Z 一般解决方案：原始矩形的 Voronoi 图。Voronoi 图将为您将矩形之间的空白空间划分为区域，这些区域具有分区的边界区域对应于相邻矩形的属性。 Voronoi 图将解决任意多边形的这个问题。在您的情况下，由于您的多边形恰好是矩形，因此您可以期待一些优化。但它可能只是一个简化的图表过程。 例如，这里是一组随机的轴导向矩形的 Voronoi 图，内置于 Chebyshev 度量中 矩形 1 的 Voronoi 区域与矩形 2 的 Voronoi 区域共享边界这一事实表明矩形 1 和 2 是相邻的。邻居也是 1 和 5，因为它们的 Voronoi 区域之间有一小段公共边界。Voronoi Rectangle 4 区域与 Voronoi Rectangle 1 区域没有公共边界这一事实表明它们不是邻居。 通常在此类问题中，Voronoi 图允许您生成一组邻域的初步候选对象，并立即剔除明显的“非邻域”。然后你就可以根据你自己的更微妙的标准选择你需要的邻居了。在图中的这个例子中，这些标准尤其可以用来决定是否将矩形 1 和 5 视为邻居。
一般解决方案：原始矩形的 Voronoi 图。Voronoi 图将为您将矩形之间的空白空间划分为区域，这些区域具有分区的边界区域对应于相邻矩形的属性。
Voronoi 图将解决任意多边形的这个问题。在您的情况下，由于您的多边形恰好是矩形，因此您可以期待一些优化。但它可能只是一个简化的图表过程。
例如，这里是一组随机的轴导向矩形的 Voronoi 图，内置于 Chebyshev 度量中
矩形 1 的 Voronoi 区域与矩形 2 的 Voronoi 区域共享边界这一事实表明矩形 1 和 2 是相邻的。邻居也是 1 和 5，因为它们的 Voronoi 区域之间有一小段公共边界。Voronoi Rectangle 4 区域与 Voronoi Rectangle 1 区域没有公共边界这一事实表明它们不是邻居。
通常在此类问题中，Voronoi 图允许您生成一组邻域的初步候选对象，并立即剔除明显的“非邻域”。然后你就可以根据你自己的更微妙的标准选择你需要的邻居了。在图中的这个例子中，这些标准尤其可以用来决定是否将矩形 1 和 5 视为邻居。