Comments (5)
Yeah, filtering fixes some really nasty degenerate cases for the algorithm. You can check this yourself by adding return start
in the filterPoints
function so that it does nothing and then running the tests — a lot of them will break hard.
Can you describe in more detail why you can't use triangles on filtered points? Even if unfiltered points set is used for something else, the fact the triangles don't use the colinear vertices won't make a visual difference, right?
from earcut.
I think about adopting earcut for https://github.com/x3dom/x3dom which currently uses very basic earclipping to triangulate polygons. The main use case I see is extrusions where earclipping is used to fill end caps but the sides are triangulated/connected independently. Also it is just good practice to preserve as much as possible of the input and to have no surprises.
Here is a current PR x3dom/x3dom#577 which provides some context.
from earcut.
Ah, I see — makes sense. I pushed a branch (less-filtering
) where filtering colinear/duplicate points doesn't happen unless we can't find a valid ear to clip. Please try it in x3dom and see if it works correctly.
This improves performance and fixes this issue but may (or may not) lead to some unhandled edge cases, although we can assume it won't cause any trouble until we find a test case that does.
BTW, what do you think about adjacent duplicate (not just colinear) points? Can we remove them safely by default?
from earcut.
Thanks ! It may be a while since in x3dom earclip function consumers provide their own linked list but I will give adopting earcut.js a try. Also, the x3dom developers have a policy to not include or rely on external libraries but for a small one perhaps after some streamlining (hole support not really required, perhaps not even the cool hashing) it would be a case of absorbing it which is probably acceptable. The copyright notice would be always retained.
Having adjacent duplicate points would generally indicate some issue during generation of the polygon but it may happen for some automated procedures. Since zero area triangles are accepted for the sides of an extrusion, again filtering out these out would lead to a mesh with zero area holes and rendering artefacts. But in this case, it may be beneficial as an indicator that the polygon has a problem. So, if possible it would be better to not filter but if necessary it should be done, similar to the colinear cases.
BTW, these Hilbert curves may make good test polygons since they have a lot of reflexes and may hit numerical corner cases. They also have colinear segments.
Here are the vertices of a level 5 one:
[[0 0] [-1 0] [-1 -1] [0 -1] [0 -2] [0 -3] [-1 -3] [-1 -2] [-2 -2] [-2 -3] [-3 -3] [-3 -2] [-3 -1] [-2 -1] [-2 0] [-3 0] [-4 0] [-4 -1] [-5 -1] [-5 0] [-6 0] [-7 0] [-7 -1] [-6 -1] [-6 -2] [-7 -2] [-7 -3] [-6 -3] [-5 -3] [-5 -2] [-4 -2] [-4 -3] [-4 -4] [-4 -5] [-5 -5] [-5 -4] [-6 -4] [-7 -4] [-7 -5] [-6 -5] [-6 -6] [-7 -6] [-7 -7] [-6 -7] [-5 -7] [-5 -6] [-4 -6] [-4 -7] [-3 -7] [-2 -7] [-2 -6] [-3 -6] [-3 -5] [-3 -4] [-2 -4] [-2 -5] [-1 -5] [-1 -4] [0 -4] [0 -5] [0 -6] [-1 -6] [-1 -7] [0 -7] [0 -8] [0 -9] [-1 -9] [-1 -8] [-2 -8] [-3 -8] [-3 -9] [-2 -9] [-2 -10] [-3 -10] [-3 -11] [-2 -11] [-1 -11] [-1 -10] [0 -10] [0 -11] [0 -12] [-1 -12] [-1 -13] [0 -13] [0 -14] [0 -15] [-1 -15] [-1 -14] [-2 -14] [-2 -15] [-3 -15] [-3 -14] [-3 -13] [-2 -13] [-2 -12] [-3 -12] [-4 -12] [-5 -12] [-5 -13] [-4 -13] [-4 -14] [-4 -15] [-5 -15] [-5 -14] [-6 -14] [-6 -15] [-7 -15] [-7 -14] [-7 -13] [-6 -13] [-6 -12] [-7 -12] [-7 -11] [-7 -10] [-6 -10] [-6 -11] [-5 -11] [-4 -11] [-4 -10] [-5 -10] [-5 -9] [-4 -9] [-4 -8] [-5 -8] [-6 -8] [-6 -9] [-7 -9] [-7 -8] [-8 -8] [-8 -9] [-9 -9] [-9 -8] [-10 -8] [-11 -8] [-11 -9] [-10 -9] [-10 -10] [-11 -10] [-11 -11] [-10 -11] [-9 -11] [-9 -10] [-8 -10] [-8 -11] [-8 -12] [-9 -12] [-9 -13] [-8 -13] [-8 -14] [-8 -15] [-9 -15] [-9 -14] [-10 -14] [-10 -15] [-11 -15] [-11 -14] [-11 -13] [-10 -13] [-10 -12] [-11 -12] [-12 -12] [-13 -12] [-13 -13] [-12 -13] [-12 -14] [-12 -15] [-13 -15] [-13 -14] [-14 -14] [-14 -15] [-15 -15] [-15 -14] [-15 -13] [-14 -13] [-14 -12] [-15 -12] [-15 -11] [-15 -10] [-14 -10] [-14 -11] [-13 -11] [-12 -11] [-12 -10] [-13 -10] [-13 -9] [-12 -9] [-12 -8] [-13 -8] [-14 -8] [-14 -9] [-15 -9] [-15 -8] [-15 -7] [-14 -7] [-14 -6] [-15 -6] [-15 -5] [-15 -4] [-14 -4] [-14 -5] [-13 -5] [-13 -4] [-12 -4] [-12 -5] [-12 -6] [-13 -6] [-13 -7] [-12 -7] [-11 -7] [-11 -6] [-10 -6] [-10 -7] [-9 -7] [-8 -7] [-8 -6] [-9 -6] [-9 -5] [-8 -5] [-8 -4] [-9 -4] [-10 -4] [-10 -5] [-11 -5] [-11 -4] [-11 -3] [-11 -2] [-10 -2] [-10 -3] [-9 -3] [-8 -3] [-8 -2] [-9 -2] [-9 -1] [-8 -1] [-8 0] [-9 0] [-10 0] [-10 -1] [-11 -1] [-11 0] [-12 0] [-13 0] [-13 -1] [-12 -1] [-12 -2] [-12 -3] [-13 -3] [-13 -2] [-14 -2] [-14 -3] [-15 -3] [-15 -2] [-15 -1] [-14 -1] [-14 0] [-15 0] [-16 0] [-16 -1] [-17 -1] [-17 0] [-18 0] [-19 0] [-19 -1] [-18 -1] [-18 -2] [-19 -2] [-19 -3] [-18 -3] [-17 -3] [-17 -2] [-16 -2] [-16 -3] [-16 -4] [-17 -4] [-17 -5] [-16 -5] [-16 -6] [-16 -7] [-17 -7] [-17 -6] [-18 -6] [-18 -7] [-19 -7] [-19 -6] [-19 -5] [-18 -5] [-18 -4] [-19 -4] [-20 -4] [-21 -4] [-21 -5] [-20 -5] [-20 -6] [-20 -7] [-21 -7] [-21 -6] [-22 -6] [-22 -7] [-23 -7] [-23 -6] [-23 -5] [-22 -5] [-22 -4] [-23 -4] [-23 -3] [-23 -2] [-22 -2] [-22 -3] [-21 -3] [-20 -3] [-20 -2] [-21 -2] [-21 -1] [-20 -1] [-20 0] [-21 0] [-22 0] [-22 -1] [-23 -1] [-23 0] [-24 0] [-25 0] [-25 -1] [-24 -1] [-24 -2] [-24 -3] [-25 -3] [-25 -2] [-26 -2] [-26 -3] [-27 -3] [-27 -2] [-27 -1] [-26 -1] [-26 0] [-27 0] [-28 0] [-28 -1] [-29 -1] [-29 0] [-30 0] [-31 0] [-31 -1] [-30 -1] [-30 -2] [-31 -2] [-31 -3] [-30 -3] [-29 -3] [-29 -2] [-28 -2] [-28 -3] [-28 -4] [-28 -5] [-29 -5] [-29 -4] [-30 -4] [-31 -4] [-31 -5] [-30 -5] [-30 -6] [-31 -6] [-31 -7] [-30 -7] [-29 -7] [-29 -6] [-28 -6] [-28 -7] [-27 -7] [-26 -7] [-26 -6] [-27 -6] [-27 -5] [-27 -4] [-26 -4] [-26 -5] [-25 -5] [-25 -4] [-24 -4] [-24 -5] [-24 -6] [-25 -6] [-25 -7] [-24 -7] [-24 -8] [-25 -8] [-25 -9] [-24 -9] [-24 -10] [-24 -11] [-25 -11] [-25 -10] [-26 -10] [-26 -11] [-27 -11] [-27 -10] [-27 -9] [-26 -9] [-26 -8] [-27 -8] [-28 -8] [-28 -9] [-29 -9] [-29 -8] [-30 -8] [-31 -8] [-31 -9] [-30 -9] [-30 -10] [-31 -10] [-31 -11] [-30 -11] [-29 -11] [-29 -10] [-28 -10] [-28 -11] [-28 -12] [-28 -13] [-29 -13] [-29 -12] [-30 -12] [-31 -12] [-31 -13] [-30 -13] [-30 -14] [-31 -14] [-31 -15] [-30 -15] [-29 -15] [-29 -14] [-28 -14] [-28 -15] [-27 -15] [-26 -15] [-26 -14] [-27 -14] [-27 -13] [-27 -12] [-26 -12] [-26 -13] [-25 -13] [-25 -12] [-24 -12] [-24 -13] [-24 -14] [-25 -14] [-25 -15] [-24 -15] [-23 -15] [-23 -14] [-22 -14] [-22 -15] [-21 -15] [-20 -15] [-20 -14] [-21 -14] [-21 -13] [-20 -13] [-20 -12] [-21 -12] [-22 -12] [-22 -13] [-23 -13] [-23 -12] [-23 -11] [-22 -11] [-22 -10] [-23 -10] [-23 -9] [-23 -8] [-22 -8] [-22 -9] [-21 -9] [-21 -8] [-20 -8] [-20 -9] [-20 -10] [-21 -10] [-21 -11] [-20 -11] [-19 -11] [-18 -11] [-18 -10] [-19 -10] [-19 -9] [-19 -8] [-18 -8] [-18 -9] [-17 -9] [-17 -8] [-16 -8] [-16 -9] [-16 -10] [-17 -10] [-17 -11] [-16 -11] [-16 -12] [-16 -13] [-17 -13] [-17 -12] [-18 -12] [-19 -12] [-19 -13] [-18 -13] [-18 -14] [-19 -14] [-19 -15] [-18 -15] [-17 -15] [-17 -14] [-16 -14] [-16 -15] [-16 -16] [-16 -17] [-17 -17] [-17 -16] [-18 -16] [-19 -16] [-19 -17] [-18 -17] [-18 -18] [-19 -18] [-19 -19] [-18 -19] [-17 -19] [-17 -18] [-16 -18] [-16 -19] [-16 -20] [-17 -20] [-17 -21] [-16 -21] [-16 -22] [-16 -23] [-17 -23] [-17 -22] [-18 -22] [-18 -23] [-19 -23] [-19 -22] [-19 -21] [-18 -21] [-18 -20] [-19 -20] [-20 -20] [-21 -20] [-21 -21] [-20 -21] [-20 -22] [-20 -23] [-21 -23] [-21 -22] [-22 -22] [-22 -23] [-23 -23] [-23 -22] [-23 -21] [-22 -21] [-22 -20] [-23 -20] [-23 -19] [-23 -18] [-22 -18] [-22 -19] [-21 -19] [-20 -19] [-20 -18] [-21 -18] [-21 -17] [-20 -17] [-20 -16] [-21 -16] [-22 -16] [-22 -17] [-23 -17] [-23 -16] [-24 -16] [-25 -16] [-25 -17] [-24 -17] [-24 -18] [-24 -19] [-25 -19] [-25 -18] [-26 -18] [-26 -19] [-27 -19] [-27 -18] [-27 -17] [-26 -17] [-26 -16] [-27 -16] [-28 -16] [-28 -17] [-29 -17] [-29 -16] [-30 -16] [-31 -16] [-31 -17] [-30 -17] [-30 -18] [-31 -18] [-31 -19] [-30 -19] [-29 -19] [-29 -18] [-28 -18] [-28 -19] [-28 -20] [-28 -21] [-29 -21] [-29 -20] [-30 -20] [-31 -20] [-31 -21] [-30 -21] [-30 -22] [-31 -22] [-31 -23] [-30 -23] [-29 -23] [-29 -22] [-28 -22] [-28 -23] [-27 -23] [-26 -23] [-26 -22] [-27 -22] [-27 -21] [-27 -20] [-26 -20] [-26 -21] [-25 -21] [-25 -20] [-24 -20] [-24 -21] [-24 -22] [-25 -22] [-25 -23] [-24 -23] [-24 -24] [-25 -24] [-25 -25] [-24 -25] [-24 -26] [-24 -27] [-25 -27] [-25 -26] [-26 -26] [-26 -27] [-27 -27] [-27 -26] [-27 -25] [-26 -25] [-26 -24] [-27 -24] [-28 -24] [-28 -25] [-29 -25] [-29 -24] [-30 -24] [-31 -24] [-31 -25] [-30 -25] [-30 -26] [-31 -26] [-31 -27] [-30 -27] [-29 -27] [-29 -26] [-28 -26] [-28 -27] [-28 -28] [-28 -29] [-29 -29] [-29 -28] [-30 -28] [-31 -28] [-31 -29] [-30 -29] [-30 -30] [-31 -30] [-31 -31] [-30 -31] [-29 -31] [-29 -30] [-28 -30] [-28 -31] [-27 -31] [-26 -31] [-26 -30] [-27 -30] [-27 -29] [-27 -28] [-26 -28] [-26 -29] [-25 -29] [-25 -28] [-24 -28] [-24 -29] [-24 -30] [-25 -30] [-25 -31] [-24 -31] [-23 -31] [-23 -30] [-22 -30] [-22 -31] [-21 -31] [-20 -31] [-20 -30] [-21 -30] [-21 -29] [-20 -29] [-20 -28] [-21 -28] [-22 -28] [-22 -29] [-23 -29] [-23 -28] [-23 -27] [-22 -27] [-22 -26] [-23 -26] [-23 -25] [-23 -24] [-22 -24] [-22 -25] [-21 -25] [-21 -24] [-20 -24] [-20 -25] [-20 -26] [-21 -26] [-21 -27] [-20 -27] [-19 -27] [-18 -27] [-18 -26] [-19 -26] [-19 -25] [-19 -24] [-18 -24] [-18 -25] [-17 -25] [-17 -24] [-16 -24] [-16 -25] [-16 -26] [-17 -26] [-17 -27] [-16 -27] [-16 -28] [-16 -29] [-17 -29] [-17 -28] [-18 -28] [-19 -28] [-19 -29] [-18 -29] [-18 -30] [-19 -30] [-19 -31] [-18 -31] [-17 -31] [-17 -30] [-16 -30] [-16 -31] [-15 -31] [-14 -31] [-14 -30] [-15 -30] [-15 -29] [-15 -28] [-14 -28] [-14 -29] [-13 -29] [-13 -28] [-12 -28] [-12 -29] [-12 -30] [-13 -30] [-13 -31] [-12 -31] [-11 -31] [-11 -30] [-10 -30] [-10 -31] [-9 -31] [-8 -31] [-8 -30] [-9 -30] [-9 -29] [-8 -29] [-8 -28] [-9 -28] [-10 -28] [-10 -29] [-11 -29] [-11 -28] [-11 -27] [-11 -26] [-10 -26] [-10 -27] [-9 -27] [-8 -27] [-8 -26] [-9 -26] [-9 -25] [-8 -25] [-8 -24] [-9 -24] [-10 -24] [-10 -25] [-11 -25] [-11 -24] [-12 -24] [-13 -24] [-13 -25] [-12 -25] [-12 -26] [-12 -27] [-13 -27] [-13 -26] [-14 -26] [-14 -27] [-15 -27] [-15 -26] [-15 -25] [-14 -25] [-14 -24] [-15 -24] [-15 -23] [-15 -22] [-14 -22] [-14 -23] [-13 -23] [-12 -23] [-12 -22] [-13 -22] [-13 -21] [-12 -21] [-12 -20] [-13 -20] [-14 -20] [-14 -21] [-15 -21] [-15 -20] [-15 -19] [-14 -19] [-14 -18] [-15 -18] [-15 -17] [-15 -16] [-14 -16] [-14 -17] [-13 -17] [-13 -16] [-12 -16] [-12 -17] [-12 -18] [-13 -18] [-13 -19] [-12 -19] [-11 -19] [-10 -19] [-10 -18] [-11 -18] [-11 -17] [-11 -16] [-10 -16] [-10 -17] [-9 -17] [-9 -16] [-8 -16] [-8 -17] [-8 -18] [-9 -18] [-9 -19] [-8 -19] [-8 -20] [-8 -21] [-9 -21] [-9 -20] [-10 -20] [-11 -20] [-11 -21] [-10 -21] [-10 -22] [-11 -22] [-11 -23] [-10 -23] [-9 -23] [-9 -22] [-8 -22] [-8 -23] [-7 -23] [-7 -22] [-6 -22] [-6 -23] [-5 -23] [-4 -23] [-4 -22] [-5 -22] [-5 -21] [-4 -21] [-4 -20] [-5 -20] [-6 -20] [-6 -21] [-7 -21] [-7 -20] [-7 -19] [-6 -19] [-6 -18] [-7 -18] [-7 -17] [-7 -16] [-6 -16] [-6 -17] [-5 -17] [-5 -16] [-4 -16] [-4 -17] [-4 -18] [-5 -18] [-5 -19] [-4 -19] [-3 -19] [-2 -19] [-2 -18] [-3 -18] [-3 -17] [-3 -16] [-2 -16] [-2 -17] [-1 -17] [-1 -16] [0 -16] [0 -17] [0 -18] [-1 -18] [-1 -19] [0 -19] [0 -20] [0 -21] [-1 -21] [-1 -20] [-2 -20] [-3 -20] [-3 -21] [-2 -21] [-2 -22] [-3 -22] [-3 -23] [-2 -23] [-1 -23] [-1 -22] [0 -22] [0 -23] [0 -24] [-1 -24] [-1 -25] [0 -25] [0 -26] [0 -27] [-1 -27] [-1 -26] [-2 -26] [-2 -27] [-3 -27] [-3 -26] [-3 -25] [-2 -25] [-2 -24] [-3 -24] [-4 -24] [-4 -25] [-5 -25] [-5 -24] [-6 -24] [-7 -24] [-7 -25] [-6 -25] [-6 -26] [-7 -26] [-7 -27] [-6 -27] [-5 -27] [-5 -26] [-4 -26] [-4 -27] [-4 -28] [-4 -29] [-5 -29] [-5 -28] [-6 -28] [-7 -28] [-7 -29] [-6 -29] [-6 -30] [-7 -30] [-7 -31] [-6 -31] [-5 -31] [-5 -30] [-4 -30] [-4 -31] [-3 -31] [-2 -31] [-2 -30] [-3 -30] [-3 -29] [-3 -28] [-2 -28] [-2 -29] [-1 -29] [-1 -28] [0 -28] [0 -29] [0 -30] [-1 -30] [-1 -31] [0 -31] [1 -31] [1 0] [0 0]]
from earcut.
@andreasplesch great, thanks! I'll think about merging that branch and making a release then (including your test case too).
from earcut.
Related Issues (20)
- This my test data, will wrong.
- Another infinite loop
- Bug with vertical object in 3dim space HOT 1
- The result of dividing a plane triangle is [] HOT 2
- Triangle out of contour
- Failure with simple case in 3D HOT 2
- Another infinite loop, bridge node gets filtered out but still referenced HOT 3
- Update readme to clarify if vertices are output in clockwise or counterclockwise order. HOT 4
- Is it acceptable for bridges to cross holes? HOT 3
- wrong triangulation HOT 1
- Bad triangulation with disjoint hole HOT 3
- Triangulation error
- Bug: Incorrect triangulation
- Typescript or JSDoc HOT 4
- Does the triangulation consider only 2 dimensions? HOT 1
- How do I use a polygon with Steiner points HOT 2
- Provide appropriate full examples HOT 2
- Incorrect triangulation with a shape in a hole HOT 1
- Trouble Understanding Earcut's Polygon Interpretation
- Triangulation result is different from expectation HOT 2
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from earcut.