turf.polygonize not creating polygons from grid of multilinestring lines

[maphew]

turf.polygonize isn't creating polygons from this input:

• https://gist.github.com/maphew/7bb77059574ea714977edae41e4b114c#file-w3w-grid-shwatka-4d-geojson
• Expected result similar to this output from 'Qgis >> Vector geomery tools >> polygonize': https://gist.github.com/maphew/7bb77059574ea714977edae41e4b114c#file-qgis-vector-polygonize-output-geojson

Code snippet:

var grid = {"coordinates":[[[-135.025,6 ...snip.... 4092,60.6726],"type":"MultiLineString","properties"};
var polygon = turf.polygonize(grid);

Full test case - https://jsfiddle.net/87cq6edb/

[DenisCarriere]

@NickCis Can you have a look at this? You are the one most "qualified" to answer/fix this.

[NickCis]

Current implementation of polygonize makes the following assumption (copying from docs):

Edges must be correctly noded, i.e., they must only meet at their endpoints.

As far as i understand, in this test case the lineStrings are not correctly noded, ie: they intersect between them, that's why polygonize isn't generating any polygons.

I must highlight that (according to the docs) this is the library's expected behavior.

At the moment, the user has to look for all the intersections and make the lineStrings divitions. It was the problem described at the end of the PR.

[maphew]

Oh sorry. I read "I ended up porting this to javascript because I wanted the same functionality as Shapely's polygonize function" in the PR intro and assumed there was feature parity with Shapely (because that's what I wanted to believe ;-).

[NickCis]

As far as i know Shapely is calling the GEOS's polygonizer class. This is a javascript port of that c++ class. I think that with Shapely you'll get the same problem.

If that's not the case, please tell me so (if possible, inform the Shapely version used and a working example). i could try to port that functionality.

[DenisCarriere]

We can always attempt to port over Shapely's polygonize function to NodeJS and include it in the test cases.

We've done this so far with some of the @turf/boolean modules.

This test process is a bit unconventional, but if you want to check boolean-shapely (should only be used for testing purposes).

[maphew]

According to https://gis.stackexchange.com/a/95374/108 Qgis' polygonize uses shapely, and that's how I produced the "expected output" above.

[NickCis]

@maphew I really don't know what QGis is exactly doing, but if i run Shapely's polygonize i get the same blank result.

Using the following script (i'm using shapely 1.5.17):

#! /usr/bin/env python
import sys
import json

from shapely.ops import polygonize
from shapely.geometry import asShape
from shapely.geometry import mapping

def main(in_path, out_path):
    with open(in_path, encoding='utf-8') as f:
        geo_json = json.load(f)

    output = {
        'type': 'FeatureCollection',
        'features': []
    }

    for poly in polygonize(asShape(geo_json)):
        output['features'].append({
            'type': 'Feature',
            'properties': {},
            'geometry': mapping(poly)
        })

    with open(out_path, 'w') as f:
        json.dump(output, f)

if __name__ == '__main__':
    main(sys.argv[1], sys.argv[2])

It's first argument is the input geojson, and the second one the output feature collection:

$ ./polygonizer.py input.geojson outpu.geojson

When running with your example, i get a blank result, as with turf's Polygonizer.

If it is run with an example that has the lines correctly nodded, eg:

{
  "coordinates": [
    [
        [0, 0],
        [1, 1]
    ],
    [
        [0, 0],
        [0, 1]
    ],
    [
        [0, 1],
        [1, 1]
    ],
    [
        [1, 1],
        [1, 0]
    ],
    [
        [1, 0],
        [0, 0]
    ]
  ],
  "type": "MultiLineString",
  "properties": {}
}

Loading

The polygons are formed.

If you read the performace section of Shapely's ops documentation, it says that it is using geos c library. Turf's polygonize is a port of the Polygonizer class of that library, so you get similar results.

[NickCis]

I've been reading the QGis source code in order to understand what QGis is doing.

Apparently, when you are running "QGis >> Vector geometry Tools >> Polygonize", it runs this QGis Polygonize algorithm.

If you look at the processAlgorithm method, you'll notice that before calling QgsGeometry.polygonize it calls QgsGeometry.unaryUnion.

The QgsGeometry.polygonize (header file) function is basically a wrapper of the geos polygonize function. But, if you read Doxygen comments of the header file, you'll notice the following clarification:

The input geometries must be fully noded (i.e. nodes exist at every common intersection of the geometries). The easiest way to ensure this is to first call unaryUnion() on the set of input geometries and then pass the result to polygonize()

The QgsGeometry.unaryUnion (header file) function is basically a wrapper of geos combine function. Reading the docs this function does the following:

Compute the unary union on a list of \a geometries. May be faster than an iterative union on a set of geometries. The returned geometry will be fully noded, i.e. a node will be created at every common intersection of the input geometries. An empty geometry will be returned in the case of errors.

So, in terms of a library, turf's polygonize works correctly. Its output is coherent with what other libraries (such as geos or shapely) create. All of them have the precondition that the input has to be correctly nodded.

I really don't know (please help me @DenisCarriere ) if there is a function in turf that does something similar to QgsGeometry.unaryUnion or geos combine, if not, i could try to port that function into turf.

[maphew]

Thank you for the attention and research Nicolas!

[DenisCarriere]

⭐️ 👍 @NickCis Great research. Unfortunately we Turf does not have any methods that performs unaryUnion, however it would be REALLY useful since I do recall needing this type of behavior in the past.

I have no issues if you call this new module exactly the same name as QGIS @turf/unary-union.

The only library that would do a similar effort would be @turf/line-intersect and if you only pass it 2-vertex segments it will perform really fast (skips any indexing).

[NickCis]

Ok!, I'll be starting to work on that new module. I'll update with further news.