2

我正在寻找一种方法，最好是在 PHP 中，分析一组多边形以检测该组的外部边界。

具体来说，这是用于呈现区域的 Google Maps v3 应用程序。领土中的每个多边形都是一个邮政编码。我正在尝试仅检测和绘制领土边界。这是我要完成的工作的模型：

复杂区域边缘检测前后图像

我在解决这个问题时面临的挑战：

  1. 每个区域内的邮政编码可以（并且通常是）不连续的（参见上例中的红色和绿色区域）。
  2. 邮政编码不一定是凸的，因此凸包技术不起作用（也许我错了？）
  3. 尽管它在上图中看起来像，但顶点很少从一个 ZIP 到另一个 ZIP 真正冗余。每个纬度/经度坐标（即多边形的每个顶点）都有 10 个小数点的精度。我已经尝试并拒绝了一种舍入技术，因为它从来没有产生一个仍然类似于原始形状的干净数据集。

从积极的方面来说，这些领土一旦建立就永远不会改变。因此，此过程可以离线运行以计算和存储生成的区域多边形集。

澄清： 我的数据存储在邮政编码级别。每个邮政编码由一组或多组大型纬度/经度坐标定义。每个纬度/经度坐标定义了 Google 地图多边形中的一个顶点。与更大的地区一样，每个邮政编码可能是凸面的，也可能不是凸面的，它可能是也可能不是一个连续的多边形。较大的区域仅存储为邮政编码列表；没有为地区存储多边形数据——这是我在这里试图解决的问题。

非常感谢您提供正确方向的任何指示。

4

1 回答 1

1

听起来您有一个与哪些地区相关的邮政编码列表。每个邮政编码都有一个多边形。

如果是这种情况，那么解决方案相当简单。关键的观察/假设是边界邮政编码应该共享需要删除的边缘。如果不是这种情况，那么以下是一个有争议的问题。

对于每个地区：

创建一个以排序边缘为键的字典，它的项目是具有该边缘的多边形列表。然后遍历领土中的多边形并填写字典。这可能很棘手，因为您需要确保Edge(A,B) 与 Edge(B,A) 相同，这可以通过对边缘中的点进行排序来完成。

一旦你浏览了所有的多边形，你最终会得到一个边表，以及它们与哪个多边形相关联。将此表转换为图形，忽略两个或多个多边形中的所有边，尽管“或更多”可能是不可能的。结果应该是一个无向循环图，您应该能够使用类似于深度优先搜索的算法从图中提取领土多边形。

性能应该是 O(N)，其中 N 是边/顶点的总数。

于 2013-02-02T21:43:35.940 回答