Does the winding of input edges matter?

[aallfik11]

Hello! I've been using this library a bit, and it works really well. I was usually using polygons that always had the edges wound in the same way and in order(for example: v0->v1, v1->v2, v2->v3 etc). However, for my use case (I'm using this in unreal engine to triangulate some mesh slices) I decided that it might be better to supply a full array of randomly-ordered edges (random both in winding and the general order, so they can be something like v0->v1, v2->v1, v4->v3, v2->v3...) that I get after slicing a mesh, becase unreal's FGeomTools way of building a polygon from a set of these edges resulted in unsatisfactory polygons (or their complete lack) in some cases. Unfortunately, when supplying the data, eraseOuterTriangles seemed to result in erasure of all or almost all of the geometry, and the winding of the edges is the only culprit I can think of. Some of them were intersecting, but I thought that with a proper CDT::Triangulation constructor option they would be a non-issue.

[artem-ogre]

Could you provide a minimal reproducible example?

[aallfik11]

Ok I prepared some data, here it is (sorry for the long line of code, as I said before, I tried coming up with something more minimal but failed, I'm still new to computational geometry topics). These are before removing duplicates and remapping. I tested it and it does result in holes

std::vector<CDT::V2d<double>> Points = {{126.792455, -15.963761}, {127.048560, -15.160240}, {127.068805, -15.092582}, {127.048560, -15.160240}, {126.792455, -15.963761}, {126.770462, -16.126247}, {126.770462, -16.126247}, {126.654568, -16.794991}, {126.653431, -17.112746}, {126.654568, -16.794991}, {130.279944, -22.628960}, {130.488462, -22.691769}, {130.642700, -22.703213}, {130.488462, -22.691769}, {131.658778, -23.015317}, {131.728357, -23.008943}, {131.646793, -23.015204}, {131.658778, -23.015317}, {131.646793, -23.015204}, {131.134521, -22.811506}, {130.642700, -22.703213}, {131.134521, -22.811506}, {127.462657, -14.276936}, {127.077490, -15.074620}, {127.068805, -15.092582}, {127.077490, -15.074620}, {127.678021, -13.940198}, {127.962377, -13.521991}, {127.678021, -13.940198}, {127.462657, -14.276936}, {128.503583, -12.853568}, {127.962377, -13.521991}, {128.503583, -12.853568}, {128.519743, -12.835624}, {128.547871, -12.807290}, {129.108643, -12.149856}, {128.519743, -12.835624}, {128.547871, -12.807290}, {129.108643, -12.149856}, {129.547562, -11.768390}, {129.547562, -11.768390}, {129.764471, -11.584854}, {129.764471, -11.584854}, {130.180221, -11.353168}, {134.237922, -12.125794}, {134.023696, -11.900388}, {134.904466, -12.941684}, {134.631241, -12.539966}, {134.237922, -12.125794}, {134.631241, -12.539966}, {133.567879, -11.585830}, {134.023696, -11.900388}, {133.361286, -11.439707}, {133.567879, -11.585830}, {132.899276, -11.242657}, {133.361286, -11.439707}, {132.899276, -11.242657}, {132.662822, -11.147036}, {132.367820, -11.089960}, {132.662822, -11.147036}, {131.936960, -11.002299}, {132.367820, -11.089960}, {131.518735, -11.015918}, {131.936960, -11.002299}, {131.518735, -11.015918}, {131.198891, -11.023239}, {130.585423, -11.176115}, {131.198891, -11.023239}, {130.585423, -11.176115}, {130.468679, -11.204906}, {130.468679, -11.204906}, {130.180221, -11.353168}, {134.904466, -12.941684}, {135.179552, -13.349231}, {135.179552, -13.349231}, {135.510303, -14.027637}, {135.640589, -14.301534}, {135.510303, -14.027637}, {135.706016, -14.506188}, {135.640589, -14.301534}, {135.706016, -14.506188}, {135.966623, -15.312757}, {135.966623, -15.312757}, {135.971361, -15.339055}, {135.971361, -15.339055}, {135.993254, -15.467302}, {135.993254, -15.467301}, {136.124660, -16.213962}, {136.124660, -16.213962}, {136.144880, -16.327042}, {136.144880, -16.327042}, {136.169131, -17.046903}, {136.169131, -17.046903}, {136.175510, -17.276534}, {136.087487, -17.975515}, {136.175510, -17.276534}, {136.087487, -17.975515}, {136.040436, -18.329654}, {135.885848, -18.829977}, {136.040436, -18.329654}, {135.885848, -18.829977}, {135.748533, -19.276983}, {135.374529, -20.003117}, {135.748533, -19.276983}, {134.916000, -20.661528}, {134.729290, -20.927516}, {134.729290, -20.927516}, {134.685654, -20.981481}, {135.374529, -20.003117}, {135.286505, -20.171978}, {134.916000, -20.661528}, {135.286505, -20.171978}, {134.685654, -20.981482}, {134.185920, -21.499128}, {134.063700, -21.642871}, {134.185920, -21.499128}, {134.063700, -21.642871}, {133.751424, -21.928303}, {133.653728, -22.135945}, {133.751424, -21.928303}, {133.653728, -22.135945}, {133.597621, -22.338729}, {133.387764, -22.446493}, {133.597621, -22.338729}, {133.258768, -22.525341}, {133.387764, -22.446493}, {133.010797, -22.627657}, {133.258768, -22.525341}, {132.583469, -22.783178}, {132.895928, -22.660615}, {133.010797, -22.627657}, {132.895928, -22.660615}, {132.583469, -22.783178}, {132.507631, -22.805326}, {132.143535, -22.930948}, {132.507631, -22.805326}, {132.106511, -22.941516}, {132.143535, -22.930948}, {131.728357, -23.008943}, {132.106511, -22.941516}, {130.279944, -22.628960}, {129.819558, -22.505917}, {129.538841, -22.361875}, {129.819558, -22.505917}, {129.538841, -22.361875}, {129.182931, -22.186752}, {128.868957, -21.952199}, {129.182931, -22.186752}, {128.868957, -21.952199}, {128.588249, -21.750240}, {128.254389, -21.420031}, {128.588249, -21.750240}, {128.023025, -21.194855}, {128.254389, -21.420031}, {127.706609, -20.774197}, {128.023025, -21.194855}, {127.706609, -20.774197}, {127.506551, -20.512327}, {127.238437, -20.000235}, {127.506551, -20.512327}, {127.238437, -20.000235}, {127.066667, -19.669645}, {126.899207, -19.123338}, {127.066667, -19.669645}, {126.899207, -19.123338}, {126.771883, -18.693594}, {126.702062, -18.209115}, {126.771883, -18.693594}, {126.702062, -18.209115}, {126.635907, -17.696764}, {126.653431, -17.112746}, {126.635907, -17.696764}};


std::vector<CDT::Edge> Edges = {{0, 1}, {2, 3}, {4, 5}, {6, 7}, {8, 9}, {10, 11}, {12, 13}, {14, 15}, {16, 17}, {18, 19}, {20, 21}, {22, 23}, {24, 25}, {26, 27}, {28, 29}, {30, 31}, {32, 33}, {34, 35}, {36, 37}, {38, 39}, {40, 41}, {42, 43}, {44, 45}, {46, 47}, {48, 49}, {50, 51}, {52, 53}, {54, 55}, {56, 57}, {58, 59}, {60, 61}, {62, 63}, {64, 65}, {66, 67}, {68, 69}, {70, 71}, {72, 73}, {74, 75}, {76, 77}, {78, 79}, {80, 81}, {82, 83}, {84, 85}, {86, 87}, {88, 89}, {90, 91}, {92, 93}, {94, 95}, {96, 97}, {98, 99}, {100, 101}, {102, 103}, {104, 105}, {106, 107}, {108, 109}, {110, 111}, {112, 113}, {114, 115}, {116, 117}, {118, 119}, {120, 121}, {122, 123}, {124, 125}, {126, 127}, {128, 129}, {130, 131}, {132, 133}, {134, 135}, {136, 137}, {138, 139}, {140, 141}, {142, 143}, {144, 145}, {146, 147}, {148, 149}, {150, 151}, {152, 153}, {154, 155}, {156, 157}, {158, 159}, {160, 161}, {162, 163}, {164, 165}, {166, 167}, {168, 169}, {170, 171}};

[aallfik11]

It seems that the holes were my fault, as my visualisation code wasn't working as expected. However, for the data set I've given, it still seems that the removeOuterTriangles() function results in removal of all triangles

[artem-ogre]

Thank you! I will try to take a look within next few days if I get some time.

[artem-ogre]

Hi, Adam,

To answer the original question: edges direction does not matter: edge 1 -> 2 is same as edge 2 -> 1.

I looked at your input: the boundary is not watertight (see images below).
Also here's the input that CDT visualizer can open, so you can take a look yourself if you would like to:
discussion-186.txt

[aallfik11]

Thanks for the response! Sorry for the late reply, I shifted my focus to developing some other parts of my game and it slipped my mind. I really appreciate your help. Guess I'll have to figure out a way to make my edges watertight and nice