traceRoom function

TraceResult traceRoom(

Vector2 seed,
List<RoomInput> inputs

)

Finds the room around seed among inputs (spec 10 D5, D6):

Local frame. Every point is taken relative to seed first, so the arithmetic runs on numbers the size of a building, not of the far origin.
The seed in a wall. The seed inside a closed input (crossing number), or within roomTrace.linear of any input segment, is SeedInWall, naming the lowest-handle such input.
Segments, each tagged with its source; one no longer than roomTrace.linear is dropped. Inputs are taken in ascending source order, so the output is a function of the input set.
Splits, by a sweep over the segments sorted by minX with a box reject on y: each endpoint of one segment within roomTrace.linear of another splits the other there (a T butt on a through face, a separator's end on a face, a collinear overlap); otherwise, unless the two are parallel within roomTrace.angular, a proper crossing splits both.
Vertices within roomTrace.linear of an earlier vertex are that vertex (a grid hash, the lowest index winning); duplicate edges merge and keep every source.
Faces. Half-edges around each vertex sorted by angle; the edge after u → v is the one leaving v just clockwise of v → u, so every face lies to the left of its walk and bounded faces walk anticlockwise.
The seed's face: the anticlockwise cycle of least area holding the seed. None: Unbounded.
Holes (D6): every other connected component whose outer contour (its most negative cycle) lies inside the outer ring and inside no bounded face of a third component that does not hold the seed.
Clean-up: doubled edges split out (decision 29): a half-edge and its twin in one walk are both removed and the walk between them is a loop of its own. A spike (u → v → u, a dangling separator end) is the case with nothing between them. The outer cycle leaves the outer ring (its loop of greatest area) and a clockwise loop for each island tied to the ring by zero-width edges only, which is a hole; a hole's contour leaves a clockwise loop per island it ties together; a component with no area (a free separator, or a free tree of them) leaves nothing and is not a hole. Then vertices collinear within roomTrace.linear; holes reversed to anticlockwise, their sources moving with their edges; the canonical order of Ruling 10-7; areas by the shoelace in the local frame.

Implementation

TraceResult traceRoom(Vector2 seed, List<RoomInput> inputs) {
  final tol = roomTrace.linear;

  // 1. The local frame: world point p is p - o here, and the seed is s0.
  final o = seed.clone();
  final s0 = Vector2.zero();

  // Inputs in ascending source order (3), relative to the seed (1).
  final sorted = [...inputs]
    ..sort((a, b) => a.source.value.compareTo(b.source.value));
  final local = [
    for (final input in sorted) [for (final p in input.points) p - o],
  ];

  // 2. The seed in a wall: the first input in ascending order that holds it.
  for (var k = 0; k < sorted.length; k++) {
    final pts = local[k];
    final n = pts.length;
    final closed = sorted[k].closed;
    if (closed && n >= 3 && pointInRing(s0, pts)) {
      return SeedInWall(sorted[k].source);
    }
    final m = closed ? n : n - 1;
    for (var i = 0; i < m; i++) {
      if (distToSegment(s0, pts[i], pts[(i + 1) % n]) <= tol) {
        return SeedInWall(sorted[k].source);
      }
    }
  }

  // 3-6. The arrangement: segments, splits, vertices and face cycles.
  final (
    :segments,
    :verts,
    :from,
    :to,
    :edges,
    :cycles,
    :areas,
    :comp,
  ) = _arrange(sorted, local);
  debugTracedSegments += segments;
  List<Vector2> pointsOf(List<int> cycle) =>
      [for (final h in cycle) verts[from[h]]];

  // 7. The seed's face: the least positive cycle holding the seed.
  int? outer;
  for (var c = 0; c < cycles.length; c++) {
    if (!(areas[c] > 0)) continue;
    if (!pointInRing(s0, pointsOf(cycles[c]))) continue;
    if (outer == null || areas[c] < areas[outer]) outer = c;
  }
  if (outer == null) return const Unbounded();
  final k0 = comp[outer];

  // 8. Holes.
  final contour = <int, int>{}; // component -> its most negative cycle
  for (var c = 0; c < cycles.length; c++) {
    if (comp[c] == k0) continue;
    final best = contour[comp[c]];
    if (best == null || areas[c] < areas[best]) contour[comp[c]] = c;
  }
  final outerPoints = pointsOf(cycles[outer]);
  final holeCycles = <int>[];
  for (final MapEntry(key: component, value: c) in contour.entries) {
    if (!(areas[c] < 0)) continue; // no area: not a contour
    final p = verts[from[cycles[c].first]];
    if (!pointInRing(p, outerPoints)) continue;
    var nested = false;
    for (var d = 0; d < cycles.length; d++) {
      if (comp[d] == k0 || comp[d] == component || !(areas[d] > 0)) continue;
      final pts = pointsOf(cycles[d]);
      if (pointInRing(p, pts) && !pointInRing(s0, pts)) {
        nested = true;
        break;
      }
    }
    if (!nested) holeCycles.add(c);
  }

  // 9. Clean-up and the canonical order.
  double areaOf(List<int> loop) => shoelace(pointsOf(loop));
  _Ring clean(List<int> hs) {
    final ring = _rotated((
      pts: [for (final h in hs) verts[from[h]]],
      src: [
        for (final h in hs)
          edges[from[h] < to[h] ? (from[h], to[h]) : (to[h], from[h])]!,
      ],
    ));
    // Collinear vertices, scanned from the canonical start.
    final pts = [...ring.pts];
    final src = [...ring.src];
    var changed = true;
    while (changed && pts.length > 3) {
      changed = false;
      for (var i = 0; i < pts.length; i++) {
        final prev = (i - 1 + pts.length) % pts.length;
        final a = pts[prev], b = pts[i], c = pts[(i + 1) % pts.length];
        final d = c - a;
        final along = (b - a).dot(d);
        if (distToSegment(b, a, c) <= tol && along > 0 && along < d.dot(d)) {
          src[prev] = {...src[prev], ...src[i]};
          pts.removeAt(i);
          src.removeAt(i);
          changed = true;
          break;
        }
      }
    }
    return _rotated((pts: pts, src: src));
  }

  // Doubled edges (decision 29). The outer cycle, split, leaves one loop
  // walked anticlockwise, the outer ring, and a clockwise loop for each
  // island tied to it by zero-width edges only: a hole, as a freestanding
  // island is. A hole's contour, split, leaves a clockwise loop per island
  // it ties together. A free separator, or a free tree of them, is doubled
  // edges only and leaves nothing: a component with no area is not a hole
  // (D6), whatever the sign of its walk's shoelace residue. The hole test
  // above reads the cycle as walked, so an island's courtyard stays
  // outside the face.
  final outerLoops = _splitDoubled(cycles[outer]);
  var ringLoop = outerLoops.first;
  for (final l in outerLoops) {
    if (areaOf(l) > areaOf(ringLoop)) ringLoop = l;
  }
  final ring = clean(ringLoop);
  final holes = <_Ring>[];
  for (final loop in [
    for (final l in outerLoops)
      if (!identical(l, ringLoop)) l,
    for (final c in holeCycles) ..._splitDoubled(cycles[c]),
  ]) {
    if (!(areaOf(loop) < 0)) continue;
    final r = clean(loop);
    final n = r.pts.length;
    // Walked clockwise (the face lies outside it): reversed to
    // anticlockwise, each source moving with its edge.
    holes.add(_rotated((
      pts: [for (var i = n - 1; i >= 0; i--) r.pts[i]],
      src: [for (var i = n - 1; i >= 0; i--) r.src[(i - 1 + n) % n]],
    )));
  }
  holes.sort(_byPoints);

  return Traced(
    [for (final p in ring.pts) p + o],
    [for (final s in ring.src) _ascending(s)],
    [
      for (final h in holes) [for (final p in h.pts) p + o],
    ],
    [
      for (final h in holes) [for (final s in h.src) _ascending(s)],
    ],
    shoelace(ring.pts),
    [for (final h in holes) shoelace(h.pts)],
  );
}

traceRoom function

Implementation

editor library