The following is reprinted from Totoro’s article “Geometric Computation – Implementing The Splitting and Merging of polygons based on Turf.js”

Author: totoro

Link: blog.totoroxiao.com/geo-polygon…

Source: blog.totoroxiao.com/

Copyright belongs to the author. Commercial reprint please contact the author for authorization, non-commercial reprint please indicate the source.

JavaScript API GL recently implemented a geometry editor to support the logistics industry. Users can draw and edit points, lines, planes and circles through the editor interface. In the logistics industry, the common application scenario is the drawing of distribution area and geographical fence. It is often necessary to split or merge existing areas, so the editor also provides corresponding functions. This article introduces how to achieve polygon splitting and merging based on Turf.

background

Polygon splitting and merging

Polygon splitting refers to dividing polygons into several polygons along a line. As shown in the figure below, not only can the polygon be divided into two parts along the line, but it can also be divided into multiple parts when the polygon has multiple sections intersecting it, and when the polygon has holes (ring polygons), the shape of the holes can be kept after splitting.

Polygon combination refers to the combination of multiple polygons into one polygon, the prerequisite of which is that there are cross regions or common sides between polygons. As shown in the figure below, both fully common and partially common edges can be merged, and the intersecting parts will be transfixed when there are intersects.

Turf.js

It is not difficult to find that there will be a lot of complicated geometric calculation in polygon splitting and merging, including the calculation of intersection and inclusion among points, lines and planes. We don’t need to build wheels though, and can use Turf.js to do most of the basic calculations. Turf is calculated by the mapbox launch of the space geometry, library, used in the geometrical relationship analysis of geographical space, function is very powerful, specific function visible Turf. Js | Advanced geospatial analysis.

However, Turf-js does not provide the method of polygon splitting at present. In addition, although the union method has been used for polygon merging, it cannot solve the problem of polygon merging with some common sides well in practical application, so it can only realize the splitting and merging function that meets the business requirements on the basis of Turf.

Polygon splitting

Foundation scheme

The core idea of polygon splitting is to find the cutting point, so the cutting across the line can be simplified to the line to line cutting. Two lines cut each other to obtain subline segments, which are combined to form polygons.

As shown in the figure above, the polygon to be split is marked as polygon and the broken line to be cut is marked as splitter. The separation steps are as follows:

  • Polygon to line: Polygon unwinds from the starting point to form a polyline pline with paths [P0, P1, P2, p3, P0]
  • Lines cut each other: Turf provides a lineSplit method that splits a broken line into sections using points or lines. Using this method, the pline and splitter can be cut into each other to obtain the pieceCollection
  • Line combinations are polygons: Turf provides a polygonize method, where a set of broken lines are joined together to form polygons. Using this method, pieceCollection can be combined into multiple polygon splitedcollections

This scheme seems feasible, but it has the following problems:

  • The cut points obtained by pline and Splitter are inconsistent, resulting in the inability of Polygonize to splice them together
  • The part of the cut line outside the polygon will form the outer polygon, as shown below

Solve the problem of inconsistent cut points

The problem with the inconsistency of the first cut point mentioned above is that the cut point obtained by using line A tangent B is different from that obtained by using line B tangent A.

See how The Turf source code implements lineSplit:

functionlineSplit(line, splitter) { ... var lineType = getType(line); var splitterType = getType(splitter); . // remove excessive decimals from splitter // to avoid possible approximation issuesin rbush
    var truncatedSplitter = truncate(splitter, {precision: 7});

    switch (splitterType) {
    case 'Point':
        return splitLineWithPoint(line, truncatedSplitter);
    case 'MultiPoint':
        return splitLineWithPoints(line, truncatedSplitter);
    case 'LineString':
    case 'MultiLineString':
    case 'Polygon':
    case 'MultiPolygon':
        returnsplitLineWithPoints(line, lineIntersect(line, truncatedSplitter)); }}Copy the code

Truncate method in the code is used to retain the decimal of the specified number of digits, that is, splitter is limited in accuracy, so the coordinate points in the actual calculation will change after pline and Splitter exchange positions, resulting in inconsistent problems.

How to ensure that the two are consistent? It can be found that when line B is used to cut line A, in fact, the intersection points of line B and line A are calculated first, and then the splitLineWithPoints method is used to cut line A with these intersection points. Then calculate the intersection of the two lines first, and then use the intersection point to cut the two lines respectively, so as to ensure the consistency of the cutting point. The implementation method is as follows:

