earcut - npm Package Compare versions

Comparing version 1.1.0 to 1.2.0

package.json

 {
   "name": "earcut",
-  "version": "1.1.0",
+  "version": "1.2.0",
   "description": "The fastest and smallest JavaScript polygon triangulation library for your WebGL apps",
@@ -5,0 +5,0 @@ "main": "src/earcut.js",

README.md

 ## Earcut
 
-The fastest and smallest JavaScript polygon triangulation library. 1.7KB gzipped.
+The fastest and smallest JavaScript polygon triangulation library. 2.3KB gzipped.
 
@@ -8,4 +8,6 @@ [![Build Status](https://travis-ci.org/mapbox/earcut.svg?branch=master)](https://travis-ci.org/mapbox/earcut)
 
-The library implements an ear slicing algorithm which is extended to handle holes, twisted polygons,
-degeneracies and self-intersections in a way that doesn't _guarantee_ correctness of triangulation,
+The library implements a modified ear slicing algorithm,
+optimized by [z-order curve](http://en.wikipedia.org/wiki/Z-order_curve) hashing
+and extended to handle holes, twisted polygons, degeneracies and self-intersections
+in a way that doesn't _guarantee_ correctness of triangulation,
 but attempts to always produce acceptable results for practical data like geographical shapes.
@@ -27,6 +29,7 @@
 ------------------| ---- | --------- | -------- | -------- | ---------
-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
+OSM building      | 15   | _580,351_ | _27,832_ | _28,151_ | _216,352_
+dude shape        | 94   | _29,848_  | _6,194_  | _3,575_  | _13,027_
+holed dude shape  | 104  | _18,688_  | _5,428_  | _3,378_  | _2,264_
+complex OSM water | 2523 | _232_     | _63.72_  | failure  | failure
+huge OSM water    | 5667 | _30.82_   | _23.73_  | failure  | failure
 
@@ -77,2 +80,7 @@ Earcut may be slow for huge complex shapes,
 
+##### 1.2.0 (Jan 26)
+
+- Significantly improved performance on polygons with high number of vertices
+  by using z-order curve hashing for vertice lookup.
+
 ##### 1.1.0 (Jan 21)
@@ -79,0 +87,0 @@

src/earcut.js

@@ -7,8 +7,32 @@ 'use strict';
 
-    var outerNode = linkedList(points[0], true);
+    var outerNode = linkedList(points[0], true),
+        node, minX, minY, maxX, maxY, x, y, size,
+        len = 0,
+        threshold = 80;
 
+    for (var i = 0; len < threshold && i < points.length; i++) len += points[i].length;
+
+    // if the shape is not too simple, we'll use z-order curve hash later; calculate polygon bbox
+    if (len >= threshold) {
+        node = outerNode.next;
+        minX = maxX = node.p[0];
+        minY = maxY = node.p[1];
+        do {
+            x = node.p[0];
+            y = node.p[1];
+            if (x < minX) minX = x;
+            if (y < minY) minY = y;
+            if (x > maxX) maxX = x;
+            if (y > maxY) maxY = y;
+            node = node.next;
+        } while (node !== outerNode);
+
+        // minX, minY and size are later used to transform coords into integers for z-order calculation
+        size = Math.max(maxX - minX, maxY - minY);
+    }
+
     if (points.length > 1) outerNode = eliminateHoles(points, outerNode);
 
     var triangles = [];
-    if (outerNode) earcutLinked(outerNode, triangles);
+    if (outerNode) earcutLinked(outerNode, triangles, minX, minY, size);
 
@@ -47,6 +71,13 @@ return triangles;
         again = false;
+
         if (equals(node.p, node.next.p) || orient(node.prev.p, node.p, node.next.p) === 0) {
+
             node.prev.next = node.next;
             node.next.prev = node.prev;
+
+            if (node.prevZ) node.prevZ.nextZ = node.nextZ;
+            if (node.nextZ) node.nextZ.prevZ = node.prevZ;
+
             node = start = node.prev;
+
             if (node === node.next) return null;
@@ -63,6 +94,8 @@ again = true;
 
-function earcutLinked(ear, triangles, secondPass) {
+function earcutLinked(ear, triangles, minX, minY, size, secondPass) {
     ear = filterPoints(ear);
     if (!ear) return;
 
+    if (!secondPass && minX !== undefined) indexCurve(ear, minX, minY, size);
+
     var stop = ear,
@@ -76,3 +109,3 @@ prev, next;
 
-        if (isEar(ear)) {
+        if (isEar(ear, minX, minY, size)) {
             triangles.push(prev.p, ear.p, next.p);
@@ -83,2 +116,5 @@
 
+            if (ear.prevZ) ear.prevZ.nextZ = ear.nextZ;
+            if (ear.nextZ) ear.nextZ.prevZ = ear.prevZ;
+
             ear = next.next;
@@ -94,5 +130,5 @@ stop = next.next;
             // if we can't find any more ears, try filtering points and cutting again
-            if (!secondPass) earcutLinked(ear, triangles, true);
+            if (!secondPass) earcutLinked(ear, triangles, minX, minY, size, true);
             // if this didn't work, try splitting the remaining polygon into two
-            else splitEarcut(ear, triangles);
+            else splitEarcut(ear, triangles, minX, minY, size);
             break;
@@ -103,3 +139,3 @@ }
 
-function isEar(ear) {
+function isEar(ear, minX, minY, size) {
 
@@ -120,25 +156,85 @@ var a = ear.prev.p,
 
-    var node = ear.next.next,
-        cay = cy - ay,
+    // now make sure we don't have other points inside the potential ear
+
+    var cay = cy - ay,
         acx = ax - cx,
         aby = ay - by,
         bax = bx - ax,
-        px, py, s, t, k;
+        p, px, py, s, t, k, node;
 
-    // make sure we don't have other points inside the potential ear
-    while (node !== ear.prev) {
+    // if we use z-order curve hashing, iterate through the curve
+    if (minX !== undefined) {
 
-        px = node.p[0];
-        py = node.p[1];
+        // triangle bbox; min & max are calculated like this for speed
+        var minTX = ax < bx ? (ax < cx ? ax : cx) : (bx < cx ? bx : cx),
+            minTY = ay < by ? (ay < cy ? ay : cy) : (by < cy ? by : cy),
+            maxTX = ax > bx ? (ax > cx ? ax : cx) : (bx > cx ? bx : cx),
+            maxTY = ay > by ? (ay > cy ? ay : cy) : (by > cy ? by : cy),
 
-        node = node.next;
+            // z-order range for the current triangle bbox;
+            minZ = zOrder(minTX, minTY, minX, minY, size),
+            maxZ = zOrder(maxTX, maxTY, minX, minY, size);
 
-        s = cay * px + acx * py - acd;
-        if (s >= 0) {
-            t = aby * px + bax * py + abd;
-            if (t >= 0) {
-                k = A - s - t;
-                if ((k >= 0) && ((s && t) || (s && k) || (t && k))) return false;
+        // first look for points inside the triangle in increasing z-order
+        node = ear.nextZ;
+
+        while (node && node.z <= maxZ) {
+            p = node.p;
+            node = node.nextZ;
+            if (p === a || p === c) continue;
+
+            px = p[0];
+            py = p[1];
+
+            s = cay * px + acx * py - acd;
+            if (s >= 0) {
+                t = aby * px + bax * py + abd;
+                if (t >= 0) {
+                    k = A - s - t;
+                    if ((k >= 0) && ((s && t) || (s && k) || (t && k))) return false;
+                }
             }
         }
+
+        // then look for points in decreasing z-order
+        node = ear.prevZ;
+
+        while (node && node.z >= minZ) {
+            p = node.p;
+            node = node.prevZ;
+            if (p === a || p === c) continue;
+
+            px = p[0];
+            py = p[1];
+
+            s = cay * px + acx * py - acd;
+            if (s >= 0) {
+                t = aby * px + bax * py + abd;
+                if (t >= 0) {
+                    k = A - s - t;
+                    if ((k >= 0) && ((s && t) || (s && k) || (t && k))) return false;
+                }
+            }
+        }
+
+    // if we don't use z-order curve hash, simply iterate through all other points
+    } else {
+        node = ear.next.next;
+
+        while (node !== ear.prev) {
+            p = node.p;
+            node = node.next;
+
+            px = p[0];
+            py = p[1];
+
+            s = cay * px + acx * py - acd;
+            if (s >= 0) {
+                t = aby * px + bax * py + abd;
+                if (t >= 0) {
+                    k = A - s - t;
+                    if ((k >= 0) && ((s && t) || (s && k) || (t && k))) return false;
+                }
+            }
+        }
     }
@@ -149,3 +245,3 @@
 
-function splitEarcut(start, triangles) {
+function splitEarcut(start, triangles, minX, minY, size) {
     // find a valid diagonal that divides the polygon into two
@@ -161,4 +257,4 @@ var a = start;
                 // run earcut on each half
-                earcutLinked(a, triangles);
-                earcutLinked(c, triangles);
+                earcutLinked(a, triangles, minX, minY, size);
+                earcutLinked(c, triangles, minX, minY, size);
                 return;
@@ -196,2 +292,3 @@ }
 
+// David Eberly's algorithm for finding a bridge between hole and outer polygon
 function findHoleBridge(holeNode, outerNode) {
@@ -205,2 +302,4 @@ var node = outerNode,
 
+    // find a segment intersected by a ray from the hole's leftmost point to the left;
+    // segment's endpoint with lesser x will be potential connection point
     do {
@@ -222,2 +321,6 @@ a = node.p;
 
+    // look for points strictly inside the triangle of hole point, segment intersection and endpoint;
+    // if there are no points found, we have a valid connection;
+    // otherwise choose the point of the minimum angle with the ray as connection point
+
     var bx = mNode.p[0],
@@ -266,2 +369,98 @@ by = mNode.p[1],
 
+function indexCurve(start, minX, minY, size) {
+    var node = start;
+
+    do {
+        node.z = node.z || zOrder(node.p[0], node.p[1], minX, minY, size);
+        node.prevZ = node.prev;
+        node.nextZ = node.next;
+        node = node.next;
+    } while (node !== start);
+
+    node.prevZ.nextZ = null;
+    node.prevZ = null;
+
+    sortLinked(node);
+}
+
+// Simon Tatham's linked list merge sort algorithm
+// http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html
+function sortLinked(list) {
+    var i, p, q, e, tail, numMerges, pSize, qSize,
+        inSize = 1;
+
+    while (true) {
+        p = list;
+        list = null;
+        tail = null;
+        numMerges = 0;
+
+        while (p) {
+            numMerges++;
+            q = p;
+            pSize = 0;
+            for (i = 0; i < inSize; i++) {
+                pSize++;
+                q = q.nextZ;
+                if (!q) break;
+            }
+
+            qSize = inSize;
+
+            while (pSize > 0 || (qSize > 0 && q)) {
+
+                if (pSize === 0) {
+                    e = q;
+                    q = q.nextZ;
+                    qSize--;
+                } else if (qSize === 0 || !q) {
+                    e = p;
+                    p = p.nextZ;
+                    pSize--;
+                } else if (p.z <= q.z) {
+                    e = p;
+                    p = p.nextZ;
+                    pSize--;
+                } else {
+                    e = q;
+                    q = q.nextZ;
+                    qSize--;
+                }
+
+                if (tail) tail.nextZ = e;
+                else list = e;
+
+                e.prevZ = tail;
+                tail = e;
+            }
+
+            p = q;
+        }
+
+        tail.nextZ = null;
+
+        if (numMerges <= 1) return list;
+
+        inSize *= 2;
+    }
+}
+
+// z-order of a point given coords and bbox
+function zOrder(x, y, minX, minY, size) {
+    // coords are transformed into (0..1000) integer range
+    x = 1000 * (x - minX) / size;
+    x = (x | (x << 8)) & 0x00FF00FF;
+    x = (x | (x << 4)) & 0x0F0F0F0F;
+    x = (x | (x << 2)) & 0x33333333;
+    x = (x | (x << 1)) & 0x55555555;
+
+    y = 1000 * (y - minY) / size;
+    y = (y | (y << 8)) & 0x00FF00FF;
+    y = (y | (y << 4)) & 0x0F0F0F0F;
+    y = (y | (y << 2)) & 0x33333333;
+    y = (y | (y << 1)) & 0x55555555;
+
+    return x | (y << 1);
+}
+
 function getLeftmost(start) {
@@ -348,4 +547,4 @@ var node = start,
 function splitPolygon(a, b) {
-    var a2 = {p: a.p, prev: null, next: null},
-        b2 = {p: b.p, prev: null, next: null},
+    var a2 = new Node(a.p),
+        b2 = new Node(b.p),
         an = a.next,
@@ -370,7 +569,3 @@ bp = b.prev;
 function insertNode(point, last) {
-    var node = {
-        p: point,
-        prev: null,
-        next: null
-    };
+    var node = new Node(point);
 
@@ -389,1 +584,11 @@ if (!last) {
 }
+
+function Node(p) {
+    this.p = p;
+    this.prev = null;
+    this.next = null;
+
+    this.z = null;
+    this.prevZ = null;
+    this.nextZ = null;
+}

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

282973

increased by2.36%

Lines of code

1949

increased by9%

Number of lines in readme file

95

increased by9.2%

No dependency changes