Union on Paths64 with colinear segments fail

[TorstenKassbaum]

Hi Angus,
i want to use Clipper2 V2.0.1 to combine traces and pads of a PCB board. The data source is Gerber. All traces and pads of one layer were converted to polygons. Outer polygons have CCW orientation and hole polygons have CW orientation. When i do Union with NonZero on all polygons everything works fine.

For improving the speed of this operation, i tried to divide the polygons into tiles by RectClip. Then i work inside the tile and combine the tiles later. Inside the tile i do a Union of the clipped Paths64. Due to RectClip there are many edges of the polygons collinear.

The first bug is: I get a StackOverflow from private bool CheckSplitOwner(OutRec outrec, List? splits)

I tried to repair ist by:

private bool CheckSplitOwner(OutRec outrec, List<int>? splits)
{
  return CheckSplitOwner(outrec, splits, new HashSet<OutRec>());
}

private bool CheckSplitOwner(OutRec outrec, List<int>? splits, HashSet<OutRec> recursionGuard)
{
  if (splits == null) return false;
  // nb: use indexing (not an iterator) in case 'splits' is modified inside this loop (#1029)
  for (int i = 0; i < splits.Count; i++)
  {
    OutRec? originalSplit = _outrecList[splits[i]];

    if (!recursionGuard.Add(originalSplit))
    {
      // Cycle detected, this OutRec is already in the current recursion path.
      Trace.WriteLine(">>>>>>>>>>>>>>>>>>>>   Clipper Recursion    <<<<<<<<<<<<<<<<<<<");
      continue;
    }

    try
    {
      if (originalSplit.pts == null && originalSplit.splits != null &&
          CheckSplitOwner(outrec, originalSplit.splits, recursionGuard)) return true;

      OutRec? split = GetRealOutRec(originalSplit);
      if (split == null || split == outrec || split.recursiveSplit == outrec) continue;
      split.recursiveSplit = outrec;

      if (split.splits != null && CheckSplitOwner(outrec, split.splits, recursionGuard)) return true;

      if (!CheckBounds(split) ||
          !split.bounds.Contains(outrec.bounds) ||
          !Path1InsidePath2(outrec.pts!, split.pts!)) continue;

      if (!IsValidOwner(outrec, split)) // split is owned by outrec (#957)
        split.owner = outrec.owner;

      outrec.owner = split; //found in split
      return true;
    }
    finally
    {
      // Backtrack: remove from guard when leaving the recursion level
      recursionGuard.Remove(originalSplit);
    }
  }
  return false;
}

This hack removed the StackOverflow. But then i got wrong results from the Union operation. When i do Union into a PolyTree64, i found there are outer polygons with positive area.
I also found outer polygons that are connected with a zero width bridge.

The next thing i found is: In public static bool GetLineIntersectPt(Point64 ln1a, Point64 ln1b, Point64 ln2a, Point64 ln2b, out Point64 ip)

Her you don't Round the intersection point anymore (//avoid using constructor (and rounding too) as they affect performance //664), but this generates points outside the clipping rectangle during RectClip.

Unfortunately, it’s difficult to give you any figures, as my data is very extensive.

I hope you find my description of the problem helpful.

Best regards,
Torsten