d3-polygon - npm Package Compare versions

Comparing version 0.0.4 to 0.0.5

build/bundle.js

@@ -1,1 +0,1 @@
-var version = "0.0.4"; export * from "../index"; export {version};
+var version = "0.0.5"; export * from "../index"; export {version};

build/d3-polygon.js

@@ -44,2 +44,58 @@ (function (global, factory) {
 
+  // Returns the 2D cross product of AB and AC vectors, i.e., the z-component of
+  // the 3D cross product in a quadrant I Cartesian coordinate system (+x is
+  // right, +y is up). Returns a positive value if ABC is counter-clockwise,
+  // negative if clockwise, and zero if the points are collinear.
+  function cross(a, b, c) {
+    return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0]);
+  };
+
+  function lexicographicOrder(a, b) {
+    return a[0] - b[0] || a[1] - b[1];
+  }
+
+  // Computes the upper convex hull per the monotone chain algorithm.
+  // Assumes points.length >= 3, is sorted by x, unique in y.
+  // Returns an array of indices into points in left-to-right order.
+  function computeUpperHullIndexes(points) {
+    var n = points.length,
+        indexes = [0, 1],
+        size = 2;
+
+    for (var i = 2; i < n; ++i) {
+      while (size > 1 && cross(points[indexes[size - 2]], points[indexes[size - 1]], points[i]) <= 0) --size;
+      indexes[size++] = i;
+    }
+
+    return indexes.slice(0, size); // remove popped points
+  }
+
+  function hull(points) {
+    if ((n = points.length) < 3) return null;
+
+    var i,
+        n,
+        sortedPoints = new Array(n),
+        flippedPoints = new Array(n);
+
+    for (i = 0; i < n; ++i) sortedPoints[i] = [+points[i][0], +points[i][1], i];
+    sortedPoints.sort(lexicographicOrder);
+    for (i = 0; i < n; ++i) flippedPoints[i] = [sortedPoints[i][0], -sortedPoints[i][1]];
+
+    var upperIndexes = computeUpperHullIndexes(sortedPoints),
+        lowerIndexes = computeUpperHullIndexes(flippedPoints);
+
+    // Construct the hull polygon, removing possible duplicate endpoints.
+    var skipLeft = lowerIndexes[0] === upperIndexes[0],
+        skipRight = lowerIndexes[lowerIndexes.length - 1] === upperIndexes[upperIndexes.length - 1],
+        hull = [];
+
+    // Add upper hull in right-to-l order.
+    // Then add lower hull in left-to-right order.
+    for (i = upperIndexes.length - 1; i >= 0; --i) hull.push(points[sortedPoints[upperIndexes[i]][2]]);
+    for (i = +skipLeft; i < lowerIndexes.length - skipRight; ++i) hull.push(points[sortedPoints[lowerIndexes[i]][2]]);
+
+    return hull;
+  };
+
   function inside(polygon, point) {
@@ -86,3 +142,3 @@ var n = polygon.length,
 
-  var version = "0.0.4";
+  var version = "0.0.5";
 
@@ -92,2 +148,3 @@ exports.version = version;
   exports.centroid = centroid;
+  exports.hull = hull;
   exports.inside = inside;
@@ -94,0 +151,0 @@ exports.perimeter = perimeter;

build/d3-polygon.min.js

@@ -1,1 +0,1 @@
-!function(e,n){"object"==typeof exports&&"undefined"!=typeof module?n(exports):"function"==typeof define&&define.amd?define("d3-polygon",["exports"],n):n(e.d3_polygon={})}(this,function(e){"use strict";function n(e){for(var n,t=-1,r=e.length,o=e[r-1],f=0;++t<r;)n=o,o=e[t],f+=n[1]*o[0]-n[0]*o[1];return f/2}function t(e){for(var n,t,r=-1,o=e.length,f=0,i=0,u=e[o-1],d=0;++r<o;)n=u,u=e[r],d+=t=n[0]*u[1]-u[0]*n[1],f+=(n[0]+u[0])*t,i+=(n[1]+u[1])*t;return d*=3,[f/d,i/d]}function r(e,n){for(var t,r,o=e.length,f=e[o-1],i=n[0],u=n[1],d=f[0],c=f[1],a=!1,p=0;o>p;++p)f=e[p],t=f[0],r=f[1],r>u!=c>u&&(d-t)*(u-r)/(c-r)+t>i&&(a=!a),d=t,c=r;return a}function o(e){for(var n,t,r=-1,o=e.length,f=e[o-1],i=f[0],u=f[1],d=0;++r<o;)n=i,t=u,f=e[r],i=f[0],u=f[1],n-=i,t-=u,d+=Math.sqrt(n*n+t*t);return d}var f="0.0.4";e.version=f,e.area=n,e.centroid=t,e.inside=r,e.perimeter=o});
+!function(n,r){"object"==typeof exports&&"undefined"!=typeof module?r(exports):"function"==typeof define&&define.amd?define("d3-polygon",["exports"],r):r(n.d3_polygon={})}(this,function(n){"use strict";function r(n){for(var r,e=-1,t=n.length,o=n[t-1],f=0;++e<t;)r=o,o=n[e],f+=r[1]*o[0]-r[0]*o[1];return f/2}function e(n){for(var r,e,t=-1,o=n.length,f=0,u=0,i=n[o-1],l=0;++t<o;)r=i,i=n[t],l+=e=r[0]*i[1]-i[0]*r[1],f+=(r[0]+i[0])*e,u+=(r[1]+i[1])*e;return l*=3,[f/l,u/l]}function t(n,r,e){return(r[0]-n[0])*(e[1]-n[1])-(r[1]-n[1])*(e[0]-n[0])}function o(n,r){return n[0]-r[0]||n[1]-r[1]}function f(n){for(var r=n.length,e=[0,1],o=2,f=2;r>f;++f){for(;o>1&&t(n[e[o-2]],n[e[o-1]],n[f])<=0;)--o;e[o++]=f}return e.slice(0,o)}function u(n){if((e=n.length)<3)return null;var r,e,t=new Array(e),u=new Array(e);for(r=0;e>r;++r)t[r]=[+n[r][0],+n[r][1],r];for(t.sort(o),r=0;e>r;++r)u[r]=[t[r][0],-t[r][1]];var i=f(t),l=f(u),c=l[0]===i[0],h=l[l.length-1]===i[i.length-1],a=[];for(r=i.length-1;r>=0;--r)a.push(n[t[i[r]][2]]);for(r=+c;r<l.length-h;++r)a.push(n[t[l[r]][2]]);return a}function i(n,r){for(var e,t,o=n.length,f=n[o-1],u=r[0],i=r[1],l=f[0],c=f[1],h=!1,a=0;o>a;++a)f=n[a],e=f[0],t=f[1],t>i!=c>i&&(l-e)*(i-t)/(c-t)+e>u&&(h=!h),l=e,c=t;return h}function l(n){for(var r,e,t=-1,o=n.length,f=n[o-1],u=f[0],i=f[1],l=0;++t<o;)r=u,e=i,f=n[t],u=f[0],i=f[1],r-=u,e-=i,l+=Math.sqrt(r*r+e*e);return l}var c="0.0.5";n.version=c,n.area=r,n.centroid=e,n.hull=u,n.inside=i,n.perimeter=l});

index.js

 export {default as area} from "./src/area";
 export {default as centroid} from "./src/centroid";
+export {default as hull} from "./src/hull";
 export {default as inside} from "./src/inside";
 export {default as perimeter} from "./src/perimeter";

package.json

 {
   "name": "d3-polygon",
-  "version": "0.0.4",
+  "version": "0.0.5",
   "description": "Operations for two-dimensional polygons.",
@@ -5,0 +5,0 @@ "keywords": [

README.md

@@ -19,2 +19,8 @@ # d3-polygon
 
+<a href="#hull" name="hull">#</a> <b>hull</b>(<i>points</i>)
+
+<a href="http://bl.ocks.org/mbostock/6f14f7b7f267a85f7cdc"><img src="https://raw.githubusercontent.com/d3/d3-polygon/master/img/hull.png" width="250" height="250"></a>
+
+Returns the [convex hull](https://en.wikipedia.org/wiki/Convex_hull) of the specified *points* using [Andrew’s monotone chain algorithm](http://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain). The returned hull is represented as an array containing a subset of the input *points* arranged in counterclockwise order. Returns null if *points* has fewer than three elements.
+
 <a href="#inside" name="inside">#</a> <b>inside</b>(<i>polygon</i>, <i>point</i>)
@@ -21,0 +27,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

Improved metrics

Total package byte prevSize

25657

increased by190.6%

Number of package files

15

increased by25%

Lines of code

238

increased by61.9%

Number of lines in readme file

38

increased by18.75%

No dependency changes