// truncate
let truncatedSplitter = truncate(splitter, {precision: 7});

// compute intersects of two lines
let intersectCollection = lineIntersect(outerLine, truncatedSplitter);
if (intersectCollection.features.length < 2) {
	return null;
}

// transform FeatureCollection[Point] to Feature[MultiPoint]
let intersectCombined = combine(intersectCollection).features[0];

// split lines with points
let outerPieceCollection = lineSplit(outerLine, intersectCombined);
let splitterPieceCollection = lineSplit(truncatedSplitter, intersectCombined);

// polygonize pieces
let pieceCollection = featureCollection(outerPieceCollection.features.concat(splitterPieceCollection.features));
let polygonCollection = polygonize(pieceCollection);
Copy the code

Solve external polygon problems

In simple terms, it is only necessary to screen out the small polygons inside the original large polygon. Turf provides booleanContains, booleanDisjoint, booleanWithin and other methods for determining the position relationship between points, lines and surfaces. However, because some vertices of small polygons are calculated on the edge of the original polygon, and the accuracy is limited, the position relationship is very delicate, and it may fall inside and outside the polygon during calculation, so the misjudgment rate is very high.

However, the centroid of a polygon does not have this problem. In the current scenario, we do not need to determine whether every vertex of a small polygon falls inside the original polygon, as long as the centroid falls inside the original polygon.

The implementation is as follows:

// filter polygons in outer poly
let innerPolygons = polygonCollection.features.filter(polygon => {
	let center = centroid(polygon);
	return booleanWithin(center, outerPolygon);
});
Copy the code

Splitting of ring polygons

A ring polygon is a polygon with a “hole” inside. There are two cases when it is split. One is if the split line passes through the hole, then the hole becomes an outer contour; the other is if the split line does not pass through the hole, then the hole remains. However, this way of thinking easily leads us to split the hole and then splice it with the spliced fragment of the outer ring.

It’s even easier to use the hole as a mask. In other words, only the outer ring polygons are split, and the small polygons are masked after the split. As shown in the figure below.

let diffedPolygons = innerPolygons.map(polygon => {
	let diff = polygon;
	featureEach(holeCollection, (hole) => {
		diff = difference(diff, hole);
	});

	return diff;
});
Copy the code

This can complete the polygon split function.

Polygon combination

turf.union

Turf provides a union method for merging intersecting polygons, which can handle fully co-edged, partially capped, contained cases, as well as ring polygons. However, there is still the problem that there is no tolerance in the judgment of the relation between point and line when dealing with partial common polygon, which leads to the point being judged out of line and unable to merge completely.

Here is a brief introduction to the calculation method to judge the relationship between point and line segment. P is used to represent point, S0 and S1 form a line segment. Then, the cross product of vector P-s0 and s1-s0 (the cross product represents the area of the parallelogram it forms) is judged to be 0, and then whether P is between S0 and S1. The problem lies in whether the cross product is 0 or not. Since point coordinates are high-precision floating point numbers, it is difficult for the cross product to be strictly equal to 0, so a small tolerance limit is generally set. As long as the absolute value of the cross product is less than the tolerance limit, the point can be judged to be on the line.

The combination of partial cosided polygons

The cause of the failed merge has been located, but there is no way to modify the union source directly because Turf also uses an external library, Martinez-polygon-Clipping, on the Union implementation. However, it is possible to change the way of thinking and convert the situation of partially common edges to fully common edges, and then hand over the union to merge. This conversion process IS called point injection. The vertices of polygon B are injected into polygon A, that is, the vertices of polygon B are traversed to judge, and if they are on A line segment of A and not at the end of the line segment, they are inserted into the path of A. When A and B inject vertices into each other, the edges of all partially common edges become completely common.

* @param {Feature[LineString]} line * @param {FeatureCollection} pointCollection */function injectPointsOnSide(line, pointCollection) {
	let coords = getCoords(line);
	featureEach(pointCollection, (point, index) => {
		let isOnLine = isPointOnLine(point, line, {
			ignoreVertices: true
		});
		if(isOnLine.bool) { coords.splice(isOnLine.index + 1, 0, getCoord(point)); }}); }Copy the code

This can complete the polygon merge function.

Product promotion

The graphics editor implemented on JSAPI GL integrates the functions of drawing, editing and deleting geometric figures, which is more perfect and easy to use compared with JSAPI V2. This function has been online website, welcome to use ~ JavaScript API GL | tencent location service

Note: GIF image is blurry and flickering, does not represent the real effect.