discontinuedPackage jet_cad_floor_plan has been discontinued and replaced by jet_cad_2d_plan.

poleOfInaccessibility function

({double distance, Vector2 point}) poleOfInaccessibility(List<Vector2> ring, List<List<Vector2>> holes, { double precision = 10, })

The point of the face ring minus holes farthest from its boundary, to within precision mm (spec 10 D10, R-12), and its distance to that boundary.

Polylabel's quadtree search: the ring's box is covered by square cells, and the cell whose bound (its centre's distance plus its half-diagonal) is highest is taken next from a binary heap, and split in four while its bound beats the best distance found by more than precision. The search runs relative to the ring's first vertex, so a far-origin room costs what a near one does, and its point is exact to the same few ulps.

Not the centroid or the box centre: on a thin L both lie outside the face (the spike's Q4a). ring must hold three points or more; precision must be positive.

Implementation

({Vector2 point, double distance}) poleOfInaccessibility(
    List<Vector2> ring, List<List<Vector2>> holes,
    {double precision = 10}) {
  final o = ring.first;
  final r = [for (final p in ring) p - o];
  final hs = [
    for (final h in holes) [for (final p in h) p - o],
  ];
  var minX = double.infinity, minY = double.infinity;
  var maxX = double.negativeInfinity, maxY = double.negativeInfinity;
  for (final p in r) {
    minX = math.min(minX, p.x);
    minY = math.min(minY, p.y);
    maxX = math.max(maxX, p.x);
    maxY = math.max(maxY, p.y);
  }
  final w = maxX - minX, ht = maxY - minY;
  final size = math.min(w, ht);
  _Cell cell(double x, double y, double half) =>
      _Cell(x, y, half, _signedDistance(Vector2(x, y), r, hs));
  if (!(size > 0) || !size.isFinite) {
    final c = cell(minX, minY, 0);
    return (point: Vector2(c.x, c.y) + o, distance: c.d);
  }

  final queue = _MaxHeap();
  final half = size / 2;
  for (var x = minX; x < maxX; x += size) {
    for (var y = minY; y < maxY; y += size) {
      queue.push(cell(x + half, y + half, half));
    }
  }
  // Polylabel's first guesses: the centroid, then the box centre.
  final c0 = _centroid(r);
  var best = cell(c0.x, c0.y, 0);
  final box = cell(minX + w / 2, minY + ht / 2, 0);
  if (box.d > best.d) best = box;

  while (queue.isNotEmpty) {
    final c = queue.pop();
    if (c.d > best.d) best = c;
    // Written negated, so that a NaN bound ends the split, not the search.
    if (!(c.max - best.d > precision)) continue;
    final h = c.half / 2;
    queue
      ..push(cell(c.x - h, c.y - h, h))
      ..push(cell(c.x + h, c.y - h, h))
      ..push(cell(c.x - h, c.y + h, h))
      ..push(cell(c.x + h, c.y + h, h));
  }
  return (point: Vector2(best.x, best.y) + o, distance: best.d);
}