1

I am trying to implement an utility for land subdivision using leaflet and turf. I am not sure if these tools are the right ones for the task. I've got it right for most of the scenarios but sometimes I get weird results. I need to know if there is something wrong with my algorithm or the tools aren't fit.

Here's the code

import { UUID } from 'angular2-uuid';
import * as turf from '@turf/turf';

export function splitPolygonsByLines(polygons: any[], lines: any[]) {
  this.intersectingCoordinates = [];
  this.coordinateMatches = [];
  const linesWithIntersections = this.insertIntersectingCoordsInLines(lines);
  let splitPolygons = polygons.map(polygon => {
    return JSON.parse(JSON.stringify({
      id: UUID.UUID(),
      polygon
    }));
  });

  linesWithIntersections.forEach(line => {
    const newSplits = [];
    splitPolygons.forEach(split => {
      const splitResult = this.splitPolygonByLine(split.polygon, line);
      if (splitResult.length > 0) {
        newSplits.push({
          parent: split,
          children: splitResult
        });
      }
    });
    newSplits.forEach(split => {
      const parentIndex = splitPolygons.findIndex(parent => parent.id === split.parent.id);
      splitPolygons.splice(parentIndex, 1);
      // replace parent with children
      splitPolygons = [...splitPolygons.slice(0, parentIndex), ...split.children, ...splitPolygons.slice(parentIndex)];
    });
    this.splitPolygonsWithLines.push({
      line,
      splitPolygons
    });
  });
  const result = {
    polygons: splitPolygons.map(split => split.polygon),
    areas: polygons.map(polygon => ({
      polygon,
      area: turf.area(polygon)
    })),
    points: this.intersectingCoordinates
  };
  console.table(result.areas);
  return result;
}
export function splitPolygonByLine(polygon, line) {
  const result = [];
  const intersectingFeatures = turf.lineIntersect(polygon, line);
  const intersectingCoords = this.featurePointsToCoordinates(intersectingFeatures.features);
  if (intersectingCoords.length < 2 || intersectingCoords.length % 2 !== 0) {
    return []; // invalid intersection
  }
  this.intersectingCoordinates = [...this.intersectingCoordinates, ...intersectingCoords];
  const polygonInsertionResult = this.insertIntersectingCoords(polygon.coordinates[0], intersectingCoords);
  polygon.coordinates[0] = polygonInsertionResult.coords;
  const lineInsertionResult = this.insertIntersectingCoords(line.coordinates, intersectingCoords);
  line.coordinates = lineInsertionResult.coords;
  let coordIntersections = polygonInsertionResult.indexes.map(idx => ({
    coord: idx.coord,
    coordIdx: idx.sourceIndex,
    polygonIdx: idx.insertedIndex,
    lineIdx: undefined
  }));
  coordIntersections = coordIntersections.map(int => {
    int.lineIdx = lineInsertionResult.indexes
      .find(lineResult => JSON.stringify(lineResult.coord) === JSON.stringify(int.coord)).insertedIndex;
    return int;
  });
  for (let i = 0; i < coordIntersections.length; i += 2) {
    const newPolygons = this.makePolygons(polygon, coordIntersections[i], coordIntersections[coordIntersections.length - (i + 1)], line);
    if (newPolygons.length === 2) {
      newPolygons.forEach(poly => result.push({ id: UUID.UUID(), polygon: poly }));
    }
  }
  return result;
}
export function makePolygons(existingPolygon, sourceIntersection, destinationIntersection, line) {
  const lineStartIndex = sourceIntersection.lineIdx < destinationIntersection.lineIdx ?
    sourceIntersection.lineIdx : destinationIntersection.lineIdx;
  const lineEndIndex = sourceIntersection.lineIdx === lineStartIndex ? destinationIntersection.lineIdx : sourceIntersection.lineIdx;
  const lineSegment: any[] = line.coordinates.slice(lineStartIndex, lineEndIndex + 1);

  const upperCoords = existingPolygon.coordinates[0]
    .slice(sourceIntersection.polygonIdx, destinationIntersection.polygonIdx + 1);
  let lineForUpperPolygon;
  if (upperCoords.length === 0) {
    lineForUpperPolygon = JSON.parse(JSON.stringify(lineSegment));
    lineForUpperPolygon.push(lineForUpperPolygon[0]);
  } else if (JSON.stringify(upperCoords[upperCoords.length - 1]) === JSON.stringify(lineSegment[0])) {
    lineForUpperPolygon = JSON.parse(JSON.stringify(lineSegment.slice(1, lineSegment.length)));
  } else {
    lineForUpperPolygon = JSON.parse(JSON.stringify(lineSegment.reverse().slice(1, lineSegment.length)));
  }
  const upperPolygonCoords = [
    ...upperCoords,
    ...lineForUpperPolygon
  ];
  let lineForLowerPolygon;
  const lowerPolygonCoordsFirstHalf = existingPolygon.coordinates[0].slice(0, sourceIntersection.polygonIdx + 1);
  const lowerPolygonCoordsSecondHalf = existingPolygon.coordinates[0]
    .slice(destinationIntersection.polygonIdx + 1, existingPolygon.coordinates[0].length);
  if (JSON.stringify(lowerPolygonCoordsFirstHalf[lowerPolygonCoordsFirstHalf.length - 1]) === JSON.stringify(lineSegment[0])) {
    lineForLowerPolygon = lineSegment.slice(1, lineSegment.length);
  } else {
    lineForLowerPolygon = lineSegment.reverse().slice(1, lineSegment.length);
  }
  const lowerPolygonCoords = [
    ...lowerPolygonCoordsFirstHalf,
    ...lineForLowerPolygon,
    ...lowerPolygonCoordsSecondHalf
  ];
  const result = [];
  try {
    const upperPolygon = Object.assign({
      type: 'Polygon',
      coordinates: [upperPolygonCoords]
    })
    if (upperPolygon) {
      result.push(upperPolygon);
    }
  } catch (error) {
  }
  try {
    const lowerPolygon = Object.assign({
      type: 'Polygon',
      coordinates: [lowerPolygonCoords]
    });
    result.push(lowerPolygon);
  } catch (error) {

  }

  return result;
}
export function featurePointsToCoordinates(featurePoints: any[]) {
  return featurePoints.map(feature => {
    return feature.geometry.coordinates;
  });
}

