initialize method
void
initialize()
Initializes the Delaunay triangulation by finding the seed triangle and sorting the points in increasing distance from the seed triangle's circumcenter.
Implementation
void initialize() {
final int n = _inputCoords.length >> 1;
if (n < 3) {
return;
}
// Populate an array of point indices; calculate input data bbox.
double minX = double.maxFinite;
double minY = double.maxFinite;
double maxX = -double.maxFinite;
double maxY = -double.maxFinite;
for (int i = 0; i < n; i++) {
final double x = _inputCoords[2 * i];
final double y = _inputCoords[2 * i + 1];
if (x < minX) {
minX = x;
}
if (y < minY) {
minY = y;
}
if (x > maxX) {
maxX = x;
}
if (y > maxY) {
maxY = y;
}
_ids[i] = i;
}
final double cx = (maxX + minX) / 2.0;
final double cy = (maxY + minY) / 2.0;
double minDist = double.maxFinite;
int i0 = 0;
int i1 = 0;
int i2 = 0;
// Pick a seed point close to the center.
for (int i = 0; i < n; i++) {
final double d = _dist(
cx,
cy,
_inputCoords[2 * i],
_inputCoords[2 * i + 1],
);
if (d < minDist) {
i0 = i;
minDist = d;
}
}
final double i0x = _inputCoords[2 * i0];
final double i0y = _inputCoords[2 * i0 + 1];
// Find the point closest to the seed.
minDist = double.maxFinite;
for (int i = 0; i < n; i++) {
if (i == i0) {
continue;
}
final double d = _dist(
i0x,
i0y,
_inputCoords[2 * i],
_inputCoords[2 * i + 1],
);
if (d < minDist && d > 0.0) {
i1 = i;
minDist = d;
}
}
double i1x = _inputCoords[2 * i1];
double i1y = _inputCoords[2 * i1 + 1];
// Find the third point which forms the smallest circumcircle with the first
// two.
double minRadius = double.maxFinite;
for (int i = 0; i < n; i++) {
if (i == i0 || i == i1) {
continue;
}
final double r = _circumradius(
i0x,
i0y,
i1x,
i1y,
_inputCoords[2 * i],
_inputCoords[2 * i + 1],
);
if (r < minRadius) {
i2 = i;
minRadius = r;
}
}
double i2x = _inputCoords[2 * i2];
double i2y = _inputCoords[2 * i2 + 1];
if (minRadius == double.maxFinite) {
// Order collinear points by dx (or dy if all x are identical)
// and return the list as a hull
for (int i = 0; i < n; i++) {
final double dx = _inputCoords[2 * i] - _inputCoords[0];
_dists[i] = dx != 0.0 ? dx : _inputCoords[2 * i + 1] - _inputCoords[1];
}
_quicksort(_ids, _dists, 0, n - 1);
final Uint32List hull = Uint32List(n);
int j = 0;
double d0 = -double.maxFinite;
for (int i = 0; i < n; i++) {
final int id = _ids[i];
if (_dists[id] > d0) {
hull[j++] = id;
d0 = _dists[id];
}
}
_hull = hull.sublist(0, j);
_colinear = true;
return;
}
// Swap the order of the seed points for counter-clockwise orientation.
if (_orient(i0x, i0y, i1x, i1y, i2x, i2y)) {
final int i = i1;
final double x = i1x;
final double y = i1y;
i1 = i2;
i1x = i2x;
i1y = i2y;
i2 = i;
i2x = x;
i2y = y;
}
// Sort the points by distance from the seed triangle circumcenter
final Point<double> center = _circumcenter(i0x, i0y, i1x, i1y, i2x, i2y);
_cx = center.x;
_cy = center.y;
for (int i = 0; i < n; i++) {
_dists[i] = _dist(_inputCoords[2 * i], _inputCoords[2 * i + 1], _cx, _cy);
}
_quicksort(_ids, _dists, 0, n - 1);
if (n <= 100000) {
_i0 = i0;
_i1 = i1;
_i2 = i2;
_coords = _inputCoords;
} else {
// When there are more than ~100000 points, improving the locality of
// access to the coordinate list improves performance.
_sortedCoords ??= Float32List(_inputCoords.length);
final Float32List localSorted = _sortedCoords!;
for (int i = 0; i < n; i++) {
if (_ids[i] == i0) {
_i0 = i;
}
if (_ids[i] == i1) {
_i1 = i;
}
if (_ids[i] == i2) {
_i2 = i;
}
localSorted[2 * i] = _inputCoords[2 * _ids[i]];
localSorted[2 * i + 1] = _inputCoords[2 * _ids[i] + 1];
_ids[i] = i;
}
_coords = localSorted;
}
// Set up the seed triangle as the starting hull.
_hullStart = _i0;
_hullSize = 3;
_hullNext[_i0] = _hullPrev[_i2] = _i1;
_hullNext[_i1] = _hullPrev[_i0] = _i2;
_hullNext[_i2] = _hullPrev[_i1] = _i0;
_hullTri[_i0] = 0;
_hullTri[_i1] = 1;
_hullTri[_i2] = 2;
_hullHash.fillRange(0, _hullHash.length, -1);
_hullHash[_hashKey(i0x, i0y)] = _i0;
_hullHash[_hashKey(i1x, i1y)] = _i1;
_hullHash[_hashKey(i2x, i2y)] = _i2;
_trianglesLen = 0;
_addTriangle(_i0, _i1, _i2, -1, -1, -1);
}