compareSegments does not sort correctly

[Fribur]

While working on issue #8 (I think I got a fairly simple solution which I will post under issue 8 once final), I noticed compareSegments is not sorting correctly, and think for clarity this warrants this dedicated issue. In fact the credit for discovering this bug and finding a solution goes all to Lior Sinai.

The correct comparer (copy and paste from my C# implementation):

public struct EventSegmentComparer : IComparer<EventBool>
{
    //assumes segments are already sorted by x coordinate (seg1 is on x-axis before seg2)
    /// <summary> Sorts events in DESCENDING order on y-axis </summary>
    /// <returns>Returns 1 if eventA is smaller, -1 if bEvent is smaller, 0 if equal </returns>
    public int Compare(EventBool eventA, EventBool eventB)
    {
        Segment seg1 = eventA.seg;
        Segment seg2 = eventB.seg;
        var a = seg1.p0_start;
        var b = seg1.p1_end;
        var c = seg2.p0_start;
        var d = seg2.p1_end;
        if (PointUtils.IsCollinear(c, b, a, out double orient2d))
            return PointUtils.IsAboveOrOn(a, b, d) < 0 ? -1 : 1;
        if (c.x < a.x)
            return PointUtils.IsAboveOrOn(c, d, a) >= 0 ? -1 : 1;
        else
            return PointUtils.IsAboveOrOn(a, b, c) < 0 ? -1 : 1;
    }
}

Helper methods:

/// <summary>
/// Returns a positive value if the points a, b, and p occur in counterclockwise order (CCW, p lies to the left of the directed line defined by points a and b).
/// Returns a negative value if they occur in clockwise order(CW, p lies to the right of the directed line ab).
/// Returns zero if they are collinear.
/// Result also happens to be twice the signed area of the triangle
/// </summary>  
public static double Orient2DFast(double2 a, double2 b, double2 p)
{
    return (a.x - p.x) * (b.y - p.y) - (a.y - p.y) * (b.x - p.x);
}

public static bool IsCollinear(double2 a, double2 b, double2 p, out double orient2d)
{
    orient2d = Orient2DFast(a, b, p);
    return math.abs(orient2d) < epsilon1;
}

public static double IsAboveOrOn(double2 a, double2 b, double2 p)
{
    if(GenericEquals(b.x, a.x))
        return p.y >= math.max(a.y, b.y) ? 1 : -1;

    var orient2d = Orient2DFast(a, b, p);
    return orient2d;
}

/// <summary>Tolerance comparison for large and small values. https://realtimecollisiondetection.net/blog/?p=89</summary>
public static bool GenericEquals(double x, double y)
{
    return math.abs(x - y) <= math.max(epsilon1, relativeTolerance * math.max(math.abs(x), math.abs(y)));
}

public const float epsilon1   = 0.000002f; //next representable float at 1 is 1 +- 1.19*10^-7, so set epsilon a bit larger than that
public const float epsilon100 = 0.0001f;//next representable float at 100 is 100 +- 7.6*10^-6, so set epsilon a bit larger than that

I also implemented the unit tests from Lior; here the results with the fixed comparer:

And here the results with the current buggy comparer:

Lastly, while I am not familiar with Typescript, I think this compare function is unnecessary, because check(b), which is check(node) will always be 0. So the while loop test can be directly if (check(this.nodes[mid]) < 0). In fact in C# I do not need FindTransition as List<T> comes with an equivalent BinarySearch method out of the box.

[velipso]

very interesting! unfortunately I don't have the brain power to think through this, but I'm so grateful that you and Lior have put effort into this problem!

[Fribur]

How very modest...you might not have the time or priority etc right now however I pretty sure you do have the brain power considering your work on Polybool, the tutorial , the demo...
Anyhow, for when you do come back to further developing PolyBool, a further visualization of this fix might help:

For a status as in the picture, and doing a "FindTransation" with "New Event"..it should find that new event is below status[0], and above status[1]. However, your current implementation finds that "New Event" is above everything else...which is clearly wrong.

Why? Because it checks all the status segments start points "P", against the segment "New Event". First, if the "P" is colinear with the new event segment (it is not), secondly (fall through code), if "P" is CCW or CW from "new event". And "CW" means "P" is right of the new event segment, which is considered "below". Hence...it incorrectly establishes that the entire status is "below" the new event segment, because all the status segment start points are CW of "new event".

What it should rather do: it should check P= "start point new event" against the status segments. If so, it would determine that "P" is CCW of status[1] ="above status[1]" and CW of status[0]="below status[0]".

So in essence the new segment comparer determines if orientation should be determined of seg1 points against seg2 or vice versa.

Correct sorting of events in the status is crucial for the "Non-Zero" implementation (issue 8) to work...hence why I looked deeper into this.

[Fribur]

While throwing my C# conversation of Polybool against hundreds of polygons (glyphs from fonts)..I discovered yet another bug with the sorter above...was still related to not selecting the correct point from the correct segment prior to the orientation test. I think I got it now: fully symmetrical, considering all orientations of the 4 points towards each other, and removing all indirection, just plain simple Orient2D. https://github.com/Fribur/TextMeshDOTS/blob/f09e566bc2973f93e53f9021325f13f71e666314/Polybool/IComparer/StatusQueueComparer.cs#L18