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);
}