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: