earcut - npm Package Compare versions

Comparing version 1.0.6 to 1.1.0

package.json

 {
   "name": "earcut",
-  "version": "1.0.6",
+  "version": "1.1.0",
   "description": "The fastest and smallest JavaScript polygon triangulation library for your WebGL apps",
@@ -10,3 +10,5 @@ "main": "src/earcut.js",
     "build-dev": "mkdirp dist && browserify -d src/earcut.js -s earcut > dist/earcut.dev.js",
-    "build-min": "mkdirp dist && browserify src/earcut.js -s earcut | uglifyjs -c warnings=false -m > dist/earcut.min.js"
+    "build-min": "mkdirp dist && browserify src/earcut.js -s earcut | uglifyjs -c warnings=false -m > dist/earcut.min.js",
+    "cov": "istanbul cover test/*.js",
+    "coveralls": "istanbul cover test/*.js && coveralls < ./coverage/lcov.info"
   },
@@ -17,2 +19,4 @@ "author": "Vladimir Agafonkin",
     "browserify": "^8.1.1",
+    "coveralls": "^2.11.2",
+    "istanbul": "^0.3.5",
     "jshint": "^2.5.11",
@@ -19,0 +23,0 @@ "mkdirp": "^0.5.0",

README.md

 ## Earcut
 
-The fastest and smallest JavaScript polygon triangulation library for your WebGL apps. 1.6KB gzipped.
+The fastest and smallest JavaScript polygon triangulation library. 1.7KB gzipped.
 
