earcut - npm Package Compare versions

Comparing version 1.2.3 to 1.3.0

package.json

 {
   "name": "earcut",
-  "version": "1.2.3",
+  "version": "1.3.0",
   "description": "The fastest and smallest JavaScript polygon triangulation library for your WebGL apps",
@@ -17,10 +17,10 @@ "main": "src/earcut.js",
   "devDependencies": {
-    "browserify": "^8.1.1",
+    "browserify": "^8.1.3",
     "coveralls": "^2.11.2",
-    "eslint": "^0.13.0",
+    "eslint": "^0.15.0",
     "istanbul": "^0.3.5",
     "mkdirp": "^0.5.0",
-    "tape": "^3.4.0",
-    "uglifyjs": "^2.3.6",
-    "watchify": "^2.2.1"
+    "tape": "^3.5.0",
+    "uglify-js": "^2.4.16",
+    "watchify": "^2.3.0"
   },
@@ -38,2 +38,9 @@ "eslintConfig": {
       "space-after-keywords": 2,
+      "space-before-function-parentheses": [
+        2,
+        {
+          "anonymous": "always",
+          "named": "never"
+        }
+      ],
       "comma-style": 2,
@@ -48,2 +55,3 @@ "no-lonely-if": 2,
       "space-in-brackets": 2,
+      "brace-style": 2,
       "quotes": [
@@ -53,2 +61,3 @@ 2,
       ],
+      "indent": 2,
       "curly": 0,
@@ -55,0 +64,0 @@ "no-constant-condition": 0

README.md

@@ -8,2 +8,4 @@ ## Earcut
 
+#### The algorithm
+
 The library implements a modified ear slicing algorithm,
@@ -13,3 +15,3 @@ optimized by [z-order curve](http://en.wikipedia.org/wiki/Z-order_curve) hashing
 in a way that doesn't _guarantee_ correctness of triangulation,
-but attempts to always produce acceptable results for practical data like geographical shapes.
+but attempts to always produce acceptable results for practical data.
 
@@ -49,6 +51,15 @@ It's based on ideas from
 Input should be an array of rings, where the first is outer ring and others are holes;
-each ring is an array of points, where each point is of the `[x, y]` form.
+each ring is an array of points, where each point is of the `[x, y]` or `[x, y, z]` form.
 
 Each group of three points in the resulting array forms a triangle.
 
+Alternatively, you can get triangulation results in the form of flat index and vertex arrays
+by passing `true` as a second argument to `earcut`
+(convenient for uploading results directly to WebGL as buffers):
+
+```js
+var triangles = earcut([[[10,0],[0,50],[60,60],[70,10]]], true);
+// {vertices: [0,50, 10,0, 70,10, 60,60], indices: [1,0,2, 3,2,1]}
+```
+
 #### Install
@@ -78,4 +89,12 @@
 
+#### Ports
+
+- [mapbox/earcut.hpp](https://github.com/mapbox/earcut.hpp) (C++11)
+
 #### Changelog
 
+##### 1.3.0 (Feb 24, 2015)
+
+- Added a second argument to `earcut` that switches output format to flat vertex and index arrays if set to `true`.
+
 ##### 1.2.3 (Feb 10, 2015)
@@ -82,0 +101,0 @@

src/earcut.js

@@ -5,6 +5,6 @@ 'use strict';
 
-function earcut(points) {
+function earcut(points, returnIndices) {
 
     var outerNode = filterPoints(linkedList(points[0], true)),
-        triangles = [];
+        triangles = returnIndices ? {vertices: [], indices: []} : [];
 
@@ -69,3 +69,3 @@ if (!outerNode) return triangles;
 function filterPoints(start, end) {
-    end = end || start;
+    if (!end) end = start;
 
@@ -103,2 +103,4 @@ var node = start,
 
+    var indexed = triangles.vertices !== undefined;
+
     // interlink polygon nodes in z-order
@@ -117,5 +119,11 @@ if (!pass && minX !== undefined) indexCurve(ear, minX, minY, size);
             // cut off the triangle
-            triangles.push(prev.p);
-            triangles.push(ear.p);
-            triangles.push(next.p);
+            if (indexed) {
+                addIndexedVertex(triangles, prev);
+                addIndexedVertex(triangles, ear);
+                addIndexedVertex(triangles, next);
+            } else {
+                triangles.push(prev.p);
+                triangles.push(ear.p);
+                triangles.push(next.p);
+            }
 
@@ -141,6 +149,7 @@ // remove ear node
             // try filtering points and slicing again
-            if (!pass) earcutLinked(filterPoints(ear), triangles, minX, minY, size, 1);
+            if (!pass) {
+                earcutLinked(filterPoints(ear), triangles, minX, minY, size, 1);
 
             // if this didn't work, try curing all small self-intersections locally
-            else if (pass === 1) {
+            } else if (pass === 1) {
                 ear = cureLocalIntersections(ear, triangles);
@@ -150,3 +159,5 @@ earcutLinked(ear, triangles, minX, minY, size, 2);
             // as a last resort, try splitting the remaining polygon into two
-            } else if (pass === 2) splitEarcut(ear, triangles, minX, minY, size);
+            } else if (pass === 2) {
+                splitEarcut(ear, triangles, minX, minY, size);
+            }
 
@@ -158,2 +169,16 @@ break;
 
+function addIndexedVertex(triangles, node) {
+    if (node.source) node = node.source;
+
+    var i = node.index;
+    if (i === null) {
+        var vertices = triangles.vertices;
+        node.index = i = vertices.length;
+        vertices.push(node.p[0]);
+        vertices.push(node.p[1]);
+        if (node.p.length > 2) vertices.push(node.p[2]);
+    }
+    triangles.indices.push(i);
+}
+
 // check whether a polygon node forms a valid ear with adjacent nodes
@@ -267,2 +292,4 @@ function isEar(ear, minX, minY, size) {
 function cureLocalIntersections(start, triangles) {
+    var indexed = !!triangles.vertices;
+
     var node = start;
@@ -276,5 +303,11 @@ do {
 
-            triangles.push(a.p);
-            triangles.push(node.p);
-            triangles.push(b.p);
+            if (indexed) {
+                addIndexedVertex(triangles, a);
+                addIndexedVertex(triangles, node);
+                addIndexedVertex(triangles, b);
+            } else {
+                triangles.push(a.p);
+                triangles.push(node.p);
+                triangles.push(b.p);
+            }
 
@@ -433,3 +466,3 @@ // remove two nodes involved
     do {
-        node.z = node.z || zOrder(node.p[0], node.p[1], minX, minY, size);
+        if (node.z === null) node.z = zOrder(node.p[0], node.p[1], minX, minY, size);
         node.prevZ = node.prev;
@@ -616,2 +649,5 @@ node.nextZ = node.next;
 
+    a2.source = a;
+    b2.source = b;
+
     a.next = b;
@@ -663,2 +699,6 @@ b.prev = a;
     this.nextZ = null;
+
+    // used for indexed output
+    this.source = null;
+    this.index = null;
 }

test/test.js

@@ -11,2 +11,3 @@ 'use strict';
 areaTest('water', 0.0019);
+areaTest('water', 0.0019, true);
 areaTest('water2');
@@ -22,3 +23,3 @@ areaTest('water3');
 
-function areaTest(filename, expectedDeviation) {
+function areaTest(filename, expectedDeviation, indexed) {
     expectedDeviation = expectedDeviation || 0.000001;
@@ -29,8 +30,20 @@
         var data = JSON.parse(fs.readFileSync(path.join(__dirname, '/fixtures/' + filename + '.json'))),
-            triangles = earcut(data),
+            triangles = earcut(data, indexed),
+            vertices = triangles.vertices,
+            indices = triangles.indices,
             expectedArea = polygonArea(data),
-            area = 0;
+            area = 0,
+            i;
 
-        for (var i = 0; i < triangles.length; i += 3) {
-            area += triangleArea(triangles[i], triangles[i + 1], triangles[i + 2]);
+        if (vertices) {
+            for (i = 0; i < indices.length; i += 3) {
+                area += triangleArea(
+                    [vertices[indices[i]], vertices[indices[i] + 1]],
+                    [vertices[indices[i + 1]], vertices[indices[i + 1] + 1]],
+                    [vertices[indices[i + 2]], vertices[indices[i + 2] + 1]]);
+            }
+        } else {
+            for (i = 0; i < triangles.length; i += 3) {
+                area += triangleArea(triangles[i], triangles[i + 1], triangles[i + 2]);
+            }
         }
@@ -37,0 +50,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

Mixed license

License

(Experimental) Package contains multiple licenses.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

318767

increased by0.4%

Number of low license alerts

0

decreased by-100%

Lines of code

2378

increased by10.76%

Number of lines in readme file

123

increased by18.27%

No dependency changes