mapbox / earcut Goto Github PK
View Code? Open in Web Editor NEWThe fastest and smallest JavaScript polygon triangulation library for your WebGL apps
License: ISC License
The fastest and smallest JavaScript polygon triangulation library for your WebGL apps
License: ISC License
I'm getting an error in the function findHoleBridge() on this line:
297: if (hy <= p.y && hy >= p.next.y) {
p is null.
I've been working on this for a few hours and I haven't made any headway. I'm using 3-dimensional polygons with several holes. What might cause this problem?
I know that it's not earcut's goal to be perfect, but just to be acceptable in practice. What I'm wondering is, if it's possible to run earcut as a fast optimistic pass, and fallback to something slower but more robust for problematic geometry. That of course requires earcut to be aware when it might be wrong, or maybe even more conservative just that the input is possibly problematic. Is there a way to sort of use earcut "conservatively", and bail out with an error if there is not a guarantee for the answer to be correct?
I know in a way it's probably asking a lot, but of course it would be great to have the performance improvement for earcut in the 95% of cases where it can handle it, and otherwise fall back to something like tess2.
Maybe worded in a different way, is it sort of clearly known when and where earcut can go wrong? Is it realistic to possibly categorize (hopefully efficiently) inputs that are / are not simple in the eyes of earcut? Even if if there was some performance overhead but half of the time earcut could be used, it would still be a win.
PS: I saw deviation, but I was thinking of something more along the lines of a quick pre-pass or an early bail out, not a post analysis. And also somehow my instinct tells me that just comparing the signed area might not always work. Couldn't it be possible that there are just multiple errors that cancel out in regards to area?
Thanks
Test case:
[
[[1920,552],[1904,616],[1912,664],[1984,672],[2008,712],[1944,720],[1904,760],[1896,800],[1856,760],[1824,768],[1824,832],[1864,864],[1888,864],[1904,936],[1936,944],[1936,1064],[1936,1112],[1872,1136],[1856,1160],[1840,1144],[1792,1152],[1784,1112],[1752,1096],[1608,1096],[1600,1064],[1640,1040],[1664,992],[1640,968],[1568,1024],[1560,1056],[1480,1048],[1440,1072],[1440,1032],[1400,1032],[1400,1088],[1336,1136],[1320,1136],[1264,1072],[1232,1080],[1240,1104],[1200,1096],[1232,1048],[1272,1032],[1272,1000],[1232,1024],[1176,1024],[1176,1000],[1248,952],[1344,944],[1352,904],[1424,880],[1448,848],[1496,840],[1512,800],[1568,760],[1616,752],[1640,640],[1680,600],[1736,592],[1776,560],[1776,536],[1840,464],[1848,400],[1888,328],[1952,264],[2000,240],[2040,240],[2040,264],[1968,376],[1912,424],[1936,512],[1920,528],[1880,528],[1872,552],[1920,552]],
[[1608,800],[1576,848],[1520,840],[1512,872],[1456,904],[1440,952],[1528,936],[1552,912],[1584,912],[1608,880],[1664,864],[1680,816],[1656,776],[1608,800]],
[[1720,792],[1736,792],[1720,780],[1720,792]],
[[1656,728],[1670,752],[1672,728],[1656,728]],
[[1712,680],[1696,720],[1720,728],[1736,704],[1736,680],[1712,680]],
[[1968,712],[2000,712],[1968,688],[1968,712]]
]
It looks like this happens when a hole connects to outer polygon, then another hole connects to that hole through the same vertice, but since there are two vertices after eliminating the hole, one of the two connections leads to a broken outline. Should be fixable with some more checks in the findHoleBridge
routine.
[[
[-20037508.34,19971868.877628453,0],
[-20037508.34,-19971868.877628453,0],
[20037508.34,-19971868.877628453,0],
[20037508.34,19971868.877628453,0]
],
[
[537637.6007702783,5907542.234420554,0],
[539500.1483225027,5905165.501947839,0],
[538610.3146341922,5905217.430281373,0],
[538040.6306361248,5906132.0755739985,0],
[538068.958329954,5906571.138846622,0],
[537711.0379352621,5906645.06648362,0],
[537629.886026485,5907533.69114742,0]
]]
Ref: #16 (comment) @sctf4
Processed ~5 million polygons from a Mapbox Terrain subset and found just 79 cases with deviations that are not fixed by filtering out collinear points (fix-alt
branch): https://gist.github.com/mourner/738f8ff6c7dae5a1144e (for reference, it's 159 on master without filtering).
edit: it's down to 4 failing cases with the latest patches.
This is a great set of cases to investigate and fix remaining Earcut issues. A lot of them seem to be about rings sharing a point (edges touching by an endpoint).
I'll look into them in the next few days but any help is appreciated too. cc @hjanetzek @mrgreywater
The biggest failing sample looks like this (it's a hole on the left):
When using earcut on client-side I get the error: "module is undefined"
I suggest changing the first line from:
module.exports = earcut;
to:
if ( 'undefined' !== typeof exports && 'undefined' !== typeof module ) {
module.exports = earcut;
}
that way it should work normally on Node and on client-side.
There are also no tests for a [x, y, z] file!
Ref: mapbox/earcut.hpp#10. We should try this and benchmark. cc @jfirebaugh
Currently the most expensive operation when triangulating is checking whether a potential ear contains any reflex vertices (which means it can't be cut off). It requires looping through all the points on each ear, which makes earcut perform poorly on shapes with thousands of points.
In FIST paper, Martin Held proposes using a simple grid for indexing the vertices, with conclusion that it improves performance dramatically for polygons with high number of points (in tests, it starts to pay off with >64).
In Earcut and JS, the overhead of hashing will probably be bigger, so it'll start to pay off much later, but it's still worth exploring. A very rough rbush-based implementation on earcut pays off only at >1-2k vertices, but with an optimized, earcut-specific grid, it'll probably be much faster.
Held's hole elimination algorithm is very slow on some input (e.g. takes 70% on test/fixtures/water-huge.json
because of 2 bad holes).
There's a much more efficient algorithm described by Eberly in http://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf
Not sure this fits here, but I wanted to say this.
I tried to use this library to cut my maps' walls into convex pieces for box2d. I thought the fact that all my point were on a grid would make this library perform correctly. It ended up being wrong on some maps:
earcut: http://i.imgur.com/F4aC3S2.png
libtess: http://i.imgur.com/PZ41Gkf.png
I've found that some of the vertices in my polygons are being ignored when run through earcut, resulting in less triangles than would be expected.
For example, take the following points:
[68238.985, 268.575, 68248.747, 268.512, 68248.747, 259.248, 68238.985, 259.248, 68238.338, 259.248, 68238.338, 268.58, 68238.985, 268.575]
There are 6 unique vertices (7 minus the duplicated start/end vertex), which when run through earcut produce the following 3 triangles:
[5, 4, 2, 2, 1, 6, 6, 5, 2]
Which looks like this (notice how the vertex second from left at the bottom is part of no face):
When the same polygon is run through poly2tri the results are as per expected; 4 triangles using all vertices:
Is this expected with earcut, or is something wrong? I notice in the readme that it's suggested that earcut can sacrifice triangulation quality so I want to be sure that's the cause before moving to another triangulation approach for now.
For tile providers, it helps to do the same comparison between geometry area and earcut area that is done in earcut's tests, which helps ensure that the tiles are 100% compatible with earcut's algorithm. Would it be possible to expose this calculation as a helper method, like earcutArea(geom)
that returns the sum of the areas of the earcut triangles? Having it exposed would reduce the likelihood of area miscalculation in tile provider tests, and would prevent the tests from getting out of sync.
Originally from mapbox/earcut.hpp#11, reduced to the following test case:
[
[[800,300],[500,800],[1200,800]],
[[798,572],[792,606],[768,614],[758,586]],
[[892,584],[894,594],[882,588]],
[[842,596],[860,626],[848,622]],
]
cc @jfirebaugh
So I upgraded, and I flattened the arrays. Here is the original code:
for (; featureIndex < featureMax; featureIndex++) {
rawVerts = [];
feature = features[featureIndex];
//***
coords = feature.geometry.coordinates[0];
for (i = 0, iMax = coords.length; i < iMax; i++) {
rawVerts.push([coords[i][1], coords[i][0]]);
}
rawVerts.pop();
currentColor = [Math.random(), Math.random(), Math.random()];
triangles = earcut([rawVerts]);
for (i = 0, iMax = triangles.length; i < iMax; i++) {
triangle = triangles[i];
pixel = L.glify.latLonToPixelXY(triangle[0], triangle[1]);
verts.push(pixel.x, pixel.y, currentColor[0], currentColor[1], currentColor[2]
/**random color -> **/ );
//TODO: handle color
}
}
here is the upgraded, and broken code:
for (; featureIndex < featureMax; featureIndex++) {
rawVerts = [];
feature = features[featureIndex];
//***
coords = feature.geometry.coordinates[0];
for (i = 0, iMax = coords.length; i < iMax; i++) {
rawVerts.push(coords[i][1], coords[i][0]);
}
rawVerts.pop();
rawVerts.pop();
currentColor = [Math.random(), Math.random(), Math.random()];
triangles = earcut(rawVerts);
for (i = 0, iMax = triangles.length; i < iMax; i += 2) {
pixel = L.glify.latLonToPixelXY(triangles[i], triangles[i + 1]);
verts.push(pixel.x, pixel.y, currentColor[0], currentColor[1], currentColor[2]
/**random color -> **/ );
//TODO: handle color
}
}
And, although my wife mentioned that it does look like a fabulous piece of art, it isn't my intended output. Where did I go wrong?
earcut([])
produces:
/Users/john/Development/earcut/src/earcut.js:73
if (!node.steiner && (equals(data, node.i, node.next.i) || orient(data
^
TypeError: Cannot read property 'steiner' of undefined
at filterPoints (/Users/john/Development/earcut/src/earcut.js:73:18)
at earcut (/Users/john/Development/earcut/src/earcut.js:11:21)
at Test.<anonymous> (/Users/john/Development/earcut/test/test.js:26:19)
at Test.bound [as _cb] (/Users/john/Development/earcut/node_modules/tape/lib/test.js:63:32)
at Test.run (/Users/john/Development/earcut/node_modules/tape/lib/test.js:76:10)
at Test.bound [as run] (/Users/john/Development/earcut/node_modules/tape/lib/test.js:63:32)
at Object.next [as _onImmediate] (/Users/john/Development/earcut/node_modules/tape/lib/results.js:70:15)
at processImmediate [as _immediateCallback] (timers.js:354:15)
Expected it to return an empty array.
Currently, earcut will always produce triangles in a clockwise winding order, regardless of the sense of the winding order of the original polygon. In 3d, this can reverse the direction of the normal vector which is used for example for lighting calculations of the generated triangles with respect to the original polygon. So for 3d applications it is often required to reflect the winding order of the original polygon in the winding order of the triangles.
I created a branch with a few, simple modifications to this effect here:
https://github.com/andreasplesch/earcut/tree/ccw-winding
I would gladly submit a pull request if there is a desire to accommodate such a feature. There is a performance cost for ccw polygons since the array of indices needs to be reversed. array.reverse(), however, is a native array function, and hopefully optimized. To avoid this cost, it would be necessary to take into account winding order during construction of the triangle list which is also possible.
I have a low poly 2D camera mesh with three contours, and I'm having trouble triangulating it with earcut
.
The way it should look, rendered with lineTo:
The way it looks, rendered with earcut triangles:
I'm wondering if you have any recommended modules/ideas to deal with this?
Here is my test case:
var earcut = require('earcut')
var canvas = document.createElement('canvas')
var context = canvas.getContext('2d')
var size = 800
canvas.width = canvas.height = size
render()
function render () {
var scale = 0.25
context.fillStyle = 'rgba(0,0,0,0.25)'
context.strokeStyle = '#1d1d1d'
context.lineWidth = 1 / scale
context.clearRect(0, 0, size, size)
context.save()
context.scale(scale, scale)
context.translate(150, 50)
var points = [[[896,672],[1183,974],[881,1247],[608,945],[896,672]],[[1600,256],[1848,448],[1781,1589],[1,1579],[11,331],[427,224],[633,0],[1223,16],[1600,256]],[[896,1408],[1187,1300],[1340,1016],[1263,703],[896,512],[604,619],[451,903],[528,1216],[896,1408]]]
// renderCanvas(points, '#1d1d1d')
renderEarcut(points, '#1d1d1d')
}
function renderCanvas (poly, color) {
context.fillStyle = context.strokeStyle = color
context.beginPath()
poly.forEach(function (path) {
path.forEach(function (point, i) {
if (i === 0) context.moveTo(point[0], point[1])
else context.lineTo(point[0], point[1])
})
})
context.fill()
}
function renderEarcut (poly, color) {
var result = flattenData(poly)
var verts = result.vertices
var cells = earcut(verts, result.holes, result.dimensions)
context.fillStyle = context.strokeStyle = color
context.beginPath()
for (var i = 0; i < cells.length; i+=3) {
var a = cells[i], b = cells[i+1], c = cells[i+2]
context.moveTo(verts[a * 2], verts[a * 2 + 1])
context.lineTo(verts[b * 2], verts[b * 2 + 1])
context.lineTo(verts[c * 2], verts[c * 2 + 1])
context.lineTo(verts[a * 2], verts[a * 2 + 1])
}
context.fill()
context.restore()
}
function flattenData (data) {
var dim = data[0][0].length,
result = {vertices: [], holes: [], dimensions: dim},
holeIndex = 0
for (var i = 0; i < data.length; i++) {
for (var j = 0; j < data[i].length; j++) {
for (var d = 0; d < dim; d++) result.vertices.push(data[i][j][d])
}
if (i > 0) {
holeIndex += data[i - 1].length
result.holes.push(holeIndex)
}
}
return result
}
document.body.appendChild(canvas)
Hi,
First, thanks for creating this amazing library and open sourcing it! I've enjoyed using it but I'm having trouble understanding the following results:
earcut([-180, -90, -180, 0, -180, 90, -90, -90, -90, 0, -90, 90, 0, -90, 0, 0, 0, 90, 90, -90, 90, 0, 90, 90, 180, -90, 180, 0, 180, 90]);
The result I get back is 4 triangles but shouldn't there be 8 triangles since there are no holes?
[3, 2, 0, 12, 11, 9, 9, 8, 6, 6, 5, 3]
Taking a step back, I'm working on partitioning the globe with 15 points (lon, lat) to visualize on a map but the problem is that when I render these triangles, I'm left with 4 triangle holes when I'm not expecting any?
The triangulation comes back as an empty array if the vertices of the polygon are in a vertical plane, e.g.
polygon = [0,0,0, 1,0,1, 2,0,0]
earcut['default'](polygon, null, 3)
will return []
Are three dimensions fully supported or only if the polygon can be mapped to the XY plane, effectively by just ignoring the Z coordinate ?
This square in the XZ plane does not return any triangles in my testing:
earcut([0,0,0, 10,0,0, 10,0,10, 0,0,10, 0,0,0], null, 3);
Currently point filtering routine is run on the whole polygon after a split. We should do this only on affected nodes instead.
It looks like earcut filters out points along colinear segments of the polygon as these are not required to cover the polygon with triangles. However, I would like to have triangles with a vertex at these filtered out points since the same set of points is used for something else (the sides of a 3d extrusion of the polygon). which does not need the filtering.
Is there a way to avoid the filtering ? It looks the algorithm may rely on not having colinear segments ? Eg. this is done not just for performance reasons ?
Currently ear slicing is done sequentially, which is very fast but produces bad triangulation quality. We could try some modifications of the algorithm that produce much better triangles:
Then we'd look if we can make this optional so you can choose between max quality triangulation and max speed triangulation.
I'm looking to use earcut for some 3D triangulation. I've tried running through some of my existing data and have met mixed results.
This 3D polygon triangulates ok:
var earcut = require("earcut");
// x, y, height
var points = [458875, 5438350, 116, 458885, 5438350, 116, 458885, 5438355, 116, 458875, 5438355, 116, 458875, 5438350, 116];
// Returns [ 2, 3, 0, 0, 1, 2 ]
console.log(earcut(points, null, 3));
Yet this one returns nothing:
var earcut = require("earcut");
// x, y, height
var points = [458875, 5438355, 112, 458875, 5438350, 112, 458875, 5438350, 116, 458875, 5438355, 116, 458875, 5438355, 112];
// Returns []
console.log(earcut(points, null, 3));
From what I can see, the polygon that doesn't work is valid. The only difference being that it might be winding differently in 2D space (eg. by ignoring one of the axis), though that can't be controlled in 3D space.
Any ideas?
In preparation of porting this code to C++, it'd be cool to add type annotations to all variables, and especially parameters.
I haven't used it, but Flow might be a candidate syntax. Alternatively, TypeScript might be another one.
Simplification on polygons introduces minor self-intersections that can cause sliver triangles in the resulting triangulation. One thing that appears to improve results on data like this a lot is rejecting ears with points very close to them, not necessarily strictly inside the triangle. The trouble is coming up with a point-near-or-in-triangle test that is:
In rare cases the triangulation fails and appears to originate from the precision of the data sent to the earcut function.
Below is data for a simple ring with a hole which triangulates correctly:
[[143.129527283745121, 61.240160826593642, 12.157953862848911],
[147.399527283763751, 74.780160826630892, 12.157953862848911],
[154.049527283757931, 90.260160827077932, 12.157953862848911],
[174.429527283762581, 81.710160826332872, 12.157953862848911],
[168.03952728374861, 67.040160826407372, 12.157953862848911],
[159.099527283746281, 53.590160826221112, 12.157953862848911]],
[[156.85952728375561, 67.430160827003422, 12.157953862848911],
[157.489527283760251, 67.160160826519132, 12.157953862848911],
[159.969527283741631, 68.350160826928912, 12.157953862848911],
[161.339527283766071, 67.640160826966172, 12.157953862848911],
[159.649527283763751, 63.310160826891662, 12.157953862848911],
[155.759527283749781, 64.880160826258362, 12.157953862848911]]
]
Modifying the y-coordinate of the first ring point slightly (61.240160826593642 -> 61.240160826593640) produces incorrect triangles (tested with the triangulation test of earcut):
[[143.129527283745121, 61.240160826593640, 12.157953862848911],
[147.399527283763751, 74.780160826630892, 12.157953862848911],
[154.049527283757931, 90.260160827077932, 12.157953862848911],
[174.429527283762581, 81.710160826332872, 12.157953862848911],
[168.03952728374861, 67.040160826407372, 12.157953862848911],
[159.099527283746281, 53.590160826221112, 12.157953862848911]],
[[156.85952728375561, 67.430160827003422, 12.157953862848911],
[157.489527283760251, 67.160160826519132, 12.157953862848911],
[159.969527283741631, 68.350160826928912, 12.157953862848911],
[161.339527283766071, 67.640160826966172, 12.157953862848911],
[159.649527283763751, 63.310160826891662, 12.157953862848911],
[155.759527283749781, 64.880160826258362, 12.157953862848911]]
]
In the above case, the triangulation appears to deviate in the isEar function, around line 250, where in one case we have a value of t at -1.xxxe-13 and in the other at +1.xxxe-13 leading to different test results on (t >= 0).
Tested with version 1.4.0 of earcut.
It should be relatively easy to add. They'd be handled the same way as holes, with the only problem being that currently it would filter out the connection as collinear.
Hi there,
I understand earcut produces the triangles in cw winding order (I saw the thread to get ccw). However, obviously given the original geojson, the winding order doesn't guarantee the position of neighbouring triangles within the array (or am I mistaken? I'm thinking about cases where some triangles have only one or two neighbours vs three...)
What would be the quickest way to find the neighbouring triangles of a given triangle in the results array? short of obviously linearly running through the entire results...
Instead of outputting triangles as 3 vertices each, we could output unique vertices + list of indexes for triangles instead, like e.g. https://github.com/claus/libtess2.js/. This can save a lot of memory and vertex processing time when uploading vertices data to GL.
This library looks awesome, my only issue with it is the format the data input is in. Up until now we have been using PolyK
which has worked OK but is kind of slow and buggy.
I want to switch to this library but our data is a flat array of 2D coords ([x, y, x, y, x, y, ...]
) and I would have to convert it to the format used here in order to make it work with this lib. The GC churn that would be caused by creating so many array objects is not desired. Is there anyway for this library to support a flat-array of coords syntax?
Here's a bunch of OSM samples from @lbud with an Earcut error where the cause seems to be the same, a hole touching an outer ring.
https://gist.github.com/lbud/7371eb115344eb914a81
https://gist.github.com/lbud/717479a7743886c16199
https://gist.github.com/lbud/d4e2ccfd45b1c9435bd1
https://gist.github.com/lbud/de48ea431b6d2bfe192e
https://gist.github.com/lbud/9aecbc89dc949dc62d00
https://gist.github.com/lbud/8bf3f767f97fcff8e886
https://gist.github.com/lbud/785feed00fc58f3de1c7
https://gist.github.com/lbud/cbe6508faf1d092c9c0d
https://gist.github.com/lbud/02c00e32629768b10110
https://gist.github.com/lbud/ee6f62abb9696c464e56
https://gist.github.com/lbud/f003aadac93180fc28dc
https://gist.github.com/lbud/b9e1b83e64df5e1f9d11
https://gist.github.com/lbud/191bcf1a5d2712079fb8
https://gist.github.com/d57d0185442cffd68dbb
https://gist.github.com/a9e84efe8f3a7aace226
https://gist.github.com/9ca29f2e70f5f996194c
https://gist.github.com/57390cd817cb5237f9bc
https://gist.github.com/c6090ba2385ea5eb75f4
https://gist.github.com/71b4908bbbf07cace80c
https://gist.github.com/fa1056ac3be07dca5ba2
https://gist.github.com/d1b11e1009c7c786074c
https://gist.github.com/09e9b47ff90652f99ae5
https://gist.github.com/97314071aeff0b0d4f47
https://gist.github.com/34bc7f0b20f529b739d8
Awesome library. It would be fantastic to make this available as a bower package, too. Any plans for this?
While earcut is great for single polygon calculations, for multipolygon cases it could provide advanced API for more efficient working with Arrays:
all above is enabling to efficiently earcut hundreds of thousands polygons and passing the resulting arrays directly into the WebGL buffers.
I did that as experiment and saved hundreds of ms in total (for all polygons processing). Branch of this approach available here : https://github.com/Sumbera/earcut/tree/multipolygon
The sizes the triangles in result of earcut are uneven.
If I use them as NavMesh , are there some problems ?
Hey - I'm sorry I don't know if this package is still maintained - I have a 3d quad with the following vertices:
[
2.456295967102051,
1.5326589345932007,
0.5580052137374878,
2.3840434551239014,
1.6075363159179688,
0.5736544132232666,
2.3840434551239014,
1.6075363159179688,
0.4867267608642578,
2.456295967102051,
1.5326589345932007,
0.471077561378479
]
and many more such quads - ex.
[
2.8560659885406494,
0.7904728651046753,
0.4427383840084076,
2.8363993167877197,
0.8773361444473267,
0.45491600036621094,
2.8363993167877197,
0.8773361444473267,
0.36798834800720215,
2.8560659885406494,
0.7904728651046753,
0.3558107316493988
]
And earcut is returning an empty array after executing earcut(vertices, null, 3)
Some quads (non co-planar quads) it is returning at least one triangle - and I can correct this by adding the missing vertice to a triangle sharing an edge and all is fine - but I cannot solve the case where earcut is returning nothing - i would have to do the triangulation manually.
I really need to get this to work - or can someone point me to a triangulation library which works the same as earcut? It doesn't have to be fast at all - just produce a triangle list of 3d coordinates from a list of vertices - exactly the way earcut does it - i tried plntri but the examples are poor and cannot figure out a way to call the function for 3d coordinates - libtess seems super complicated i have no idea how to get it working - the example webpage is terribly confusing and not documented at all.
any help would be MUCH MUCH appreciated..
@mourner In the README.md
it is stated about the creation of indices:
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]}
But the current implementation creates indices which are a multiple of the passed-in dimension. For the given 2D
case it produces something like this: [2,0,4, 6,4,2]
. And passing in 3D
coords like this [[[10,0,0],[0,50,0],[60,60,0],[70,10,0]]]
it produces something like this: [3,0,6, 9,6,3]
.
Is this a bug in the description or a bug in the implementation? If you want to be able to upload the produced indices directly into a WebGL index buffer
, the implementation needs to be changed to follow the description given above. Right now, I need to divide each generated index by 2
or 3
(depending on the passed-in dimensionality of the passed-in vertices).
Here's a sample that results in an incorrect tessellation. Appears to be caused when there are two holes where one touches the outer ring and the other does not. Below is an example.
The first is the actual polygon (gray polygon, white holes), the second is it after running through Earcut, where the dark gray is overlap of triangles. The third is the same as the second except with each triangle having its edges highlighted.
Note it does not actually matter where the hole that is entirely enclosed is. The one that does touch the ring must be touching a vertex.
Vertices: [10,10, 25,10, 25,40, 10,40, 15,30, 20,35, 10,40, 15,15, 15,20, 20,15]
Hole Indicies: [4, 7]
Triangle Indices (result): [9,7,0, 0,7,8, 2,6,5, 4,6,0, 0,1,2, 5,4,0, 0,2,5]
Tile coords: 12/2261/1208
Geo coords: 14/59.1396/18.7855
Currentry:
module.exports = earcut;
Better:
if( typeof module !== 'undefined' && typeof module.exports !== 'undefined'){
module.exports = earcut;
}
From mapbox/earcut.hpp#14. Working on a reduced test case.
I have data sets that can contain duplicate vertices.
In this case the holes aren't handled correctly.
When I remove the duplicate vertices the holes are handled correctly.
It is possible to solve this by filtering out the duplicate vertices, but in some cases it would be useful to have the triangulation match the data set. (issue might be related to #52)
I've created an ESbin with example code
After rendering some vector-tiles with the new v2 specification, I found a few tiles with significant area deviations between their area and the earcut-calculated area.
Tile | Layer | Deviation | Validity failures |
---|---|---|---|
12,2244,1715 | contour | 253.64864864864865 | interior_rings_outside |
13,4817,4321 | contour | 241.72 | interior_rings_outside |
11,1556,777 | contour | 73 | interior_rings_outside |
12,3233,1464 | contour | 31.794736842105262 | interior_rings_outside |
12,1988,1777 | contour | 27.457142857142856 | interior_rings_outside |
14,5587,8896 | contour | 13.777889723392562 | interior_rings_outside |
11,1492,861 | contour | 10.678260869565218 | self_intersections_method_t |
These are just initial test results, but should be a good way to find patterns that could point to the source of area differences - either in invalid geometries or earcut edge cases.
cc/ @mourner @flippmoke
Coords: [10, 10, 610, 10, 610, 610, 10, 610]
HoleIndices: [50, 50, 150, 50, 150, 150, 50, 150]
numDimensions: 2
Eracut is returning an empty result for the above data set and both are rectangle vertices.
const outer = [0,0, 100,0, 100,100, 0,100];
const holes = [60,0, 80,0, 80,50, 60,50, 20,0, 40,0, 40,50, 20,50];
const conc = outer.concat(inner);
earcut(conc, [4])
printout => [3, 0, 11, 2, 3, 11, 2, 11, 10, 10, 9, 7, 4, 11, 0, 2, 10, 7, 2, 7, 6, 1, 2, 6, 1, 6, 5]
I am using [email protected]. could't find out why this one not working, all my outer and holes are anticlockwise.
When we reach a point where we can't find any valid ears to cut off (usually when there are self-intersections left), we proceed to polygon splitting routine which tries to find a valid diagonal. This step is very expensive โ it's O(n^3)
worst-case.
Polygons like OSM water contain a lot of small local self-intersections where edge (i-1,i) intersects edge (i+1,i+2). All these can be detected and cured much faster (O(n)
in one pass) before we resort to diagonal search.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.