Split Up Big Polygon Into Smaller Ones By Condition

Question

I have some big Polygon. Within it collection of leaflet layers (points). Every point have some numeric property. What I want is split up big Polygon into smaller ones. Every smaller polygon should contain points with ~equal (+-200 ok) sum of points properties. On the left side of my example page I added image of desirable result. Here is my simplified example with sufficient code and comments.

1. So my first step is find some start point within big Polygon. It's should be point near Polygon edge - the northernmost point for example.

   var nothernmostPoint= 0; var nothernmostLayer= 0; L.geoJSON(features, { pointToLayer: function (feature) { return L.circleMarker(feature.geometry.coordinates.reverse(), defaultPointStyle); }, onEachFeature: function (feature, layer) { if (feature.geometry.coordinates[0] > nothernmostPoint) { nothernmostPoint = feature.geometry.coordinates[0]; nothernmostLayer = feature; } } }).addTo(map);

---

2. Second step is to find next nearest point(s) to my start point.

   var geoJ = L.GeometryUtil.nClosestLayers(map, features, nothernmostLayer.geometry.coordinates, 5);

---

3. Then sum up their properties. If sum is smaller than needed I go to step 2 and repeat, if sum is satisfy condition then I draw polygon with chosen points inside it and find nearest point to my last point and repeat search for points for the next smaller polygon.

---

My current difficulty is to find nearest point(s) to my start point. For that purpose I use GeometryUtil Leaflet plugin. Red dots are points that GeometryUtil found as nearest to my start point (the green one). It's certainly not what I was expected.

What am I doing wrong?

Maybe I should use different algorithm and/or tool for that task.

If it may help - all that data I store in PostgreSQL with PostGIS extension. Maybe this can be done on database level.

Answer 1

It looks like L.GeometryUtil.nClosestLayers method in this case always returns the first five elements from features array (tested).

Since I could not quickly find the reason for this behaviour, here is one possible solution for finding first five closest points:

var i, j;
var distance;
var nearestPoint = [];

for (i = 0; (i < features.length); i++) {
  distance = map.distance(features[i].geometry.coordinates, nothernmostLayer.geometry.coordinates);
  if (distance == 0) continue;
  if (nearestPoint.length == 0) {
    nearestPoint[0] = [i, distance];
    }
  else {
    for (j = 0; (j < nearestPoint.length); j++) {
      if (distance < nearestPoint[j][1]) {
        nearestPoint.splice(j, 0, [i, distance]);
        if (nearestPoint.length > 5) {
          nearestPoint.splice(5, 1);
        };
        break;
      }
    }
  }
}

At the end array nearestPoint contains five pairs [iPoint, dist], where iPoint is index of the point in features array in dist is distance of the point.