mapbox / polylabel

A fast algorithm for finding the pole of inaccessibility of a polygon (in JavaScript and C++)
Other
1.44k stars 151 forks source link

MultiPolygon #54

Open paomedia opened 5 years ago

paomedia commented 5 years ago

(enhancement)

As the GeoJSON format is concerned, I figure it out that "type":"MultiPolygon" is not supported. I suppose this would take an other kind of algorithm (idk?). Anyway, thanks for sharing !

jradasaurus commented 4 years ago

I figured this out the hard way too... the process would run out of memory and I noticed a pattern that all the ones that failed had multiple polygons. So I added a condition to my program to check if (obj.geometry.coordinates.length === 1) { and in my case I can ignore those... best effort :)

HarryStevens commented 4 years ago

If the GeoJSON feature is of type "Polygon", you can just pass the coordinates to polylabel. If it's "MultiPolygon", you can loop through the coordinates array to find the polygon with the largest area, and then pass that to polylabel. I do it like this, using d3.geoArea to calculate the areas:

function findPolylabel(feature){
  let output = [];
  if (feature.geometry.type === "Polygon"){
    output = polylabel(feature.geometry.coordinates);
  }
  else {
    let maxArea = 0, maxPolygon = [];
    for (let i = 0, l = feature.geometry.coordinates.length; i < l; i++){
      const p = feature.geometry.coordinates[i];
      const area = d3.geoArea({type: "Polygon", coordinates: p})
      if (area > maxArea){
        maxPolygon = p;
        maxArea = area;
      }
    }
    output = polylabel(maxPolygon);
  }
  return output;
}
hollasch commented 3 years ago

In my implementation, I plan to loop through all polygons, finding the most-interior point of all, and choosing the point with the greatest interior room as the winner.

xeruf commented 2 years ago

That algorithm has to be out there somewhere though, as MultiPolygons are successfully handled by the default OSM Mapnik style labels.