+[![Build Status](https://travis-ci.org/mapbox/earcut.svg?branch=master)](https://travis-ci.org/mapbox/earcut)
+[![Coverage Status](https://coveralls.io/repos/mapbox/earcut/badge.svg?branch=master)](https://coveralls.io/r/mapbox/earcut?branch=master)
+
 The library implements an ear slicing algorithm which is extended to handle holes, twisted polygons,
@@ -10,3 +13,4 @@ degeneracies and self-intersections in a way that doesn't _guarantee_ correctness of triangulation,
 It's based on ideas from
-[FIST: Fast Industrial-Strength Triangulation of Polygons](http://www.cosy.sbg.ac.at/~held/projects/triang/triang.html) paper.
+[FIST: Fast Industrial-Strength Triangulation of Polygons](http://www.cosy.sbg.ac.at/~held/projects/triang/triang.html) by Martin Held
+and [Triangulation by Ear Clipping](http://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf) by David Eberly.
 
@@ -23,6 +27,6 @@ #### Why another triangulation library?
 ------------------| ---- | --------- | -------- | -------- | ---------
-OSM building      | 15   | _600,314_ | _28,124_ | _28,131_ | _210,320_
-dude shape        | 94   | _28,226_  | _5,904_  | _3,544_  | _12,916_
-holed dude shape  | 104  | _10,674_  | _5,204_  | _3,205_  | _2,232_
-complex OSM water | 2523 | _35.95_   | _64.73_  | failure  | failure
+OSM building      | 15   | _603,533_ | _28,124_ | _28,131_ | _210,320_
+dude shape        | 94   | _28,620_  | _5,904_  | _3,544_  | _12,916_
+holed dude shape  | 104  | _13,913_  | _5,204_  | _3,205_  | _2,232_
+OSM water         | 2523 | _45.13_   | _64.73_  | failure  | failure
 
@@ -70,1 +74,16 @@ Earcut may be slow for huge complex shapes,
 ![](https://cloud.githubusercontent.com/assets/25395/5778431/e8ec0c10-9da3-11e4-8d4e-a2ced6a7d2b7.png)
+
+#### Changelog
+
+##### 1.1.0 (Jan 21)
+
+- Improved performance on polygons with holes by switching from Held to Eberly hole elimination algorithm
+- More robustness fixes and tests
+
+##### 1.0.1 — 1.0.6 (Jan 20, 2015)
+
+- Various robustness improvements and fixes.
+
+##### 1.0.0 (Jan 18, 2015)
+
+- Initial release.

src/earcut.js

 'use strict';
 
-if (typeof module !== 'undefined') module.exports = earcut;
+module.exports = earcut;
 
 function earcut(points) {
 
-    var outerNode = filterPoints(linkedList(points[0], true));
+    var outerNode = linkedList(points[0], true);
 
-    if (points.length > 1) eliminateHoles(points, outerNode);
+    if (points.length > 1) outerNode = eliminateHoles(points, outerNode);
 
@@ -18,3 +18,3 @@ var triangles = [];
 // create a circular doubly linked list from polygon points in the specified winding order
-function linkedList(points, ccw) {
+function linkedList(points, clockwise) {
     var sum = 0,
@@ -26,7 +26,9 @@ len = points.length,
     for (i = 0, j = len - 1; i < len; j = i++) {
-        sum += (points[i][0] - points[j][0]) * (points[i][1] + points[j][1]);
+        var p1 = points[i],
+            p2 = points[j];
+        sum += (p2[0] - p1[0]) * (p1[1] + p2[1]);
     }
 
-    // link points into circular doubly-linked list in the specified winding order; return the leftmost point
-    if (ccw === (sum < 0)) {
+    // link points into circular doubly-linked list in the specified winding order
+    if (clockwise === (sum > 0)) {
         for (i = 0; i < len; i++) last = insertNode(points[i], last);
@@ -61,3 +63,6 @@ } else {
 
-function earcutLinked(ear, triangles) {
+function earcutLinked(ear, triangles, secondPass) {
+    ear = filterPoints(ear);
+    if (!ear) return;
+
     var stop = ear,
@@ -83,7 +88,9 @@ prev, next;
 
-        ear = ear.next;
+        ear = next;
 
         if (ear === stop) {
-            // if we can't find valid ears anymore, split remaining polygon into two
-            splitEarcut(ear, triangles);
+            // if we can't find any more ears, try filtering points and cutting again
+            if (!secondPass) earcutLinked(ear, triangles, true);
+            // if this didn't work, try splitting the remaining polygon into two
+            else splitEarcut(ear, triangles);
             break;
@@ -94,3 +101,2 @@ }
 
-// iterate through points to check if there's a reflex point inside a potential ear
 function isEar(ear) {
@@ -110,3 +116,3 @@
 
-    if (A <= 0) return false; // reflex
+    if (A <= 0) return false; // reflex, can't be an ear
 
@@ -120,2 +126,3 @@ var node = ear.next.next,
 
+    // make sure we don't have other points inside the potential ear
     while (node !== ear.prev) {
@@ -137,2 +144,3 @@
     }
+
     return true;
@@ -143,6 +151,2 @@ }
     // find a valid diagonal that divides the polygon into two
-
-    start = filterPoints(start);
-    if (!start) return;
-
     var a = start;
@@ -179,43 +183,99 @@ do {
     for (i = 0; i < queue.length; i++) {
-        eliminateHole(outerNode, queue[i]);
+        eliminateHole(queue[i], outerNode);
+        outerNode = filterPoints(outerNode);
     }
+
+    return outerNode;
 }
 
-function getLeftmost(start) {
-    var node = start,
-        leftmost = start;
-    do {
-        if (node.p[0] < leftmost.p[0]) leftmost = node;
-        node = node.next;
-    } while (node !== start);
-
-    return leftmost;
+function eliminateHole(holeNode, outerNode) {
+    outerNode = findHoleBridge(holeNode, outerNode);
+    if (outerNode) splitPolygon(holeNode, outerNode);
 }
 
-function eliminateHole(outerNode, holeNode) {
-    var queue = [];
+function findHoleBridge(holeNode, outerNode) {
+    var node = outerNode,
+        p = holeNode.p,
+        px = p[0],
+        py = p[1],
+        qMax = -Infinity,
+        mNode, a, b;
 
-    var node = outerNode;
     do {
-        if (node.p[0] <= holeNode.p[0]) queue.push({node: node, dist: sqrDist(node.p, holeNode.p)});
+        a = node.p;
+        b = node.next.p;
+
+        if (py <= a[1] && py >= b[1]) {
+            var qx = a[0] + (py - a[1]) * (b[0] - a[0]) / (b[1] - a[1]);
+            if (qx <= px && qx > qMax) {
+                qMax = qx;
+                mNode = a[0] < b[0] ? node : node.next;
+            }
+        }
         node = node.next;
     } while (node !== outerNode);
 
-    queue.sort(compareDist);
+    if (!mNode) return null;
 
-    for (var i = 0; i < queue.length; i++) {
-        node = queue[i].node;
+    var bx = mNode.p[0],
+        by = mNode.p[1],
+        pbd = px * by - py * bx,
+        pcd = px * py - py * qMax,
+        cpy = py - py,
+        pcx = px - qMax,
+        pby = py - by,
+        bpx = bx - px,
+        A = pbd - pcd - (qMax * by - py * bx),
+        sign = A <= 0 ? -1 : 1,
+        stop = mNode,
+        tanMin = Infinity,
+        mx, my, amx, s, t, tan;
 
-        if (!intersectsPolygon(node, node.p, holeNode.p, true) && locallyInside(node, holeNode)) {
-            splitPolygon(holeNode, node);
-            return;
+    node = mNode.next;
+
+    while (node !== stop) {
+
+        mx = node.p[0];
+        my = node.p[1];
+        amx = px - mx;
+
+        if (amx >= 0 && mx >= bx) {
+            s = (cpy * mx + pcx * my - pcd) * sign;
+            if (s >= 0) {
+                t = (pby * mx + bpx * my + pbd) * sign;
+
+                if (t >= 0 && A * sign - s - t >= 0) {
+                    tan = Math.abs(py - my) / amx; // tangential
+                    if (tan < tanMin && locallyInside(node, holeNode)) {
+                        mNode = node;
+                        tanMin = tan;
+                    }
+                }
+            }
         }
+
+        node = node.next;
     }
+
+    return mNode;
 }
 
+function getLeftmost(start) {
+    var node = start,
+        leftmost = start;
+    do {
+        if (node.p[0] < leftmost.p[0]) leftmost = node;
+        node = node.next;
+    } while (node !== start);
+
+    return leftmost;
+}
+
 function isValidDiagonal(a, b) {
     return !intersectsPolygon(a, a.p, b.p) &&
-           locallyInside(a, b) && locallyInside(b, a) && middleInside(a, a.p, b.p);
+           locallyInside(a, b) && locallyInside(b, a) &&
+           middleInside(a, a.p, b.p);
 }
 
+// winding order of triangle formed by 3 given points
 function orient(p, q, r) {
@@ -232,12 +292,9 @@ var o = (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1]);
 // check if two segments intersect
-function intersects(p1, q1, p2, q2, touches) {
-    var o1 = orient(p1, q1, p2),
-        o2 = orient(p1, q1, q2),
-        o3 = orient(p2, q2, p1),
-        o4 = orient(p2, q2, q1);
-    return (!touches || o1 && o2 && o3 && o4) && o1 !== o2 && o3 !== o4;
+function intersects(p1, q1, p2, q2) {
+    return orient(p1, q1, p2) !== orient(p1, q1, q2) &&
+           orient(p2, q2, p1) !== orient(p2, q2, q1);
 }
 
 // check if a polygon diagonal intersects any polygon segments
-function intersectsPolygon(start, a, b, touches) {
+function intersectsPolygon(start, a, b) {
     var node = start;
@@ -248,3 +305,3 @@ do {
 
-        if (p1 !== a && p2 !== a && p1 !== b && p2 !== b && intersects(p1, p2, a, b, touches)) return true;
+        if (p1 !== a && p2 !== a && p1 !== b && p2 !== b && intersects(p1, p2, a, b)) return true;
 
@@ -274,5 +331,5 @@ node = node.next;
 
-        if (((p1[1] > py) !== (p2[1] > py)) && (px < (p2[0] - p1[0]) * (py - p1[1]) / (p2[1] - p1[1]) + p1[0])) {
-            inside = !inside;
-        }
+        if (((p1[1] > py) !== (p2[1] > py)) &&
+            (px < (p2[0] - p1[0]) * (py - p1[1]) / (p2[1] - p1[1]) + p1[0])) inside = !inside;
+
         node = node.next;
@@ -284,12 +341,2 @@ } while (node !== start);
 
-function sqrDist(a, b) {
-    var dx = a[0] - b[0],
-        dy = a[1] - b[1];
-    return dx * dx + dy * dy;
-}
-
-function compareDist(a, b) {
-    return a.dist - b.dist;
-}
-
 function compareX(a, b) {
@@ -296,0 +343,0 @@ return a.p[0] - b.p[0];

test/test.js

@@ -7,21 +7,32 @@ var test = require('tape'),
 areaTest('dude');
-areaTest('water', 0.0009);
+areaTest('water', 0.0021);
 areaTest('water2');
 areaTest('water3');
+areaTest('water3b');
 areaTest('water4');
-areaTest('water-huge', 0.0007);
+areaTest('water-huge', 0.0021);
+areaTest('water-huge2', 0.0023);
+areaTest('degenerate');
+areaTest('bad-hole', 0.05);
+areaTest('empty-square');
 
 function areaTest(filename, expectedDeviation) {
     expectedDeviation = expectedDeviation || 0.000001;
+
     test(filename, function (t) {
-        var data = JSON.parse(fs.readFileSync(__dirname + '/fixtures/' + filename + '.json'));
-        var triangles = earcut(data);
-        var area = 0;
+
+        var data = JSON.parse(fs.readFileSync(__dirname + '/fixtures/' + filename + '.json')),
+            triangles = earcut(data),
+            expectedArea = polygonArea(data),
+            area = 0;
+
         for (var i = 0; i < triangles.length; i += 3) {
-            area += ringArea([triangles[i], triangles[i + 1], triangles[i + 2]]);
+            area += triangleArea(triangles[i], triangles[i + 1], triangles[i + 2]);
         }
-        var expectedArea = polygonArea(data);
-        var deviation = Math.abs(area - expectedArea) / expectedArea;
+
+        var deviation = expectedArea === 0 && area === 0 ? 0 : Math.abs(area - expectedArea) / expectedArea;
+
         t.ok(deviation < expectedDeviation,
             'deviation ' + formatPercent(deviation) + ' is less than ' + formatPercent(expectedDeviation));
+
         t.end();
@@ -35,2 +46,6 @@ });
 
+function triangleArea(a, b, c) {
+    return Math.abs((a[0] - c[0]) * (b[1] - a[1]) - (a[0] - b[0]) * (c[1] - a[1])) / 2;
+}
+
 function ringArea(points) {
@@ -41,3 +56,3 @@ var sum = 0;
     }
-    return Math.abs(sum);
+    return Math.abs(sum) / 2;
 }
@@ -44,0 +59,0 @@

No alert changes

Improved metrics

Total package byte prevSize

276448

32.58%

Number of package files

21

40%

Lines of code

1788

58.51%

Number of lines in readme file

87

27.94%

Worsened metrics

Dev dependency count

8

33.33%

No dependency changes