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).
A Perfect Cut.
before cutting
After Cutting
Best Answer
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
idin the formidPrefixN.M, whereidPrefixis input parameter to cut function,Nis number of cut side (1 or 2) andMis sequential number of polygon on relevant side.Code of cut function:
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:
drawnPolygonscontains all polygons, split and unsplitdrawnLinescontains all lines used for splittingpolygonscontains all polygons that correspond to drawnPolygons layerThe main part of the code:
Here is an example of complex polygon cut: