以下內容轉載自totoro的文章《幾何計算-基于Turf.js實現(xiàn)多邊形的拆分及合并》

作者：totoro

鏈接：https://blog.totoroxiao.com/geo-polygon-split-union/

來源：https://blog.totoroxiao.com/

著作權歸作者所有。商業(yè)轉載請聯(lián)系作者獲得授權，非商業(yè)轉載請注明出處。

JavaScript API GL近期為支持物流行業(yè)實現(xiàn)了幾何圖形編輯器，用戶可通過編輯器接口進行點、線、面、圓的繪制和編輯。在物流行業(yè)中常見的使用場景是配送區(qū)域及地理圍欄的繪制，常會有對已有區(qū)域進行拆分或者合并的需要，所以編輯器也提供了相應的功能。本文介紹了如何基于Turf實現(xiàn)多邊形的拆分及合并。

背景介紹

多邊形的拆分合并

多邊形的拆分是指將多邊形沿著線切分為幾個多邊形。如下圖所示，不僅可以沿線一分為二，當線與多邊形有多段相交時也可以分為多份，另外當多邊形帶洞（環(huán)多邊形）時也可以在拆分后保持洞的形狀。

image

多邊形的合并是指將多個多邊形合并為一個多邊形，其前提條件是多邊形之間有交叉區(qū)域或者共邊。如下圖所示，完全共邊或者部分共邊都可以合并，當有交叉時會貫通交叉部分。

image

Turf.js

不難發(fā)現(xiàn)，多邊形的拆分合并中會有大量且復雜的幾何計算，包括點、線、面相互之間的相交、包含等計算。不過我們并不需要造輪子，可以使用Turf.js完成大部分的基礎計算。Turf是由mapbox推出的空間幾何計算庫，常用于地理空間內的幾何關系分析，功能非常強大，具體功能可見Turf.js | Advanced geospatial analysis。

可是Turf.js目前還沒有提供多邊形的拆分方法，另外多邊形的合并雖然已有union方法，但在實際應用中也無法很好解決部分共邊的多邊形的合并問題，所以只能在Turf的基礎上自行實現(xiàn)符合業(yè)務需求的拆分合并功能。

多邊形的拆分

基礎方案

多邊形拆分的核心思想是找到切割點，所以線對面的切割可以簡化為線對線的切割。兩條線互相切割得到子線段，將子線段互相組合形成多邊形。

image

如上圖所示，待拆分的多邊形記為polygon，切割折線記為splitter。拆分步驟如下：

• 面化為線：polygon從起點解開可以形成路徑為[p0, p1, p2, p3, p0]的折線pline
• 線互相切割：Turf提供了lineSplit方法，可以使用點或者線將一條折線切分為幾部分。利用該方法可以將pline與splitter互相切割，得到子線段集合pieceCollection
• 線組合為多邊形：Turf提供了polygonize方法，將一組折線互相拼接組合成多邊形。利用該方法可以將pieceCollection組合成多個多邊形splitedCollection

這方案看似可行，實則有以下問題：

• pline與splitter互相切割后得到的切割點不一致，導致polygonize無法將其拼接在一起

• 切割線在多邊形外的部分會形成外部多邊形，如下圖所示

  
  
  image

解決切割點不一致問題

上文所述第一個切割點不一致的問題是指，使用線A切線B得到的切割點與使用線B切線A得到的切割點不同。

可以看看Turf的源碼是如何實現(xiàn)lineSplit的：

function lineSplit(line, splitter) {
    ...

    var lineType = getType(line);
    var splitterType = getType(splitter);

    ...

    // remove excessive decimals from splitter
    // to avoid possible approximation issues in 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':
        return splitLineWithPoints(line, lineIntersect(line, truncatedSplitter));
    }
}

代碼中truncate方法是用于保留指定位數(shù)的小數(shù)，即splitter被限制了精度，所以pline和splitter交換位置后實際計算中的坐標點就發(fā)生了變化，導致了不一致的問題。

如何保證兩者一致？可以發(fā)現(xiàn)用線B切線A時，實際上是先計算線B與線A的交點，再使用splitLineWithPoints方法用這些交點對線A進行切割。那么先計算好兩條線的交點，再用交點分別對兩條線進行切割，就可以保證切割點的一致了。實現(xiàn)方法如下：

// 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);

解決外部多邊形問題

簡單來說只要能篩選出在原大多邊形內部的小多邊形就好了，Turf提供了booleanContains、booleanDisjoint、booleanWithin等方法用于判斷點、線、面的位置關系。但是由于小多邊形的部分頂點是在原多邊形的邊線上計算出來的，且精度有限，位置關系非常微妙，計算時其落在多邊形內外都有可能，所以誤判率極高。

但是多邊形的形心就沒有這個問題了，在當前的場景下，我們無需判斷小多邊形的每個頂點是否都落在原多邊形內，只要其形心落在原多邊形內即可。

image

實現(xiàn)如下：

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

環(huán)多邊形的拆分

環(huán)多邊形是指內部帶“洞”的多邊形，其拆分時有兩種情況，一是拆分線穿過了洞，那么洞就變成了外輪廓，二是拆分線沒有穿過洞，那么洞還整個保留。但是這樣的思考方式容易引導我們去將洞也進行拆分，然后再與外環(huán)拆分后的片段進行拼接。

還能有更簡單的做法，將洞作為遮罩。即在拆分時只對外環(huán)多邊形進行拆分，在拆分完成之后對小多邊形進行遮罩剔除。如下圖所示。

image

遮罩的剔除可以使用Turf的difference方法，具體實現(xiàn)如下：

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

    return diff;
});

至此即可完成多邊形的拆分功能啦。

多邊形的合并

turf.union

Turf提供union方法可以對有交集的多邊形進行合并，可以處理完全共邊、部分壓蓋、包含的情況，環(huán)多邊形也是可以處理的。但是在處理部分共邊的多邊形時，仍然存在點、線關系判定沒有容限的問題，導致點被判定在線外而無法完全合并。

這里先簡單介紹一下判斷點、線段關系的計算方法，用P表示點，S0和S1兩點構成線段，那么首先判斷向量P-S0和S1-S0的叉積（叉積表示其構成平行四邊形的面積）是否為0，然后判斷P是否在S0、S1兩點之間。問題就出在叉積是否為0這一步，由于點坐標都是高精度浮點數(shù)，叉積很難嚴格等于0，一般會設定一個較小容限值，只要叉積絕對值小于容限值即可判定為點在線上。

image

部分共邊多邊形的合并

已定位合并失敗的原因，但是沒辦法直接修改union的源碼，因為Turf在union的實現(xiàn)上其實也使用了外部庫martinez-polygon-clipping。不過可以轉換思維方式，將部分共邊的情況轉換為完全共邊，再交給union進行合并。這個轉換過程我將其稱為點注入，將多邊形B的頂點注入到多邊形A中，即遍歷B的頂點進行判斷，若其在A的某個線段上且不是線段端頭，就將其插入到A的路徑中。A與B互相注入頂點之后，所有部分共邊的邊線都變成完全共邊了。

image

實現(xiàn)過程如下，其中沒有使用booleanPointOnLine，而是基于其實現(xiàn)了isPointOnLine，一方面在點線關系判斷時加入了容限值，同時排除了所有的端點，另一方面返回值里不僅包含了bool說明點是否在線上，同時還有index屬性說明點在線的哪個線段上，以方便將其插入路徑中：

/**
 * 將點注入到線上
 * @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));
        }
    });
}

至此即可完成多邊形的合并功能啦。

產品推廣

在JSAPI GL上實現(xiàn)的圖形編輯器集成了幾何圖形的繪制、編輯、刪除功能，相較于JSAPI v2功能更加完善且便于使用。該功能已上線官網(wǎng)，歡迎使用～
JavaScript API GL | 騰訊位置服務

注：GIF圖片較模糊且閃爍，不代表真實效果。

image

image

image