Merging Adjacent Polygons

Imagine this problem:

Recently, I had the challenge of merging 2 adjacent polygons into 1 shape. This non-trivial task was a good learning experience I want to document here.

I had the need to display CALTRANS district boundaries on a map of California. However, there is no published list of boundary lat/lngs available. CALTRANS districts are simply groupings of multiple counties. For example district 11 is San Diego County and Imperial County combined and District 8 is Riverside and San Bernardino Counties combined.

The lat/lng’s of county lines are publicly available and I was able to display them just fine:

Now, in order to display the districts instead I figured I could somehow merge the polygon shapes on the common border to create 1 shape. However, after many attempts using sets and unions the difficulty of this task emerged.

I found a demo on the internet that does essentially what I want to do, except on the zip-code level. http://www.usnaviguide.com/zipunion.htm . The merging for that site is done on the server and no source is provided. However, after searching more I found a discussion board post where the author stated it is done w/ the open-source GPC library: http://www.cs.man.ac.uk/~toby/alan/software/

I was able to modify the demo program to suite my needs. The important part to is GPC_UNION which is the option to the program telling it to merge the 2 shapes.

#include <stdio.h>
#include "gpc.h"

int main(void)
{
  gpc_polygon subject, clip, result;
  FILE *sfp, *cfp, *ofp;

  sfp= fopen("subjfile", "r");
  cfp= fopen("clipfile", "r");
  gpc_read_polygon(sfp, 0, &subject);
  gpc_read_polygon(cfp, 0, &clip);

  gpc_polygon_clip(GPC_UNION, &subject, &clip, &result);

  ofp= fopen("outfile", "w");
  gpc_write_polygon(ofp, 0, &result);

  gpc_free_polygon(&subject);
  gpc_free_polygon(&clip);
  gpc_free_polygon(&result);

  fclose(sfp);
  fclose(cfp);
  fclose(ofp);
  return 0;
}

subjfile is the lat/lngs of San Diego county. The first line is the # of contours and the second is the number of verticies

1
16
	-117.477 33.506
	-117.362 33.506
	-117.2415 33.4293
	-116.0858 33.4238
	-116.1078 32.6187
	-117.1265 32.5366
	-117.1703 32.6735
	-117.247 32.668
	-117.2798 32.8378
	-117.2524 32.898
	-117.3291 33.1226
	-117.5044 33.3362
	-117.5975 33.3855
	-117.5811 33.4512
	-117.5099 33.4676
	-117.5099 33.506

Imperial County:

1
16
	-114.733 33.4348
	-114.629 33.4348
	-114.7276 33.4019
	-114.7002 33.3526
	-114.733 33.3033
	-114.6728 33.2595
	-114.7057 33.0897
	-114.6618 33.035
	-114.514 33.0295
	-114.4647 32.9035
	-114.5249 32.7556
	-114.618 32.7282
	-114.7002 32.7447
	-114.7221 32.7173
	-116.1078 32.6187
	-116.0858 33.4238

And viola:

Here are the new coords:

1
29
-117.241500000000002  33.429299999999998
-116.085800000000006  33.423800000000000
-114.733000000000004  33.434800000000003
-114.629000000000005  33.434800000000003
-114.727599999999995  33.401899999999998
-114.700199999999995  33.352600000000002
-114.733000000000004  33.303300000000000
-114.672799999999995  33.259500000000003
-114.705699999999993  33.089700000000001
-114.661799999999999  33.034999999999997
-114.513999999999996  33.029499999999999
-114.464699999999993  32.903500000000001
-114.524900000000002  32.755600000000001
-114.617999999999995  32.728200000000001
-114.700199999999995  32.744700000000002
-114.722099999999998  32.717300000000002
-116.107799999999997  32.618699999999997
-117.126499999999993  32.536600000000000
-117.170299999999997  32.673499999999997
-117.247000000000000  32.667999999999999
-117.279799999999994  32.837800000000001
-117.252399999999994  32.898000000000003
-117.329099999999997  33.122599999999998
-117.504400000000004  33.336199999999998
-117.597499999999997  33.385500000000000
-117.581100000000006  33.451200000000000
-117.509900000000002  33.467599999999997
-117.509900000000002  33.506000000000000
-117.361999999999995  33.506000000000000

San Diego and Imperial Counties are merged:

In summary, combining polygons is not as simple and straightforward as it might
seem. Try it by hand…

Code is on github:

https://github.com/eggie5/poly-merge

Good analysis of the problem found here:

http://stackoverflow.com/questions/13746284/merging-multiple-adjacent-rectangles-into-one-polygon

Permalink: merging-adjacent-polygons

Tags: