delaunator - npm Package Compare versions

Comparing version 1.0.0 to 1.0.1

bench.js

@@ -1,20 +0,37 @@
-'use strict';
+'use strict'; /* eslint no-new: 0, no-unused-vars: 0 */
 
-// var points = [];
-// for (var i = 0; i < 100000; i++) {
-//     points.push([Math.random() * 1e5, Math.random() * 1e5]);
-// }
-var points = require('../concaveman/tmp/test.json');;
+var Delaunator = require('./');
+var fasterDelaunay = require('faster-delaunay');
+var incrementalDelaunay = require('incremental-delaunay');
+var delaunayFast = require('delaunay-fast');
 
-console.log(points.length + ' points');
+function triangulate(points) {
+    new Delaunator(points);
+    // fasterDelaunay(points).triangulate();
+    // incrementalDelaunay(points);
+    // delaunayFast.triangulate(points);
+}
 
-// var triangulate = require('delaunay-triangulate');
-// var triangulate = require('delaunay-fast').triangulate;
-// var delaunay = require('faster-delaunay');
-var triangulate = require('d3-voronoi').voronoi();
+var counts = [10000, 20000, 50000, 100000, 200000, 500000, 1000000];
+var generate = uniform;
 
-console.time('triangulate');
-var triangles = triangulate(points);
-console.timeEnd('triangulate');
+triangulate(generate(counts[0]));
 
-// console.log(triangles);
+for (var i = 0; i < counts.length; i++) {
+    var c = counts[i];
+    var points = generate(c);
+    console.time(c);
+    triangulate(points);
+    console.timeEnd(c);
+}
+
+function uniform(count) {
+    var points = [];
+    for (var i = 0; i < count; i++) {
+        points.push([
+            Math.random() * 1e3,
+            Math.random() * 1e3
+        ]);
+    }
+    return points;
+}

debug.js

@@ -5,5 +5,12 @@ 'use strict';
 
+var fasterDelaunay = require("faster-delaunay");
+
 var points = require('../concaveman/tmp/test.json');
 // var points = [[168, 180], [168, 178], [168, 179], [168, 181], [168, 183], [167, 183], [167, 184], [165, 184], [162, 186], [164, 188], [161, 188], [160, 191], [158, 193], [156, 193], [152, 195], [152, 198], [150, 198], [147, 198], [148, 205], [150, 210], [148, 210], [148, 208], [145, 206], [142, 206], [140, 206], [138, 206], [135, 206], [135, 209], [131, 209], [131, 211], [127, 211], [124, 210], [120, 207], [120, 204], [120, 202], [124, 201], [123, 201], [125, 198], [125, 194], [127, 194], [127, 191], [130, 191], [132, 189], [134, 189], [134, 186], [136, 184], [134, 182], [134, 179], [134, 176], [136, 174], [139, 174], [141, 177], [142, 176], [144, 176], [147, 178], [148, 176], [151, 178], [154, 178], [153, 175], [152, 174], [152, 170], [152, 168], [150, 166], [148, 166], [147, 165], [145, 162], [146, 160], [146, 157], [146, 155], [144, 155], [142, 152], [140, 150], [138, 150], [138, 148], [140, 145], [140, 142], [140, 138], [139, 138], [137, 138], [135, 138], [133, 135], [132, 132], [129, 132], [128, 132], [124, 132], [124, 130], [123, 130], [118, 126], [116, 124], [112, 122], [109, 122], [105, 122], [102, 124], [100, 124], [97, 124], [95, 126], [92, 127], [89, 127], [88, 130], [85, 132], [80, 134], [72, 134], [69, 134], [65, 138], [64, 138], [58, 137], [56, 133], [52, 133], [51, 133], [48, 133], [44, 133], [41, 131], [38, 130], [35, 130], [32, 127], [30, 127], [27, 127], [24, 127], [24, 126], [23, 124], [20, 122], [17, 122], [16, 118], [15, 116], [15, 110], [18, 108], [20, 102], [24, 97], [28, 102], [28, 98], [26, 97], [28, 94], [27, 85], [29, 79], [32, 76], [39, 70], [44, 66], [48, 65], [53, 61], [53, 58], [51, 54], [54, 54], [52, 48], [51, 43], [48, 42], [49, 38], [48, 34], [51, 30], [53, 33], [58, 30], [61, 30], [60, 27], [64, 26], [68, 24], [74, 24], [80, 24], [85, 26], [92, 26], [96, 29], [103, 32], [109, 33], [112, 37], [116, 37], [120, 37], [124, 35], [126, 35], [128, 38], [132, 38], [134, 41], [138, 38], [140, 36], [142, 40], [144, 43], [145, 41], [149, 41], [155, 41], [159, 41], [161, 46], [165, 46], [164, 42], [164, 39], [164, 34], [167, 30], [173, 24], [178, 24], [184, 24], [189, 26], [195, 21], [195, 20], [199, 20], [203, 20], [207, 17], [211, 17], [216, 17], [218, 16], [222, 22], [225, 27], [228, 31], [226, 34], [224, 34], [226, 39], [228, 43], [230, 46], [236, 46], [242, 46], [243, 50], [245, 50], [247, 54], [247, 56], [248, 60], [248, 65], [253, 66], [255, 64], [260, 64], [264, 67], [268, 71], [272, 66], [275, 66], [281, 61], [285, 66], [286, 70], [292, 74], [294, 74], [296, 74], [296, 71], [301, 74], [307, 74], [311, 78], [315, 74], [315, 77], [319, 77], [322, 82], [328, 82], [331, 81], [331, 84], [333, 86], [333, 90], [330, 95], [326, 98], [328, 99], [332, 98], [333, 101], [331, 104], [329, 104], [327, 106], [329, 111], [332, 116], [333, 119], [333, 122], [332, 126], [332, 130], [327, 130], [321, 130], [317, 130], [315, 134], [312, 134], [308, 138], [306, 138], [306, 144], [306, 149], [306, 152], [301, 152], [297, 154], [295, 154], [292, 154], [292, 158], [288, 158], [283, 162], [281, 164], [279, 163], [276, 163], [273, 166], [272, 169], [268, 168], [265, 170], [260, 172], [256, 176], [252, 176], [248, 181], [246, 182], [246, 189], [246, 194], [248, 197], [250, 198], [252, 200], [252, 203], [254, 205], [260, 205], [264, 202], [267, 202], [269, 202], [272, 199], [280, 199], [278, 202], [278, 207], [278, 211], [276, 211], [272, 213], [268, 213], [265, 213], [264, 211], [262, 210], [260, 210], [257, 212], [257, 214], [255, 217], [253, 217], [253, 221], [249, 220], [247, 220], [243, 222], [240, 223], [239, 226], [234, 231], [229, 231], [224, 231], [219, 227], [220, 227], [222, 224], [222, 222], [222, 219], [224, 217], [222, 214], [220, 212], [217, 210], [215, 210], [211, 209], [208, 206], [202, 209], [202, 205], [206, 202], [211, 198], [216, 195], [220, 192], [224, 192], [221, 186], [218, 186], [214, 185], [208, 185], [204, 186], [200, 186], [193, 183], [190, 182], [188, 182], [190, 178], [186, 178], [184, 174], [182, 171], [178, 171], [173, 174], [169, 174], [169, 175], [169, 179], [167, 182], [164, 186], [160, 192], [155, 195], [152, 198], [150, 198], [148, 198], [148, 202], [151, 208], [148, 210], [146, 208], [144, 205], [140, 205], [137, 208], [132, 208], [132, 210], [127, 210], [124, 210], [120, 206], [120, 202], [123, 202], [124, 201], [124, 198], [128, 195], [131, 191], [133, 187], [135, 183], [130, 203], [129, 208], [123, 203], [129, 203], [129, 198], [133, 198], [136, 200], [142, 200], [143, 199], [143, 197], [137, 196], [136, 194], [133, 194], [136, 186], [136, 182], [141, 186], [144, 186], [150, 186], [150, 190], [155, 190], [159, 188], [156, 182], [151, 182], [144, 182], [164, 176], [161, 177], [157, 177], [166, 176], [168, 165], [175, 167], [180, 167], [188, 159], [195, 164], [195, 162], [187, 162], [178, 163], [173, 166], [168, 170], [156, 170], [157, 165], [164, 165], [164, 161], [170, 159], [167, 158], [159, 154], [149, 151], [145, 145], [145, 138], [152, 138], [152, 146], [159, 146], [165, 153], [176, 153], [180, 153], [187, 153], [194, 153], [202, 153], [202, 158], [197, 158], [193, 158], [193, 142], [180, 142], [171, 142], [163, 135], [176, 135], [186, 139], [201, 139], [206, 139], [205, 147], [205, 160], [198, 160], [206, 174], [205, 178], [196, 178], [196, 182], [202, 182], [206, 181], [209, 181], [215, 181], [222, 181], [230, 177], [238, 175], [241, 175], [237, 175], [237, 168], [237, 161], [232, 156], [231, 162], [225, 166], [217, 169], [210, 173], [224, 173], [227, 173], [235, 175], [237, 178], [228, 192], [222, 199], [216, 199], [211, 204], [205, 206], [219, 207], [222, 211], [229, 214], [236, 214], [244, 211], [247, 211], [268, 206], [277, 201], [279, 201], [281, 202], [278, 202], [242, 178], [236, 170], [236, 162], [255, 162], [251, 156], [240, 156], [253, 152], [261, 152], [277, 157], [268, 151], [255, 143], [260, 142], [267, 145], [271, 149], [273, 154], [258, 146], [257, 131], [256, 134], [248, 137], [260, 137], [260, 134], [271, 137], [276, 138], [276, 144], [289, 144], [285, 150], [294, 150], [298, 149], [301, 145], [292, 145], [282, 134], [276, 134], [283, 127], [282, 116], [277, 113], [283, 113], [288, 106], [296, 106], [297, 113], [297, 118], [298, 118], [310, 122], [310, 128], [300, 130], [300, 140], [292, 129], [292, 114], [283, 122], [289, 122], [299, 122], [299, 134], [294, 134], [288, 124], [314, 121], [311, 113], [308, 110], [304, 96], [299, 90], [299, 82], [305, 87], [309, 94], [311, 101], [312, 102], [314, 107], [320, 112], [320, 115], [326, 116], [323, 109], [321, 102], [321, 94], [321, 90], [328, 90], [328, 88], [316, 88], [316, 84], [307, 84], [290, 77], [289, 88], [289, 97], [278, 97], [268, 106], [268, 110], [261, 105], [255, 103], [244, 103], [252, 100], [252, 91], [252, 82], [242, 78], [252, 78], [259, 78], [264, 87], [267, 92], [272, 91], [272, 83], [264, 83], [260, 79], [276, 79], [283, 84], [283, 94], [289, 94], [284, 86], [272, 77], [253, 110], [248, 110], [239, 110], [234, 114], [222, 125], [219, 127], [219, 131], [219, 138], [219, 141], [224, 139], [224, 135], [225, 130], [232, 136], [240, 138], [237, 131], [237, 118], [248, 120], [256, 122], [262, 127], [255, 118], [245, 110], [207, 129], [199, 134], [195, 134], [188, 130], [180, 130], [165, 129], [156, 129], [165, 128], [173, 125], [185, 126], [193, 126], [201, 124], [204, 123], [208, 116], [214, 114], [207, 114], [196, 114], [183, 121], [183, 111], [189, 117], [196, 112], [172, 126], [164, 126], [159, 114], [174, 106], [186, 106], [192, 105], [184, 105], [184, 96], [173, 96], [163, 111], [159, 110], [152, 110], [168, 110], [171, 106], [183, 98], [193, 101], [219, 96], [225, 97], [225, 104], [232, 92], [240, 92], [237, 86], [229, 86], [216, 88], [214, 79], [203, 79], [203, 75], [212, 75], [221, 75], [229, 80], [230, 89], [217, 88], [217, 77], [228, 77], [228, 69], [235, 71], [240, 71], [244, 66], [236, 54], [236, 62], [232, 68], [229, 61], [216, 61], [212, 58], [212, 47], [212, 39], [214, 28], [215, 48], [225, 55], [236, 55], [202, 65], [202, 54], [202, 44], [202, 24], [198, 32], [199, 38], [192, 38], [185, 38], [174, 42], [174, 48], [178, 51], [184, 51], [194, 55], [191, 68], [182, 68], [174, 69], [167, 67], [153, 59], [153, 49], [147, 49], [152, 58], [152, 74], [154, 83], [161, 83], [165, 88], [153, 97], [153, 89], [152, 82], [168, 88], [168, 101], [156, 102], [156, 119], [173, 110], [184, 110], [177, 106], [160, 106], [145, 125], [137, 122], [131, 120], [124, 120], [122, 118], [113, 118], [114, 111], [129, 111], [140, 110], [143, 106], [137, 102], [127, 102], [119, 98], [126, 93], [139, 93], [139, 99], [141, 95], [128, 89], [118, 74], [128, 76], [135, 76], [141, 83], [141, 71], [137, 61], [137, 50], [129, 50], [118, 50], [109, 52], [112, 61], [123, 60], [134, 60], [129, 76], [121, 67], [124, 76], [123, 76], [111, 74], [128, 73], [109, 83], [109, 94], [105, 103], [102, 118], [92, 113], [98, 105], [99, 93], [94, 93], [94, 81], [99, 81], [100, 73], [100, 89], [100, 60], [100, 55], [105, 37], [101, 34], [93, 37], [90, 37], [90, 49], [99, 49], [88, 68], [80, 68], [78, 64], [88, 62], [86, 77], [76, 89], [71, 91], [71, 106], [78, 106], [82, 118], [84, 110], [71, 104], [76, 103], [76, 91], [78, 83], [85, 89], [83, 103], [83, 119], [76, 130], [62, 130], [68, 127], [74, 126], [83, 123], [62, 123], [56, 123], [59, 129], [59, 120], [49, 110], [46, 106], [56, 100], [62, 94], [62, 109], [72, 112], [67, 112], [57, 112], [61, 122], [60, 102], [52, 125], [44, 121], [36, 114], [32, 110], [20, 110], [22, 118], [35, 118], [44, 124], [32, 119], [22, 111], [44, 96], [36, 106], [36, 94], [32, 94], [35, 83], [44, 91], [52, 91], [52, 80], [59, 80], [62, 76], [62, 70], [47, 78], [55, 75], [64, 71], [64, 60], [58, 53], [58, 43], [65, 43], [65, 60], [76, 52], [73, 38], [76, 36], [93, 48], [89, 39], [99, 40], [98, 50], [94, 63], [117, 63], [131, 67], [131, 74], [142, 78], [140, 61], [124, 58], [124, 48], [136, 55], [236, 200], [228, 200], [226, 192], [232, 198], [238, 210], [248, 210], [236, 220], [230, 223], [230, 213], [175, 32], [172, 32], [171, 38], [184, 30]];
 
+// var points = [];
+// for (var i = 0; i < 100000; i++) {
+//     points.push([Math.random() * 1e5, Math.random() * 1e5]);
+// }
+
 console.log(points.length + ' points');
@@ -13,2 +20,3 @@
 var delaunay = new Delaunator(points);
+// var delaunay = fasterDelaunay(points).triangulate();
 console.timeEnd('total');

index.js

@@ -16,3 +16,3 @@ 'use strict';
     var coords = this.coords = [];
-    var ids = this.ids = [];
+    var ids = this.ids = new Uint32Array(points.length);
 
@@ -23,5 +23,5 @@ for (var i = 0; i < points.length; i++) {
         var y = getY(p);
-        ids.push(i);
-        coords.push(x);
-        coords.push(y);
+        ids[i] = i;
+        coords[2 * i] = x;
+        coords[2 * i + 1] = y;
         if (x < minX) minX = x;
@@ -111,5 +111,14 @@ if (y < minY) minY = y;
 
-    this.triangles = [i0, i1, i2];
-    var adjacent = this.adjacent = [-1, -1, -1];
+    var maxTriangles = 2 * points.length - 5;
+    var triangles = this.triangles = new Uint32Array(maxTriangles * 3);
+    triangles[0] = i0;
+    triangles[1] = i1;
+    triangles[2] = i2;
+    this.trianglesLen = 3;
 
+    var adjacent = this.adjacent = new Int32Array(maxTriangles * 3);
+    adjacent[0] = -1;
+    adjacent[1] = -1;
+    adjacent[2] = -1;
+
     var xp, yp;
@@ -186,2 +195,6 @@ for (var k = 0; k < ids.length; k++) {
     }
+
+    // trim typed triangle mesh arrays
+    this.triangles = triangles.subarray(0, this.trianglesLen);
+    this.adjacent = adjacent.subarray(0, this.trianglesLen);
 }
@@ -234,10 +247,11 @@
         this.adjacent[a] = b;
-        this.adjacent[b] = a;
+        if (b !== -1) this.adjacent[b] = a;
     },
 
     _addTriangle(i, e) {
-        var t = this.triangles.length;
+        var t = this.trianglesLen;
         this.triangles[t] = e.i;
         this.triangles[t + 1] = i;
         this.triangles[t + 2] = e.next.i;
+        this.trianglesLen += 3;
         return t;
@@ -244,0 +258,0 @@ }

package.json

 {
   "name": "delaunator",
-  "version": "1.0.0",
-  "description": "The fastest JavaScript library for Delaunay triangulation of 2D points",
+  "version": "1.0.1",
+  "description": "A really fast JavaScript library for Delaunay triangulation of 2D points",
   "main": "index.js",
@@ -13,3 +13,3 @@ "dependencies": {},
   "scripts": {
-    "lint": "eslint index.js test.js",
+    "lint": "eslint index.js test.js bench.js",
     "pretest": "npm run lint",
@@ -16,0 +16,0 @@ "test": "tape test.js"

README.md

@@ -1,4 +0,4 @@
-## delaunator
+# delaunator
 
-The fastest JavaScript library for
+A really fast JavaScript library for
 [Delaunay triangulation](https://en.wikipedia.org/wiki/Delaunay_triangulation) of 2D points.
@@ -10,6 +10,8 @@ Implements a variation of the [Sweep-hull algorithm](http://s-hull.org/).
 
-### [Demo](https://mapbox.github.io/delaunator/)
 
-### Example
+## [Demo](https://mapbox.github.io/delaunator/)
 
+
+## Example
+
 ```js
@@ -23,4 +25,5 @@ var points = [[168, 180], [168, 178], [168, 179], [168, 181], [168, 183], ...];
 
-### API Reference
 
+## API Reference
+
 #### new Delaunator(points[, getX, getY])
@@ -34,11 +37,25 @@
 
-A flat array of triangle indices (each group of three numbers forms a triangle).
+A flat `Int32Array` array of triangle indices (each group of three numbers forms a triangle).
 
-### To do
 
-- [x] Implement the algorithm.
-- [x] Add a simple demo.
-- [x] Add proper tests.
-- [x] Clean up and document the API.
-- [ ] Release the first version to NPM.
-- [ ] Add a benchmark against similar libraries.
+## Performance
+
+Benchmark results for a uniform random distribution (`node bench.js`) against three fastest other libraries:
+
+points | delaunator | [faster-del](https://github.com/Bathlamos/delaunay-triangulation) | [incr-del](https://github.com/mikolalysenko/incremental-delaunay) | [del-fast](https://github.com/ironwallaby/delaunay)
+--: | --: | --: | --: | --:
+10000 | 26ms | 78ms | 81ms | 136ms
+20000 | 40ms | 140ms | 154ms | 386ms
+50000 | 174ms | 328ms | 428ms | 1.18s
+100000 | 327ms | 776ms | 874ms | 3.03s
+200000 | 658ms | 1.74s | 1.74s | 7.95s
+500000 | 2.07s | 3.87s | 4.3s | 28.2s
+1000000 | 4.95s | 6.99s | 9.03s | 76.96s
+
+
+## Papers
+
+The algorithm is based on ideas from the following papers:
+
+- [A simple sweep-line Delaunay triangulation algorithm](http://www.academicpub.org/jao/paperInfo.aspx?paperid=15630), 2013, Liu Yonghe, Feng Jinming, Shao Yuehong
+- [S-hull: a fast radial sweep-hull routine for Delaunay triangulation](http://www.s-hull.org/paper/s_hull.pdf), 2010, David Sinclair

test.js

@@ -13,3 +13,3 @@ 'use strict';
     var d = new Delaunator(points);
-    t.same(d.triangles, triangles);
+    t.same(Array.from(d.triangles), triangles);
     t.end();
@@ -16,0 +16,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

Minified code

Quality

This package contains minified code. This may be harmless in some cases where minified code is included in packaged libraries, however packages on npm should not minify code.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

78353

increased by7.47%

Number of package files

11

increased by10%

Lines of code

654

increased by26.99%

Number of low quality alerts

1

decreased by-50%

Number of lines in readme file

59

increased by40.48%

No dependency changes