export function insertIntersectingCoordsInLines(lines: any[]) {
  lines = JSON.parse(JSON.stringify(lines));
  const insertedPairs = [];
  for (let i = 0; i < lines.length; i++) {
    for (let j = 0; j < lines.length; j++) {
      if (i === j) {
        continue;
      }
      if (insertedPairs.some(pair => pair === `${j}${i}`)) {
        continue;
      }
      const intersection = turf.lineIntersect(lines[i], lines[j]);
      const intersectingPoints = this.featurePointsToCoordinates(intersection.features);
      lines[i].coordinates = this.insertIntersectingCoords(lines[i].coordinates, intersectingPoints).coords;
      lines[j].coordinates = this.insertIntersectingCoords(lines[j].coordinates, intersectingPoints).coords;
      insertedPairs.push(`${i}${j}`);
    }
  }
  return lines;
}

export function insertIntersectingCoords(coords: any[], insertingCoords: any[]) {
  const result = Object.assign({
    coords: JSON.parse(JSON.stringify(coords)),
    indexes: []
  });
  insertingCoords
    .filter(coord => !result.coords.some(pCoord => JSON.stringify(pCoord) === JSON.stringify(coord)))
    .forEach((coord, index) => {
      const coordIndex = this.findCoordIndex(coord, result.coords);
      if (coordIndex >= 0) {
        result.coords.splice(coordIndex + 1, 0, coord);
      }
    });
  insertingCoords.forEach((coord, i) => {
    const insertedIndex = result.coords.findIndex(rCoord => {
      const isFound = JSON.stringify(rCoord) === JSON.stringify(coord)
      return isFound;
    });
    if (insertedIndex >= 0) {
      result.indexes.push({
        coord,
        insertedIndex,
        sourceIndex: i
      });
    } else {
      result.indexes.push({
        coord,
        insertedIndex: result.coords.findIndex(pCoord => JSON.stringify(pCoord) === JSON.stringify(coord)),
        sourceIndex: i
      });
    }
  });
  return result;
}

export function findCoordIndex(coord, coordinates: any[]) {
  return coordinates.findIndex((co, i) => {
    const isFound = this.isTheCoordBetween(coordinates[i], coordinates[i + 1], coord);
    return isFound;
  });
}

