preserve colinear segments

[andreasplesch]

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 ?

[mourner]

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?

[andreasplesch]

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.

[mourner]

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?

[andreasplesch]

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]]

[mourner]

@andreasplesch great, thanks! I'll think about merging that branch and making a release then (including your test case too).