How to merge adjacent polygons

Question

I'm using a Javascript implementation of Fortune's algorithm to compute voronoi cells (https://github.com/gorhill/Javascript-Voronoi). My sites to compute are points on a map (so (lat,lng)). I first made the projection (lat,lng) -> (x,y), I then computed the voronoi cells and made the projection of the half edges the other way.
It works fine, I display the result using leaflet but I need to do one more thing.

Each site I initially compute depends of an ID, I reclassify the voronoi cells by ID and I end up, for each ID with a standard data structure looking like this :

{
  "type": "FeatureCollection",
  "features": [
    {
      "type": "Feature",
      "geometry": {
        "type": "Polygon",
        "coordinates": [[
          [9.994812, 53.549487],
          [10.046997, 53.598209],
          [10.117721, 53.531737],
          [9.994812, 53.549487]
        ]]
      }
    }, {
      "type": "Feature",
      "geometry": {
        "type": "Polygon",
        "coordinates": [[
          [10.000991, 53.50418],
          [10.03807, 53.562539],
          [9.926834, 53.551731],
          [10.000991, 53.50418]
        ]]
      }
    }
  ]
};

A set of polygons (made form the half edge of the voronoi cells) for a given ID.

I need to merge those polygons by ID, I intended to use turf.merge(), but I have topology errors

 turf.min.js:13 Uncaught TopologyError: side location conflict

Based on this post (http://lists.refractions.net/pipermail/jts-devel/2009-March/002939.html), I've tried to round the (lat,lng) couple from 10^-14 to 10^-7 but it didn't really worked. Before looking for the kinks and trying to remove them, I printed some data sample and I'm know asking myself if I used the good data from Fortune's algorithm. When I display all the polygons for all IDs, I have the right diagram, but when I display all the polygons for one ID or some polygons for one ID I end up with incomplete diagrams :

Part of the full diagram

Part of the diagram for one ID

Two "polygons" for a given ID

Does anyone has an idea how to merge polygon that share at least one common vertex ? And why there is a topology error ?

Edit : The polygons are not "incomplete" (I was using polyline)

I also tried on an easier sample :

And still got the error :

Uncaught TopologyError: side location conflict [ (44.8220601, -0.5869532) ]

So it's not (or at least not only) due to kinks

I've used this library but I didn't had to merge any cells unfortunatly so cannot help you... You should try posting this question as a bug on the github repo if you manage to reproduce it in a very simple case. — dekajoo, Mar 29 '16 at 10:45
thanks, I created a bug on the github repo. I encounter the same issue with turf.union() — kwn, Mar 29 '16 at 13:58
Do you try whit d3.js? https://github.com/mbostock/d3/wiki/Geometry — cbertelegni, Mar 29 '16 at 19:10

score 2 · Accepted Answer · answered Mar 30 '16 at 09:06

Your problem appears to be occurring before the data gets to Turf. Running the GeoJSON from your GitHub issue through a GeoJSON validator reveals two errors. The first is that you only include a geometry object for each feature, and GeoJSON requires that all features also have a properties object, even if it's empty. Second, and more importantly, a valid GeoJSON polygon must be a closed loop, with identical coordinates for the first and last points. This second problem appears to be what's causing Turf to throw its error. The polygons will successfully merge once the first set of coordinates is copied to the end to close the ring.

After displaying the data on a map, it also becomes clear that your latitude and longitude are reversed. Coordinates are supposed to be lon,lat in GeoJSON, and because yours are in lat,lon, the polygons show up in the middle of the Indian Ocean. Once that is corrected, they show up in the correct place.

Here is a fiddle showing their successful merging:

http://fiddle.jshell.net/nathansnider/p7kfxvk7/

thanks for the answer, I didn't know about the closed loop. About the latitude and longitude being reversed, it's because the data are from a French institution and the standard is (lat,lon) — kwn, Mar 30 '16 at 09:14
The coordinate reversal is a pretty common problem, as `lat,lon` is the standard in most places in the world (and in Leaflet!), but since that runs counter to the mathematical convention of ordering coordinates as `x,y`, GIS software often uses `lon,lat`. — nathansnider, Mar 30 '16 at 09:22

How to merge adjacent polygons

1 Answers1