Skip to content

Stabilize LocMinSorter sorting #594

@olologin

Description

@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:

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.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions