Accuracy depends on binary heap implementation

[urschrei]

Testing a non-degenerate Polygon:

[
    (0.0, 0.0),
    (4.0, 0.0),
    (4.0, 1.0),
    (1.0, 1.0),
    (1.0, 4.0),
    (0.0, 4.0),
    (0.0, 0.0)
];

Gives different values when tested against this implementation ((0.5, 0.5)), than against the implementation in Shapely 1.6b2 ((0.5, 1.5)), and my Rust implementation ((0.5, 1.5)). This is due to the fact that the binary heap implementations return elements with equal values in a different order.

This version, using tinyqueue:

Popped cell with max distance: 1.8284271247461903, 2, 2
Splitting
Popped cell with max distance: 1.4142135623730951, 1, 1
Found greater distance: 0, -0.3571428571428572
New best coords: (1, 1)
Splitting
Popped cell with max distance: 1.4142135623730951, 3, 1
Splitting
Popped cell with max distance: 1.4142135623730951, 1, 3
Splitting
Popped cell with max distance: 1.2071067811865475, 0.5, 0.5
Found greater distance: 0.5, 0
New best coords: (0.5, 0.5)
Popped cell with max distance: 1.2071067811865475, 3.5, 0.5
Popped cell with max distance: 1.2071067811865475, 1.5, 0.5
Popped cell with max distance: 1.2071067811865475, 0.5, 2.5
Popped cell with max distance: 1.2071067811865475, 0.5, 1.5
Popped cell with max distance: 1.2071067811865475, 0.5, 3.5
Popped cell with max distance: 1.2071067811865475, 2.5, 0.5
Popped cell with max distance: 0.20710678118654757, 2.5, 1.5
Popped cell with max distance: 0.20710678118654757, 1.5, 2.5
Popped cell with max distance: 0.20710678118654757, 1.5, 1.5
Popped cell with max distance: 0.20710678118654757, 3.5, 1.5
Popped cell with max distance: 0.20710678118654757, 1.5, 3.5
Popped cell with max distance: -0.5857864376269049, 3, 3

The Rust version:

Popped cell with max distance: (1.8284271247461903, 2, 2)
Splitting
Popped cell with max distance: (1.4142135623730951, 1, 1)
Found greater distance: (-0, -0.3571428571428572)
New best coords: (1, 1)
Splitting
Popped cell with max distance: (1.4142135623730951, 1, 3)
Splitting
Popped cell with max distance: (1.4142135623730951, 3, 1)
Splitting
Popped cell with max distance: (1.2071067811865475, 0.5, 1.5)
Found greater distance: (0.5, -0)
New best coords: (0.5, 1.5)
Popped cell with max distance: (1.2071067811865475, 0.5, 2.5)
Popped cell with max distance: (1.2071067811865475, 1.5, 0.5)
Popped cell with max distance: (1.2071067811865475, 2.5, 0.5)
Popped cell with max distance: (1.2071067811865475, 3.5, 0.5)
Popped cell with max distance: (1.2071067811865475, 0.5, 0.5)
Popped cell with max distance: (1.2071067811865475, 0.5, 3.5)
Popped cell with max distance: (0.20710678118654757, 1.5, 3.5)
Popped cell with max distance: (0.20710678118654757, 2.5, 1.5)
Popped cell with max distance: (0.20710678118654757, 3.5, 1.5)
Popped cell with max distance: (0.20710678118654757, 1.5, 1.5)
Popped cell with max distance: (0.20710678118654757, 1.5, 2.5)
Popped cell with max distance: (-0.5857864376269049, 3, 3)

I can't test the cpp version here, but it looks like we need a way to break ties between equal max distance values, because different binary heap implementations will internally order them differently…

[urschrei]

I just double-checked the Shapely version, and it returns the cells in identical order to the Rust version…

('Popped cell with max distance: (1.8284271247461903, 2.0, 2.0))
('Popped cell with max distance: (1.4142135623730951, 1.0, 1.0))
('Popped cell with max distance: (1.4142135623730951, 1.0, 3.0))
('Popped cell with max distance: (1.4142135623730951, 3.0, 1.0))
('Popped cell with max distance: (1.2071067811865475, 0.5, 1.5))
('Popped cell with max distance: (1.2071067811865475, 0.5, 2.5))
('Popped cell with max distance: (1.2071067811865475, 1.5, 0.5))
('Popped cell with max distance: (1.2071067811865475, 2.5, 0.5))
('Popped cell with max distance: (1.2071067811865475, 3.5, 0.5))
('Popped cell with max distance: (1.2071067811865475, 0.5, 0.5))
('Popped cell with max distance: (1.2071067811865475, 0.5, 3.5))
('Popped cell with max distance: (0.20710678118654757, 1.5, 3.5))
('Popped cell with max distance: (0.20710678118654757, 2.5, 1.5))
('Popped cell with max distance: (0.20710678118654757, 3.5, 1.5))
('Popped cell with max distance: (0.20710678118654757, 1.5, 1.5))
('Popped cell with max distance: (0.20710678118654757, 1.5, 2.5))
('Popped cell with max distance: (-0.5857864376269049, 3.0, 3.0))

[mourner]

Do you think this should really be addressed somehow in the JS implementation? I don't think we should or can do anything about this. It provides the result given within a given precision and it shouldn't matter whether it exactly matches results from other implementations.