polygonize - npm Package Compare versions

Comparing version 1.0.0 to 1.0.1

.eslintrc.js

@@ -10,2 +10,3 @@ module.exports = {
     camelcase: [0],
+    'no-return-assign': ['error', 'except-parens'],
     'consistent-return': [0],
@@ -12,0 +13,0 @@ 'valid-jsdoc': [2, {

dist/EdgeRing.js

@@ -31,2 +31,4 @@ 'use strict';
     this.edges = [];
+    this.polygon = undefined; //< Caches Polygon representation
+    this.envelope = undefined; //< Caches Envelope representation
   }
@@ -46,2 +48,3 @@
       this.edges.push(edge);
+      this.polygon = this.envelope = undefined;
     }
@@ -155,3 +158,2 @@
     /** Creates a Polygon representing the EdgeRing.
-     * XXX: the polygon could be cached
      * @returns {Feature<Polygon>} - Polygon representation of the Edge Ring
@@ -163,2 +165,3 @@ */
     value: function toPolygon() {
+      if (this.polygon) return this.polygon;
       var coordinates = this.edges.map(function (edge) {
@@ -168,7 +171,6 @@ return edge.from.coordinates;
       coordinates.push(this.edges[0].from.coordinates);
-      return polygon([coordinates]);
+      return this.polygon = polygon([coordinates]);
     }
 
     /** Calculates the envelope of the EdgeRing.
-     * XXX: the envelope could be cached
      * @returns {Feature<Polygon>} - envelope
@@ -180,3 +182,4 @@ */
     value: function getEnvelope() {
-      return envelope(this.toMultiPoint());
+      if (this.envelope) return this.envelope;
+      return this.envelope = envelope(this.toPolygon());
     }
@@ -183,0 +186,0 @@

dist/Graph.js

@@ -9,4 +9,20 @@ 'use strict';
     Edge = require('./Edge'),
-    EdgeRing = require('./EdgeRing');
+    EdgeRing = require('./EdgeRing'),
+    _require = require('@turf/meta'),
+    flattenEach = _require.flattenEach,
+    coordReduce = _require.coordReduce,
+    _require2 = require('@turf/invariant'),
+    featureOf = _require2.featureOf;
 
+/** Validates the geoJson.
+ *
+ * @param {Geojson} geoJson - input geoJson.
+ * @throws {Error} if geoJson is invalid.
+ */
+function validateGeoJson(geoJson) {
+  if (!geoJson) throw new Error('No geojson passed');
+
+  if (geoJson.type !== 'FeatureCollection' && geoJson.type !== 'GeometryCollection' && geoJson.type !== 'MultiLineString' && geoJson.type !== 'LineString' && geoJson.type !== 'Feature') throw new Error('Invalid input type \'' + geoJson.type + '\'. Geojson must be FeatureCollection, GeometryCollection, LineString, MultiLineString or Feature');
+}
+
 /** Represents a planar graph of edges and nodes that can be used to compute a
@@ -60,12 +76,23 @@ * polygonization.
     /** Creates a graph from a GeoJSON.
+     *
      * @param {FeatureCollection<LineString>} geoJson - it must comply with the restrictions detailed in the index
      * @returns {Graph} - The newly created graph
+     * @throws {Error} if geoJson is invalid.
      */
     value: function fromGeoJson(geoJson) {
+      validateGeoJson(geoJson);
+
       var graph = new Graph();
-      geoJson.features.forEach(function (feature) {
-        var start = graph.getNode(feature.geometry.coordinates[0]),
-            end = graph.getNode(feature.geometry.coordinates[1]);
+      flattenEach(geoJson, function (feature) {
+        featureOf(feature, 'LineString', 'Graph::fromGeoJson');
+        // When a LineString if formed by many segments, split them
+        coordReduce(feature, function (prev, cur) {
+          if (prev) {
+            var start = graph.getNode(prev),
+                end = graph.getNode(cur);
 
-        graph.addEdge(start, end);
+            graph.addEdge(start, end);
+          }
+          return cur;
+        });
       });
@@ -115,3 +142,3 @@
       if (node.innerEdges.length <= 1) {
-        var outerNodes = node.outerEdges.map(function (e) {
+        var outerNodes = node.getOuterEdges().map(function (e) {
           return e.to;
@@ -167,4 +194,4 @@ });
       } else {
-        node.outerEdges.forEach(function (edge, i) {
-          node.outerEdges[(i === 0 ? node.outerEdges.length : i) - 1].symetric.next = edge;
+        node.getOuterEdges().forEach(function (edge, i) {
+          node.getOuterEdge((i === 0 ? node.getOuterEdges().length : i) - 1).symetric.next = edge;
         });
@@ -187,3 +214,3 @@ }
     value: function _computeNextCCWEdges(node, label) {
-      var edges = node.outerEdges;
+      var edges = node.getOuterEdges();
       var firstOutDE = void 0,
@@ -298,3 +325,3 @@ prevInDE = void 0;
         var degree = 0;
-        edge.from.outerEdges.forEach(function (e) {
+        edge.from.getOuterEdges().forEach(function (e) {
           if (e.label === startEdge.label) ++degree;
@@ -347,3 +374,3 @@ });
 
-      node.outerEdges.forEach(function (edge) {
+      node.getOuterEdges().forEach(function (edge) {
         return _this6.removeEdge(edge);
@@ -350,0 +377,0 @@ });

dist/index.js

@@ -8,7 +8,9 @@ 'use strict';
 
-/** Implementation of GEOSPolygonize function (`geos::operation::polygonize::Polygonizer`).
+/**
+ * Polygonizes {@link LineString|(Multi)LineString(s)} into {@link Polygons}.
  *
+ * Implementation of GEOSPolygonize function (`geos::operation::polygonize::Polygonizer`).
+ *
  * Polygonizes a set of lines that represents edges in a planar graph. Edges must be correctly
- * noded, i.e., they must only meet at their endpoints. LineStrings must only have two coordinate
- * points.
+ * noded, i.e., they must only meet at their endpoints.
  *
@@ -18,7 +20,8 @@ * The implementation correctly handles:
  * - Dangles: edges which have one or both ends which are not incident on another edge endpoint.
- * - Cut Edges (bridges): edges that are connected at both ends but which do not form part
- *   of a polygon.
+ * - Cut Edges (bridges): edges that are connected at both ends but which do not form part of a polygon.
  *
- * @param {FeatureCollection<LineString>} geoJson - Lines in order to polygonize
- * @returns {FeatureCollection<Polygon>} - Polygons created
+ * @name polygonize
+ * @param {FeatureCollection|Geometry|Feature<LineString|MultiLineString>} geoJson Lines in order to polygonize
+ * @returns {FeatureCollection<Polygon>} Polygons created
+ * @throws {Error} if geoJson is invalid.
  */
@@ -25,0 +28,0 @@ module.exports = function polygonize(geoJson) {

dist/Node.js

@@ -22,7 +22,8 @@ 'use strict';
     this.id = Node.buildId(coordinates);
-    this.coordinates = coordinates; //< Number[]
-    this.innerEdges = []; //< Edge[]
+    this.coordinates = coordinates; //< {Number[]}
+    this.innerEdges = []; //< {Edge[]}
 
     // We wil store to (out) edges in an CCW order as geos::planargraph::DirectedEdgeStar does
-    this.outerEdges = []; //< Edge[]
+    this.outerEdges = []; //< {Edge[]}
+    this.outerEdgesSorted = false; //< {Boolean} flag that stores if the outer Edges had been sorted
   }
@@ -46,3 +47,2 @@
     /** Outer edges are stored CCW order.
-     * XXX: on each add we are ordering, this could be optimized
      * @param {Edge} edge - Edge to add as an outerEdge.
@@ -54,30 +54,61 @@ */
     value: function addOuterEdge(edge) {
+      this.outerEdges.push(edge);
+      this.outerEdgesSorted = false;
+    }
+
+    /** Sorts outer edges in CCW way.
+     * @private
+     */
+
+  }, {
+    key: 'sortOuterEdges',
+    value: function sortOuterEdges() {
       var _this = this;
 
-      this.outerEdges.push(edge);
-      //this.outerEdges.sort((a, b) => a.compareTo(b));
-      // Using this comparator in order to be deterministic
-      this.outerEdges.sort(function (a, b) {
-        var aNode = a.to,
-            bNode = b.to;
+      if (!this.outerEdgesSorted) {
+        //this.outerEdges.sort((a, b) => a.compareTo(b));
+        // Using this comparator in order to be deterministic
+        this.outerEdges.sort(function (a, b) {
+          var aNode = a.to,
+              bNode = b.to;
 
-        if (aNode.coordinates[0] - _this.coordinates[0] >= 0 && bNode.coordinates[0] - _this.coordinates[0] < 0) return 1;
-        if (aNode.coordinates[0] - _this.coordinates[0] < 0 && bNode.coordinates[0] - _this.coordinates[0] >= 0) return -1;
+          if (aNode.coordinates[0] - _this.coordinates[0] >= 0 && bNode.coordinates[0] - _this.coordinates[0] < 0) return 1;
+          if (aNode.coordinates[0] - _this.coordinates[0] < 0 && bNode.coordinates[0] - _this.coordinates[0] >= 0) return -1;
 
-        if (aNode.coordinates[0] - _this.coordinates[0] === 0 && bNode.coordinates[0] - _this.coordinates[0] === 0) {
-          if (aNode.coordinates[1] - _this.coordinates[1] >= 0 || bNode.coordinates[1] - _this.coordinates[1] >= 0) return aNode.coordinates[1] - bNode.coordinates[1];
-          return bNode.coordinates[1] - aNode.coordinates[1];
-        }
+          if (aNode.coordinates[0] - _this.coordinates[0] === 0 && bNode.coordinates[0] - _this.coordinates[0] === 0) {
+            if (aNode.coordinates[1] - _this.coordinates[1] >= 0 || bNode.coordinates[1] - _this.coordinates[1] >= 0) return aNode.coordinates[1] - bNode.coordinates[1];
+            return bNode.coordinates[1] - aNode.coordinates[1];
+          }
 
-        var det = orientationIndex(_this.coordinates, aNode.coordinates, bNode.coordinates);
-        if (det < 0) return 1;
-        if (det > 0) return -1;
+          var det = orientationIndex(_this.coordinates, aNode.coordinates, bNode.coordinates);
+          if (det < 0) return 1;
+          if (det > 0) return -1;
 
-        var d1 = Math.pow(aNode.coordinates[0] - _this.coordinates[0], 2) + Math.pow(aNode.coordinates[1] - _this.coordinates[1], 2),
-            d2 = Math.pow(bNode.coordinates[0] - _this.coordinates[0], 2) + Math.pow(bNode.coordinates[1] - _this.coordinates[1], 2);
+          var d1 = Math.pow(aNode.coordinates[0] - _this.coordinates[0], 2) + Math.pow(aNode.coordinates[1] - _this.coordinates[1], 2),
+              d2 = Math.pow(bNode.coordinates[0] - _this.coordinates[0], 2) + Math.pow(bNode.coordinates[1] - _this.coordinates[1], 2);
 
-        return d1 - d2;
-      });
+          return d1 - d2;
+        });
+        this.outerEdgesSorted = true;
+      }
     }
+
+    /** Retrieves outer edges.
+     * They are sorted if they aren't in the CCW order.
+     * @returns {Edge[]} - List of outer edges sorted in a CCW order.
+     */
+
   }, {
+    key: 'getOuterEdges',
+    value: function getOuterEdges() {
+      this.sortOuterEdges();
+      return this.outerEdges;
+    }
+  }, {
+    key: 'getOuterEdge',
+    value: function getOuterEdge(i) {
+      this.sortOuterEdges();
+      return this.outerEdges[i];
+    }
+  }, {
     key: 'addInnerEdge',
@@ -84,0 +115,0 @@ value: function addInnerEdge(edge) {

package.json

 {
   "name": "polygonize",
-  "version": "1.0.0",
+  "version": "1.0.1",
   "description": "Javascript implementation of GEOS's Polygonize function",
   "main": "dist/index.js",
   "scripts": {
-    "test": "npm run lint && npm run test-es5",
+    "test": "npm run lint && npm run test-es5 && npm run bench",
     "test-es5": "npm run build && tape dist/*.test.js dist/test.js",
@@ -12,3 +12,5 @@ "test-es6": "tape src/*.test.js src/test.js",
     "build": "babel src --out-dir dist",
-    "prepublish": "npm run build"
+    "prepublish": "npm run build",
+    "bench-es6": "node src/bench.js",
+    "bench": "node dist/bench.js"
   },
@@ -28,3 +30,5 @@ "repository": {
   "babel": {
-    "presets": ["es2015"]
+    "presets": [
+      "es2015"
+    ]
   },
@@ -40,5 +44,8 @@ "author": "Nicolas Cisco <@nickcis>",
     "babel-preset-es2015": "^6.24.1",
+    "benchmark": "^2.1.4",
     "eslint": "^3.19.0",
     "eslint-config-mourner": "^2.0.1",
-    "tape": "^4.6.3"
+    "load-json-file": "^2.0.0",
+    "tape": "^4.6.3",
+    "write-json-file": "^2.2.0"
   },
@@ -48,4 +55,6 @@ "dependencies": {
     "@turf/helpers": "^4.3.0",
-    "@turf/inside": "^4.3.0"
+    "@turf/inside": "^4.3.0",
+    "@turf/invariant": "^4.3.0",
+    "@turf/meta": "^4.3.0"
   }
 }

README.md

@@ -12,7 +12,9 @@ # Polygonize
 ```javascript
-/** Implementation of GEOSPolygonize function (`geos::operation::polygonize::Polygonizer`).
+/**
+ * Polygonizes {@link LineString|(Multi)LineString(s)} into {@link Polygons}.
  *
+ * Implementation of GEOSPolygonize function (`geos::operation::polygonize::Polygonizer`).
+ *
  * Polygonizes a set of lines that represents edges in a planar graph. Edges must be correctly
- * noded, i.e., they must only meet at their endpoints. LineStrings must only have two coordinate
- * points.
+ * noded, i.e., they must only meet at their endpoints.
  *
@@ -22,7 +24,8 @@ * The implementation correctly handles:
  * - Dangles: edges which have one or both ends which are not incident on another edge endpoint.
- * - Cut Edges (bridges): edges that are connected at both ends but which do not form part
- *     of a polygon.
+ * - Cut Edges (bridges): edges that are connected at both ends but which do not form part of a polygon.
  *
- * @param {FeatureCollection<LineString>} geoJson - Lines in order to polygonize
- * @returns {FeatureCollection<Polygon>} - Polygons created
+ * @name polygonize
+ * @param {FeatureCollection|Geometry|Feature<LineString|MultiLineString>} geoJson Lines in order to polygonize
+ * @returns {FeatureCollection<Polygon>} Polygons created
+ * @throws {Error} if geoJson is invalid.
  */
@@ -55,7 +58,7 @@ ```
 
+Polygonizes [(Multi)LineString(s)](http://geojson.org/geojson-spec.html#linestring) into [Polygons](Polygons).
+
 Implementation of GEOSPolygonize function (`geos::operation::polygonize::Polygonizer`).
 
-Polygonizes a set of lines that represents edges in a planar graph. Edges must be correctly
-noded, i.e., they must only meet at their endpoints. LineStrings must only have two coordinate
-points.
+Polygonizes a set of lines that represents edges in a planar graph. Edges must be correctly noded, i.e., they must only meet at their endpoints.
 
@@ -65,9 +68,11 @@ The implementation correctly handles:
 -   Dangles: edges which have one or both ends which are not incident on another edge endpoint.
--   Cut Edges (bridges): edges that are connected at both ends but which do not form part
-      of a polygon.
+-   Cut Edges (bridges): edges that are connected at both ends but which do not form part of a polygon.
 
 **Parameters**
 
--   `geoJson` **[FeatureCollection](http://geojson.org/geojson-spec.html#feature-collection-objects)&lt;[LineString](http://geojson.org/geojson-spec.html#linestring)>** Lines in order to polygonize
+-   `geojson` **([FeatureCollection](http://geojson.org/geojson-spec.html#feature-collection-objects) \| [Geometry](http://geojson.org/geojson-spec.html#geometry) \| [Feature](http://geojson.org/geojson-spec.html#feature-objects)&lt;([LineString](http://geojson.org/geojson-spec.html#linestring) \| [MultiLineString](http://geojson.org/geojson-spec.html#multilinestring))>)** Lines in order to polygonize
 
+
+-   Throws **[Error](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Error)** if geoJson is invalid.
+
 Returns **[FeatureCollection](http://geojson.org/geojson-spec.html#feature-collection-objects)&lt;[Polygon](http://geojson.org/geojson-spec.html#polygon)>** Polygons created
@@ -74,0 +79,0 @@

New alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Fixed alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Filesystem access

Supply chain risk

Accesses the file system, and could potentially read sensitive data.

Found 1 instance in 1 package

Improved metrics

Number of lines in readme file

83

increased by6.41%

Number of low supply chain risk alerts

0

decreased by-100%

Worsened metrics

Total package byte prevSize

119186

decreased by-16.27%

Dependency count

5

increased by66.67%

Dev dependency count

8

increased by60%

Number of package files

14

decreased by-44%

Lines of code

842

decreased by-8.28%

Dependency changes

• + Added@turf/invariant@^4.3.0

• + Added@turf/meta@^4.3.0