geojson-polygon-self-intersections - npm Package Compare versions

Comparing version 1.1.2 to 1.2.0

index.js

 // Find self-intersections in geojson polygon (possibly with interior rings)
 var rbush = require('rbush');
 
-module.exports = function(feature, filterFn, useSpatialIndex) {
+
+var merge = function(){
+  var output = {};
+  Array.prototype.slice.call(arguments).forEach(function(arg){
+    if(arg){
+      Object.keys(arg).forEach(function(key){
+        output[key]=arg[key];
+      });
+    }
+  });
+  return output;
+};
+defaults = {
+  useSpatialIndex: true,
+  epsilon: 0,
+  reportVertexOnVertex: false,
+  reportVertexOnEdge: false
+};
+
+module.exports = function(feature, filterFn, options0) {
+  var options;
+  if("object" === typeof options0){
+    options = merge(defaults,options0);
+  } else {
+    options = merge(defaults,{useSpatialIndex:options0});
+  }
+
   if (feature.geometry.type != "Polygon") throw new Error("The input feature must be a Polygon");
-  if (useSpatialIndex == undefined) useSpatialIndex = 1;
 
@@ -13,3 +38,3 @@ var coord = feature.geometry.coordinates;
 
-  if (useSpatialIndex) {
+  if (options.useSpatialIndex) {
     var allEdgesAsRbushTreeItems = [];
@@ -27,3 +52,3 @@ for (var ring0 = 0; ring0 < coord.length; ring0++) {
     for (var edge0 = 0; edge0 < coord[ring0].length-1; edge0++) {
-      if (useSpatialIndex) {
+      if (options.useSpatialIndex) {
         var bboxOverlaps = tree.search(rbushTreeItem(ring0, edge0));
@@ -50,2 +75,10 @@ bboxOverlaps.forEach(function(bboxIsect) {
 
+  // true if frac is (almost) 1.0 or 0.0
+  function isBoundaryCase(frac){
+    var e2 = options.epsilon * options.epsilon;
+    return e2 >= (frac-1)*(frac-1) || e2 >= frac*frac;
+  }
+  function isOutside(frac){
+    return frac < 0 - options.epsilon || frac > 1 + options.epsilon;
+  }
   // Function to check if two edges intersect and add the intersection to the output
@@ -72,4 +105,21 @@ function ifIsectAddToOutput(ring0, edge0, ring1, edge1) {
     };
-    if (frac0 >= 1 || frac0 <= 0 || frac1 >= 1 || frac1 <= 0) return; // require segment intersection
 
+    // There are roughly three cases we need to deal with.
+    // 1. If at least one of the fracs lies outside [0,1], there is no intersection.
+    if (isOutside(frac0) || isOutside(frac1)) {
+      return; // require segment intersection
+    }
+
+    // 2. If both are either exactly 0 or exactly 1, this is not an intersection but just
+    // two edge segments sharing a common vertex.
+    if (isBoundaryCase(frac0) && isBoundaryCase(frac1)){
+      if(! options.reportVertexOnVertex) return;
+    }
+
+    // 3. If only one of the fractions is exactly 0 or 1, this is
+    // a vertex-on-edge situation.
+    if (isBoundaryCase(frac0) || isBoundaryCase(frac1)){
+      if(! options.reportVertexOnEdge) return;
+    }
+
     var key = isect;
@@ -76,0 +126,0 @@ var unique = !seen[key];

package.json

 {
   "name": "geojson-polygon-self-intersections",
-  "version": "1.1.2",
+  "version": "1.2.0",
   "main": "index.js",
@@ -5,0 +5,0 @@ "repository": {

README.md

@@ -42,11 +42,23 @@ # geojson-polygon-self-intersections
 
-Finally, you can set a boolean variable to specify if a spatial index should be used to filter for possible intersections.
+Finally, you can pass an option object to control the behaviour of the algorithm.
+The following options are supported:
 
+|Option|Description|
+|------|-----------|
+| `useSpatialIndex` | Whether a spatial index should be used to filter for possible intersections. Default: `true` |
+| `reportVertexOnVertex` | If the same vertex (or almost the same vertex) appears more than once in the input, should this be reported as an intersection? Default: `false`|
+| `reportVertexOnEdge` | If a vertex lies (almost) exactly on an edge segment, should this be reported as an intersection? Default: `false` |
+| `epsilon` | It is almost never a good idea to compare floating point numbers for identity. Therefor, if we say "the same vertex" or "exactly on an edge segment", we need to define how "close" is "close enough". Note that the value is *not* used as an euclidian distance but always relative to the length of some edge segment. Default: `0`|
+
 Together, this may look like so:
 
 ```javascript
-var useSpatialIndex = 0;
-var isects = gpsi(poly, function filterFn(isect, ring0, edge0, start0, end0, frac0, ring1, edge1, start1, end1, frac1, unique){return [isect, frac0, frac1];}, useSpatialIndex);
+var options = {
+  useSpatialIndex:false
+};
+var isects = gpsi(poly, function filterFn(isect, ring0, edge0, start0, end0, frac0, ring1, edge1, start1, end1, frac1, unique){return [isect, frac0, frac1];}, options);
 
 // isects = [[[5, 8], 0.4856, 0.1865]], [[[7, 3], 0.3985, 0.9658]], ...]
 ```
+For backwards compatibility, if you pass anything other than an object, it will be interpreted as the value of the
+`useSpatialIndex`-option.

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

Improved metrics

Total package byte prevSize

11866

increased by24.36%

Lines of code

171

increased by34.65%

Number of lines in readme file

64

increased by23.08%

No dependency changes