How to detect interior vertices in groups of 2d polygons? (E.g. ZIP Codes to determine a territory)

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.


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.


  • Listing cities from coordinates in R
  • Union of circles and polygon in leaflet
  • Render face of cube map to a quad
  • What is the “center” of a Three.js object?
  • Only white color with zoom control shown in google-maps div area
  • Can i detect if a user canceled navigation from Google Maps App
  • How to setCenter mapview with location in google maps sdk for iOS
  • Cycles in Gremlin/Cypher
  • Boost Graph : Test if two vertices are adjacent
  • How to increase the python speed over loops?
  • How to merge all results of AQL into single document with custom properties
  • What's the point of nonfinal singleton objects in scala?
  • plotting spatial points over a raster layer in r
  • preg_replace speed optimisation
  • Hatch area using pcolormesh in Basemap
  • Getting coordinates of a component in java
  • Broadcast advanced indexing numpy
  • Storing a copy of a document embedded in another document in MongoDB via Mongoose
  • How are 32 bit JavaScript numbers resulting from a bit-wise operation converted back to 64 bit numbe
  • Fraction length
  • Jooq casting String to BigDecimal
  • Flex/AS3 very strange simple Number operation issue
  • Insert records if not exist SQL Server 2005
  • OpenGL - Object Transformations and VBOs
  • How to draw a line dynamically in android [duplicate]
  • Google Places API - Find a company's CID and LRD
  • Update Google Maps traffic layer without page reloading
  • Azure table store snapshot/backup capability
  • Android Studio Can't Find tools.jar
  • Convert Type Decimal to Hex (string) in .NET 3.5
  • Regex thinks I'm nesting, but I'm not
  • How reduce the height of an mschart by breaking up the y-axis
  • Deserializing XML into class C#
  • Large data - storage and query
  • R: gsub and capture
  • jqPlot EnhancedLegendRenderer plugin does not toggle series for Pie charts
  • Traverse Array and Display in markup
  • Comma separated Values
  • Buffer size for converting unsigned long to string
  • How to load view controller without button in storyboard?