export function isTheCoordBetween(source, destination, coord) {
  if (!source || !destination || !coord) {
    return false;
  }
  source = turf.point(source);
  destination = turf.point(destination);
  coord = turf.point(coord);
  const sourceToDestinationDistance = turf.distance(source, destination);
  const sourceToCoordDistance = turf.distance(source, coord);
  const destinationToCoordDistance = turf.distance(destination, coord);
  const sourceToCoodBearing = +turf.rhumbBearing(source, coord).toFixed(2);
  const sourceToDestinationBearing = +turf.rhumbBearing(source, destination).toFixed(2);
  const isBetween = sourceToCoodBearing === sourceToDestinationBearing &&
    sourceToDestinationDistance > sourceToCoordDistance && sourceToDestinationDistance > destinationToCoordDistance;
  return isBetween;
}

Results: (red highlighted points indicate latest subdivisions. doesn't matter).

The triangles are holes(invalid cuts).

enter image description here

A Perfect Cut.

enter image description here

before cutting enter image description here

After Cutting

enter image description here

1 Answer 1

12

Solution below is not direct answer to the question, it's just improved version of answer to similar question Splitting A polygon into multiple polygon by multiple line strings in Leaflet and turf.js, on which code in this question is based upon. It might help you with your problem.

Cutting of polygon with line is done with the help of Turf.js library. Turf.js library does not have explicit method to split polygon with line. The most convenient method for this purpose is then turf.difference(poly1, poly2), which cuts out second polygon from first. If second polygon is very thin and long rectangle (line with small 'height'), this can be used as a split method.

This is done in two steps. First step is to 'fatten' dividing line to one side, cut polygon by it and take into account split polygon(s) one the opposite side of the line. Then dividing line is 'fattened' to the other side, polygon is cut by it and split polygon(s) on opposite side is taken into account.

This way polygon of any shape can be cut with line of any shape.

Result of cut is feature collection of cut polygons, where each polygon has feature id in the form idPrefixN.M, where idPrefix is input parameter to cut function, N is number of cut side (1 or 2) and M is sequential number of polygon on relevant side.

Code of cut function:

function polygonCut(polygon, line, idPrefix) {
  const THICK_LINE_UNITS = 'kilometers';
  const THICK_LINE_WIDTH = 0.001;
  var i, j, id, intersectPoints, lineCoords, forCut, forSelect;
  var thickLineString, thickLinePolygon, clipped, polyg, intersect;
  var polyCoords = [];
  var cutPolyGeoms = [];
  var cutFeatures = [];
  var offsetLine = [];
  var retVal = null;

  if (((polygon.type != 'Polygon') && (polygon.type != 'MultiPolygon')) || (line.type != 'LineString')) {
    return retVal;
  }

  if (typeof(idPrefix) === 'undefined') {
    idPrefix = '';
  }

  intersectPoints = turf.lineIntersect(polygon, line);
  if (intersectPoints.features.length == 0) {
    return retVal;
  }

  var lineCoords = turf.getCoords(line);
  if ((turf.booleanWithin(turf.point(lineCoords[0]), polygon) ||
      (turf.booleanWithin(turf.point(lineCoords[lineCoords.length - 1]), polygon)))) {
    return retVal;
  }

  offsetLine[0] = turf.lineOffset(line, THICK_LINE_WIDTH, {units: THICK_LINE_UNITS});
  offsetLine[1] = turf.lineOffset(line, -THICK_LINE_WIDTH, {units: THICK_LINE_UNITS});

  for (i = 0; i <= 1; i++) {
    forCut = i; 
    forSelect = (i + 1) % 2; 
    polyCoords = [];
    for (j = 0; j < line.coordinates.length; j++) {
      polyCoords.push(line.coordinates[j]);
    }
     for (j = (offsetLine[forCut].geometry.coordinates.length - 1); j >= 0; j--) {
      polyCoords.push(offsetLine[forCut].geometry.coordinates[j]);
    }
    polyCoords.push(line.coordinates[0]);

    thickLineString = turf.lineString(polyCoords);
    thickLinePolygon = turf.lineToPolygon(thickLineString);
    clipped = turf.difference(polygon, thickLinePolygon);

    cutPolyGeoms = [];
    for (j = 0; j < clipped.geometry.coordinates.length; j++) {
      polyg = turf.polygon(clipped.geometry.coordinates[j]);
      intersect = turf.lineIntersect(polyg, offsetLine[forSelect]);
      if (intersect.features.length > 0) {
        cutPolyGeoms.push(polyg.geometry.coordinates);
      };
    };

    cutPolyGeoms.forEach(function (geometry, index) {
      id = idPrefix + (i + 1) + '.' +  (index + 1);
      cutFeatures.push(turf.polygon(geometry, {id: id}));
    });
  }

  if (cutFeatures.length > 0) retVal = turf.featureCollection(cutFeatures);

  return retVal;
};

Example of usage of this function is available at JSFiddle: https://jsfiddle.net/TomazicM/pwsjoa7x/. Example allows splitting of polygons multiple times with lines of any shape.

At each step (split) the following layers and arrays are updated:

  • Layer drawnPolygons contains all polygons, split and unsplit
  • Layer drawnLines contains all lines used for splitting
  • Array polygons contains all polygons that correspond to drawnPolygons layer

The main part of the code:

var osmUrl = 'http://{s}.tile.openstreetmap.org/{z}/{x}/{y}.png';
var osmAttrib = '&copy; <a href="http://openstreetmap.org/copyright">OpenStreetMap</a> contributors';
var osm = L.tileLayer(osmUrl, { maxZoom: 18, attribution: osmAttrib });
var drawnPolygons = L.featureGroup();
var drawnLines = L.featureGroup();

var map = new L.Map('map', { center: new L.LatLng(51.505, -0.04), zoom: 13 });

osm.addTo(map);
drawnPolygons.addTo(map);
drawnLines.addTo(map);

map.addControl(new L.Control.Draw({
  draw: {
    marker: false,
    circle: false,
    circlemarker: false,
    rectangle: false,
    polygon: {
      allowIntersection: true,
      showArea: true
    }
  }
}));

const cutIdPrefix = 'cut_';
var polygons = [];

function cutPolygonStyle(feature) {
  var id, color;

  id = feature.properties.id;
  if (typeof(id) !== 'undefined') {
    id = id.substring(0, (cutIdPrefix.length + 1))
  }

  if (id == cutIdPrefix + '1')
    color = 'green';
  else if (id == cutIdPrefix + '2')
    color = 'red';
  else {
    color = '#3388ff';
  }      
  return {color: color, opacity: 0.5, fillOpacity: 0.1};
}

map.on(L.Draw.Event.CREATED, function (event) {
  var drawnLayer, drawnGeoJSON, drawnGeometry, unkinked;
  var newPolygons = [];

  drawnLayer = event.layer;
  drawnGeoJSON = drawnLayer.toGeoJSON();
  drawnGeometry = turf.getGeom(drawnGeoJSON);

  if (drawnGeometry.type == 'Polygon') {
    polygons = [];
    unkinked = turf.unkinkPolygon(drawnGeometry);
    turf.geomEach(unkinked, function (geometry) {
      polygons.push(geometry);
    });
    drawnPolygons.clearLayers();
    drawnLines.clearLayers();
    drawnPolygons.addLayer(drawnLayer);
    }
  else if (drawnGeometry.type == 'LineString') {
    drawnLines.addLayer(drawnLayer);
    drawnPolygons.clearLayers();
    polygons.forEach(function (polygon, index) {
      var cutPolygon = polygonCut(polygon, drawnGeometry, cutIdPrefix);
      if (cutPolygon != null) {
        L.geoJSON(cutPolygon, {
          style: cutPolygonStyle
        }).addTo(drawnPolygons);   
        turf.geomEach(cutPolygon, function (geometry) {
          newPolygons.push(geometry);
        });
        }
      else {
        L.geoJSON(polygon).addTo(drawnPolygons);   
        newPolygons.push(polygon);
      }
    });
    polygons = newPolygons;
  };
});

Here is an example of complex polygon cut: enter image description here

3
  • 1
    Great answer. It works as expected. I already refered the previous post you mentioned but that didn't cut the polygons that were too small. But this improved algorithm does it. Commented Dec 7, 2019 at 12:22
  • If answer helped you to solve your problem, you could mark it as accepted, so it will be clear that problem was solved.
    – TomazicM
    Commented Dec 7, 2019 at 15:36
  • sorry about that. new to stack overflow Commented Dec 8, 2019 at 6:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.