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:

<img src="https://i.stack.imgur.com/q2rYN.jpg" alt="Before and After images of complex territory edge detection">

The challenges I face in solving this problem:

<ol> <li>ZIP Codes within each territory can be (and often are) non-contiguous (see the red and green territories in the example above).</li> <li>ZIP Codes are not necessarily convex, so a convex hull technique wouldn't work (maybe I'm wrong?)</li> <li>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.</li> </ol>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.

<strong>Clarification:</strong> 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.

### Answer1:

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.