如何检测2d多边形组内的顶点？ （例如确定领土的邮政编码） [英] How to detect interior vertices in groups of 2d polygons? (E.g. ZIP Codes to determine a territory)

问题描述

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

具体而言，这适用于Google Maps v3应用程序渲染区域。该领土内的每个多边形都是一个邮政编码。我试图只检测和绘制领土边界。以下是我想要完成的模型：

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

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

这些领土一旦建立就永远不会改变。因此，此过程可以离线运行，以计算并存储所得到的地区polysets。

澄清：
我的数据存储在邮政编码等级。每个邮政编码由一组或多组经纬度坐标定义。每个纬度/经度坐标定义Google地图多边形中的单个顶点。与较大的地区一样，每个邮政编码可能凸出也可能不凸出，它可能是也可能不是一个连续的多边形。较大的地区只是存储为一个邮政编码列表;没有多边形数据存储的区域 - 这是我想要解决的问题。

非常感谢任何指向正确方向的指针。这听起来像你有一个列表，哪些邮政编码涉及哪些领土。每个邮政编码也有一个多边形。

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

对于每个地区：

创建一个键入有序边的字典，其中的项是包含该边的多边形列表。然后穿过领土上的多边形并填写字典。这可能会很棘手，因为您需要确保边缘（A，B）与边缘（B，A）相同，这可以通过对边缘中的点进行排序来完成。

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

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

I am looking for a method, preferably in PHP, to analyze a group of polygons to detect the outer boundaries of the group.

Specifically, this is for a Google Maps v3 application that renders territories. Each polygon in the territory is a ZIP Code. I'm trying to detect and draw only the territory boundary. Here's a mock-up of what I'm trying to accomplish:

The challenges I face in solving this problem:

1. ZIP Codes within each territory can be (and often are) non-contiguous (see the red and green territories in the example above).
2. ZIP Codes are not necessarily convex, so a convex hull technique wouldn't work (maybe I'm wrong?)
3. Although it looks like it in the image above, vertices are rarely truly redundant from one ZIP to another. Each lat/lon coordinate (i.e. each vertex of the polygon) has 10 decimal points of precision. I have already tried and rejected a rounding technique as it never produced a clean data set that still resembled the original shape.

On the positive side, these territories never change once they're established. Therefore, this process can be run offline to calculate and store the resulting territory polysets.

Clarification: My data is stored at the ZIP Code level. Each ZIP Code is defined by one or more large sets of lat/lon coordinates. Each lat/lon coordinate defines a single vertex in the Google Maps polygon. As with the bigger territories, each ZIP Code may or may not be convex, and it may or may not be a single contiguous polygon. The larger territory is simply stored as a list of ZIP Codes; no polygonal data is stored for territories--which is the problem I'm trying to solve here.

Many thanks in advance for any pointers in the right direction.

解决方案

It sounds like you have a list of which zip codes relate to which territories. You also have a polygon for each zip code.

If this is the case, then the solution is fairly straightforward. The key observation/assumption is that bordering zip codes should share edges, which need to be removed. If this isn't the case, then the following is a moot point.

For each territory:

Create a dictionary that is keyed to the sorted edge, and which it's item is a list of polygons with that edge. Then go through the polygons in the territory and fill out the dictionary. This may be tricky as you need to ensure that Edge(A,B) is the same as Edge(B,A), which could be done by sorting the points in the edge.

Once you've gone through all of the polygons, you'll end up with essentially a table of edges and which polygon they are associated with. Convert this table into a graph, ignoring all edges that are in two or more polygons, although the "or more" is probably not possible. The result should be an undirected cyclic graph, that you should be able to extract the territory polygon from the graph using an algorithm similar to depth-first search.

The performance should be O(N), where N is the total number of edges/vertices.

这篇关于如何检测2d多边形组内的顶点？ （例如确定领土的邮政编码）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！