Stabilize LocMinSorter sorting

[olologin]

Every platform has its own default implementation of C++ STL, and each STL has its own implementation of std::sort which give slightly different results depending on how they are implemented.
This means you can get slightly different results from Clipper, depending on which platform it is compiled and run.

I tested my program for such differences and found one of them in clipper:

Clipper2/CPP/Clipper2Lib/src/clipper.engine.cpp

Line 777 in 959f96e

std::sort(minima_list_.begin(), minima_list_.end(), LocMinSorter());

To simulate potential differences between platforms I added the following snippe before each std::sort in all sources:

std::random_device rd;
std::mt19937 g(rd());
std::shuffle(minima_list_.begin(), minima_list_.end(), g);

And at least for line 777 I start to get slightly different results with the same inputs to clipper.
Of course I also found similar differences between Clipper2 built on libc++ (AppleClang) and MSVC.

I wonder if that sorting can be stabilized by improvements to LocMinSorter() ?
Of course another option is to use std::stable_sort, but that requires 2*N memory AFAIK.

If you are interested I can try to dump inputs that produce different results depending on sorting.

[AngusJohnson]

I'm certainly interested in stabilising clipping results between the various compilers, but my concern is that stable sorts are more time costly. (Note: In ClipperBase::BuildIntersectList I do use a stable sort algorithm, but there it's essential despite its relatively minor impact on performance.)

Edit: The following change doesn't seem to impact on performance:
std::stable_sort(minima_list_.begin(), minima_list_.end(), LocMinSorter());

Does this reduce the differences in results between compilers?

[olologin]

Yes, using stable_sort on that line fixes the difference.
But in my opinion better option is to use more data in predicate (in case x and y are equal), for example is_open and polytype fields, and maybe even compare by pointer (but for this we need to be sure pointers are comparable (for example they are all pointing on elements of a single std::vector). I am not sure if this is going to help in this particular case, but when I see such problems I try to resolve them by comparing more fields in predicate.

[olologin]

@AngusJohnson
Hi, reviving this discussion again.
It seems not only the first, but also the second sort in clipper.engine.cpp is leading to different results on linux (GCC and libstdc++) and windows (MSVC).
Is it possible to also replace that one with stable_sort?
I mean:
std::sort(horz_seg_list_.begin(), horz_seg_list_.end(), HorzSegSorter());

[AngusJohnson]

Is it possible to also replace that one with stable_sort?

Yes it's certainly possible, but it would affect performance which I believe is a higher priority to most.
I could add this as a CMake option, but I'd need help doing so.

Edit: oops, I've just realised you're suggesting a stable sort only on horz_seg_list_ where I suspect the performance impact would be minimal. However, if you wanted stable_sort on intersect_nodes_ too, that I believe would noticeably affect performance.

[olologin]

@AngusJohnson Is it possible to use better compare predicate so that it resolves all ties and forces the same order without dependence on initial order?
I will test if intersect_nodes_ stable sorting affects anything. Our devs did not yet complain about stability of that sorting.

[olologin]

Thanks for changes. It is stable now.