Description
In voronoi_builder.hpp line 400 the key of a map is altered in-place. Naturally I can't do this in Rust, so the
obvious solution is to remove and then re-insert the object with the new key.
Problem is that does not always work. Somehow the beach-line calculations sometimes requires that the object remains in the old position, while the key is altered.
The root of the problem is that the beachline keys in boost are not transitive (as I understand it).
A<B, B<C and yet this could also be true: C<A.
// Change the (A, B) bisector node to the (A, C) bisector node.
const_cast<key_type&>(it_first->first).right_site(site3);
Same section in rust is builder.rs line 663
Issue can be tested with this input:
0
6
0 10000000 700000 1
700000 1 700000 9000000
700000 9000000 9100000 9000000
9100000 9000000 9100000 0
9100000 0 10000000 10000000
10000000 10000000 0 10000000
Update:
I made a test in boost voronoi 1.76 and added this to voronoi_builder.hpp
284 // Find the node in the binary search tree with left arc
285 // lying above the new site point.
286 key_type new_key(*site_event_iterator_);
287 {
beach_line_iterator i;
node_comparer_type cmp;
std::cout << std::endl << "lower_bound:" << std::endl;
for(i=beach_line_.begin();i!=beach_line_.end();i++){
std::cout << (cmp(i->first, new_key)?"true":"false") << " " << (cmp(new_key, i->first)?"true":"false") << std::endl;
}
}
beach_line_iterator right_it = beach_line_.lower_bound(new_key);
It shows how each item in the beach-line map (in order) compares to the key and it generates this output:
...
false true
false true
false true
lower_bound:
true false
true false
true false
true false
false true <---- ???????
true false
true false
false true
false true
false true
lower_bound:
true false
true false
...
I don't understand how C++ map() can find the correct value under such conditions. Doesn't C++ map require Strict weak orderings?