Subtracting triangle from rectangle with WindingRule.Positive does not work as expected

[sqeezy]

While using this awesome library me and my team came across this problem. The code is taken from a unit test that reproduces the issue. Executable code can be found under [TesselationProblemExample].(https://github.com/sqeezy/TesselationProblemExample).
LibTessDotNet.Double was used for this example.

var tess = new Tess();
ContourOrientation positiveOrientation = ContourOrientation.Clockwise;
ContourOrientation negativeOrientation = ContourOrientation.CounterClockwise;

ContourVertex a = new(new Vec3(-48.13525763898019, -4.495359229766127E-14, 0));
ContourVertex b = new(new Vec3(-48.135257638980185, -27.24424809648011, 0));
ContourVertex c = new(new Vec3(47.367221005276186, -27.24424809648011, 0));
ContourVertex d = new(new Vec3(47.36722100527618, -4.495359229766127E-14, 0));

ContourVertex f = new(new Vec3(-34.571100634798604, -4.459276981465809E-14, 0));
ContourVertex e = new(new Vec3(-48.13525763898021, -11.279901577469582, 0));

var positiveRectangle = new List<ContourVertex> { a, b, c, d };
var negativeTriangle = new List<ContourVertex> { a, f, e };

tess.AddContour(positiveRectangle, positiveOrientation);
tess.AddContour(negativeTriangle, negativeOrientation);
tess.Tessellate(WindingRule.Positive, ElementType.Polygons, 3, (_, _, _) => null, new Vec3(0, 0, 1));

// The result contains the 4 vertices of positiveRectangle. Expected would be that the shared point 'a' is removed and 'e' and 'f' are added
Assert.Equal(5, tess.Vertices.Length);
// For a polygon of 5 vertices, three triangles would be expected
Assert.Equal(3, tess.ElementCount);
// The shared corner should be removed but isn't
Assert.DoesNotContain(a, tess.Vertices);

I could not think of a reason why this operation does not work as expected. Even if some points of the triangle are outside of the rectangle, the shape should never be ignored completely.

[KellanHiggins]

Does this library support doubles? 4.495359229766127E-14 is basically zero but still isn't. Floating point numbers are a pain.

[sqeezy]

Does this library support doubles? 4.495359229766127E-14 is basically zero but still isn't. Floating point numbers are a pain.

Yes, there is a LibTessDotNet.Double which I actually used for this example. Thanks for mentioning this aspect. I will add this information to the original issue.

[sqeezy]

Me and my company would be very much up helping/sponsoring in fixing this problem. It actually posses a proper issue for us.
It seems to me that it's highly inefficient for one of us to get familiar with the inner workings of the algorithm if it might be a small issue.

[DanielLorrig]

I think I came accross some similiar issues and it was something about the way the passed orientation is handled. I ended up orientating all my polygons before passing them into the Tess object and then just pass them with ContourOrientation.Original.

[sqeezy]

@DanielLorrig I tried this and sadly it did not work.

[DanielLorrig]

I took your vertices and converted them to float (as my wrapper class only works with floats)

Rearranged the order of the vertices so that the rectangle is counterclockwise and the triangle is cw.

Passed all of the contours with "ContourOrientation.Original" to libtess.

The result is as expected - vertex a is not in the list anymore. Now the only difference that comes to my mind is that I used floats instead of doubles. Have you tried using floats and if so were your results the same?