Skip to content

Replaced std::random_shuffle with std::shuffle in tri #24062

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
tacaswell merged 14 commits into from
Oct 28, 2022
Merged

Replaced std::random_shuffle with std::shuffle in tri #24062

Show file tree
Hide file tree
Changes from 12 commits
Commits
Show all changes
14 commits
Select commit Hold shift + click to select a range
601d92a
removed RandomNumberGenerator class, included <random>, replaced rand…
tybeller Sep 30, 2022
4bf6696
Merge branch 'matplotlib:main' into shuffleFix
tybeller Oct 2, 2022
1ae3610
Create 24062-tb.rst
tybeller Oct 2, 2022
c8e0531
Update doc/api/next_api_changes/behavior/24062-tb.rst
tybeller Oct 4, 2022
bd3dc8a
Update doc/api/next_api_changes/behavior/24062-tb.rst
tybeller Oct 5, 2022
4648dda
Update 24062-tb.rst
tybeller Oct 5, 2022
d77b191
Update 24062-tb.rst
tybeller Oct 6, 2022
0427513
Merge branch 'matplotlib:main' into shuffleFix
tybeller Oct 10, 2022
c4fb35e
Merge branch 'matplotlib:main' into shuffleFix
tybeller Oct 12, 2022
e096d5e
Update 24062-tb.rst
tybeller Oct 12, 2022
cf0613b
Merge branch 'matplotlib:main' into shuffleFix
tybeller Oct 14, 2022
d2d0d11
removed random number generator from _tri.h
tybeller Oct 14, 2022
a06bae9
Update _tri.cpp
tybeller Oct 14, 2022
3513a85
Update src/tri/_tri.h
oscargus Oct 23, 2022
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
8 changes: 8 additions & 0 deletions doc/api/next_api_changes/behavior/24062-tb.rst
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -0,0 +1,8 @@
``TrapezoidMapTriFinder`` uses different random number generator
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

The random number generator used to determine the order of insertion of
triangle edges in ``TrapezoidMapTriFinder`` has changed. This can result in a
different triangle index being returned for a point that lies exactly on an
edge between two triangles. This can also affect triangulation interpolation
and refinement algorithms that use ``TrapezoidMapTriFinder``.
20 changes: 4 additions & 16 deletions src/tri/_tri.cpp
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -12,6 +12,7 @@

#include <algorithm>
#include <set>
#include <random>


TriEdge::TriEdge()
Expand Down Expand Up @@ -1465,8 +1466,8 @@ TrapezoidMapTriFinder::initialize()
_tree->assert_valid(false);

// Randomly shuffle all edges other than first 2.
RandomNumberGenerator rng(1234);
std::random_shuffle(_edges.begin()+2, _edges.end(), rng);
std::mt19937 rng(1234);
std::shuffle(_edges.begin()+2, _edges.end(), rng);

// Add edges, one at a time, to tree.
size_t nedges = _edges.size();
Expand Down Expand Up @@ -2055,17 +2056,4 @@ TrapezoidMapTriFinder::Trapezoid::set_upper_right(Trapezoid* upper_right_)
upper_right = upper_right_;
if (upper_right != 0)
upper_right->upper_left = this;
}



RandomNumberGenerator::RandomNumberGenerator(unsigned long seed)
: _m(21870), _a(1291), _c(4621), _seed(seed % _m)
{}

unsigned long
RandomNumberGenerator::operator()(unsigned long max_value)
{
_seed = (_seed*_a + _c) % _m;
return (_seed*max_value) / _m;
}
}

@oscargus oscargus Oct 14, 2022

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Please end the file with an empty line. That will fix the pre-commit issue. (The pyside6 issue is fixed in #24158.)

26 changes: 0 additions & 26 deletions src/tri/_tri.h
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -790,29 +790,3 @@ class TrapezoidMapTriFinder

Node* _tree; // Root node of the trapezoid map search tree. Owned.
};
Comment thread
oscargus marked this conversation as resolved.
Resolved



/* Linear congruential random number generator. Edges in the triangulation are
* randomly shuffled before being added to the trapezoid map. Want the
* shuffling to be identical across different operating systems and the same
* regardless of previous random number use. Would prefer to use a STL or
* Boost random number generator, but support is not consistent across
* different operating systems so implementing own here.
*
* This is not particularly random, but is perfectly adequate for the use here.
* Coefficients taken from Numerical Recipes in C. */
class RandomNumberGenerator
{
public:
RandomNumberGenerator(unsigned long seed);

// Return random integer in the range 0 to max_value-1.
unsigned long operator()(unsigned long max_value);

private:
const unsigned long _m, _a, _c;
unsigned long _seed;
};

#endif
Comment thread
oscargus marked this conversation as resolved.
Resolved