dartterm/lib/algorithms/regionalize.dart

import 'dart:math' as math;

import 'package:dartterm/algorithms/geometry.dart' as geo;

class Region {
  final geo.Rect rect;
  final Set<(int, int)> points;

  bool get isRectangle => points.length == rect.dx * rect.dy;

  Region(this.rect, this.points);

  static Region fromNonEmptySet(Set<(int, int)> s) {
    assert(s.isNotEmpty);
    int xMin = s.map<int>((xy) => xy.$1).reduce(math.min);
    int yMin = s.map<int>((xy) => xy.$2).reduce(math.min);
    int xMax = s.map<int>((xy) => xy.$1).reduce(math.max);
    int yMax = s.map<int>((xy) => xy.$2).reduce(math.max);
    var rect = geo.Rect(xMin, yMin, xMax - xMin + 1, yMax - yMin + 1);
    return Region(rect, s);
  }

  @override
  String toString() {
    return "Region($rect, $points)";
  }
}

(List<Region>, Map<(int, int), int>) regionalize(
    geo.Rect rect, bool Function(int, int) isAccessible) {
  int nextRegion = 0;
  Map<(int, int), int> regions = {};

  int floodfill(int x, int y) {
    int workDone = 0;
    if (!rect.containsPoint(geo.Offset(x, y))) {
      return workDone;
    }
    if (regions[(x, y)] != null) {
      return workDone;
    }
    if (!isAccessible(x, y)) {
      return workDone;
    }

    regions[(x, y)] = nextRegion;
    workDone += 1;
    workDone += floodfill(x - 1, y);
    workDone += floodfill(x + 1, y);
    workDone += floodfill(x, y - 1);
    workDone += floodfill(x, y + 1);
    return workDone;
  }

  // TODO: This can be done more efficiently with a union/find data structure
  // But this is an easy implementation to understand
  for (var y = rect.y0; y < rect.y1; y++) {
    for (var x = rect.x0; x < rect.x1; x++) {
      if (regions[(x, y)] == null) {
        if (floodfill(x, y) > 0) {
          nextRegion += 1;
        }
      }
    }
  }
  return (_toExplicit(regions, nextRegion), regions);
}

List<Region> _toExplicit(Map<(int, int), int> pointRegions, int nRegions) {
  List<Set<(int, int)>> regionPoints = [for (var i = 0; i < nRegions; i++) {}];
  for (var MapEntry(key: (x, y), value: id_) in pointRegions.entries) {
    regionPoints[id_].add((x, y));
  }

  return [for (var s in regionPoints) Region.fromNonEmptySet(s)];
}