Offsets spend a lot of time in the scanline priority queue because Reset() queues every local minima #2

I have a fix for this on perf/scanline-queue. It applies cleanly on the current main, leaves the output unchanged, and was originally opened as AngusJohnson#1115. It covers C++, C# and Delphi, and I can cut it down to C++ only if you'd prefer. The details are below, copied from that PR.

I've been profiling Clipper2 for a WebAssembly build. Offsets that create lots of local minima (open paths, big negative deltas) spend a surprising amount of time in the C++ priority_queue of scanlines. A big part of that is Reset() pushing the y of every local minima into the queue up front. Then PopScanline() spends ages popping the duplicates back off.

The minima list is already sorted by descending y, though, so there's no need to queue them at all. With this change, Reset() leaves them out, and PopScanline() just returns whichever is larger: the next unprocessed local minima's y or the top of the queue. The scanbeams come out in exactly the same order, so results don't change, and the queue only ever holds the edge tops added during the sweep.

I made the same change in all three ports so they stay in step:

• C++: std::priority_queue, which is where it really helps.
• C#: the sorted List<long>. A smaller list means cheaper BinarySearch/Insert.
• Delphi: the linked list. Here I also changed ClearSolutionOnly. The old while assigned(FScanLine) do PopScanLine(dummy) loop could now spin forever if a local minima was still pending above the list head (e.g. after an exception). DisposeScanLineList was already called right after it, so I just dropped the loop.

Numbers

These are on an M1 Max. Times are ms per operation, best of 5. The inputs are a 5000-point circle (r = 100000) and a few unions of overlapping noisy blobs.

So that's roughly 18% faster in C++ for offset-heavy work, a few percent in C#, and within noise for unions. Delphi (tested with FPC 3.2.2) is basically unchanged; the linked list was already cheap here since inserts land near the head. It's still nice to keep the ports in step, and the list is shorter now anyway.

Testing

• The C++ test suite passes (96/96), and so do the C# Tests1 and TestsZ projects.

• I also ran a differential fuzz test against main in all three ports. It does 200k random cases with tiny coordinate ranges so there are plenty of collinear points, horizontals and duplicates. The cases cover:

  • all clip types and fill rules
  • closed and open subjects
  • polytree and paths output
  • PreserveCollinear and ReverseSolution
  • offsets with every join and end type

  It hashes every output, and the hashes are identical to main's in every port.