find method

int find(double x, double y, [ int startTriangle = 0 ])

Returns the triangle containing the given point, or -1 if not found. Uses walking algorithm starting from the given triangle (default: 0).

Implementation

int find(double x, double y, [int startTriangle = 0]) {
  if (trianglesLength == 0) return -1;

  int current = startTriangle.clamp(0, trianglesLength - 1);
  final visited = <int>{};

  while (!visited.contains(current)) {
    visited.add(current);

    final i0 = triangleIndices[current * 3];
    final i1 = triangleIndices[current * 3 + 1];
    final i2 = triangleIndices[current * 3 + 2];

    final x0 = coords[i0 * 2], y0 = coords[i0 * 2 + 1];
    final x1 = coords[i1 * 2], y1 = coords[i1 * 2 + 1];
    final x2 = coords[i2 * 2], y2 = coords[i2 * 2 + 1];

    // Check if point is inside the triangle
    final d0 = _orient(x, y, x0, y0, x1, y1);
    final d1 = _orient(x, y, x1, y1, x2, y2);
    final d2 = _orient(x, y, x2, y2, x0, y0);

    if (d0 >= 0 && d1 >= 0 && d2 >= 0) {
      return current;
    }

    // Move to neighbor triangle
    int next = -1;
    if (d0 < 0) {
      final e = halfedges[current * 3];
      if (e >= 0) next = e ~/ 3;
    }
    if (next < 0 && d1 < 0) {
      final e = halfedges[current * 3 + 1];
      if (e >= 0) next = e ~/ 3;
    }
    if (next < 0 && d2 < 0) {
      final e = halfedges[current * 3 + 2];
      if (e >= 0) next = e ~/ 3;
    }

    if (next < 0) {
      // Point is outside the triangulation
      return -1;
    }

    current = next;
  }

  return -1;
}