cellPolygon method

List<Point>? cellPolygon(int i)

Returns the Voronoi cell polygon for point i. Returns null if the cell is degenerate or empty.

Implementation

List<Point>? cellPolygon(int i) {
  if (i < 0 || i >= cellCount) return null;

  final edges = _pointToEdges[i];
  if (edges.isEmpty) return null;

  // For points on the convex hull, we need special handling
  final isOnHull = delaunay.hull.contains(i);

  if (isOnHull) {
    return _computeHullCellPolygon(i);
  }

  // For interior points, trace around the cell
  final vertices = <Point>[];
  final visited = <int>{};

  // Start from any edge
  int e = edges.first;
  final start = e;

  do {
    if (visited.contains(e)) break;
    visited.add(e);

    final t = e ~/ 3;
    if (t < circumcenters.length) {
      vertices.add(circumcenters[t]);
    }

    // Move to the next edge around point i
    final opposite = delaunay.halfedges[e];
    if (opposite < 0) {
      // Reached hull - need to handle boundary
      break;
    }

    e = _nextEdgeAroundPoint(opposite);
  } while (e != start && vertices.length < 100);

  if (vertices.length < 3) return null;

  return _clipPolygon(vertices);
}