tintOf function
The tint of the face ring minus holes (spec 10 D9), both
anticlockwise as Traced gives them, in the trace's seed-relative
frame (the caller subtracts the seed, and maps Tint.points to the
room's local space after): so the bridges and the slit are decided on
numbers the size of a building, not of the far origin.
The keyhole. The holes are taken in descending order of their
rightmost x (ties in the order given). Each joins the growing
keyholed ring (the outer ring with the holes already joined) through a
bridge from its rightmost vertex H to the nearest vertex V of that
ring whose bridge properly crosses no edge of that ring and no edge of
any hole not yet joined, this one included (ties to the earlier vertex),
and whose slit is clear (decision 29's note, Task 14c). The hole is
walked clockwise from H and ends at H'; the return edge runs from
H' to V'. First H' = H + s and V' = V + s, kSlit to the
bridge's right; if that slit is not clear, each end goes inside its own
sector (_slitEnd): H' between the bridge and the hole's last edge,
V' between the ring's next edge and the bridge. The slit's three edges
(the hole's last edge into H', the return, and V' onward) must cross
nothing and touch nothing, against the ring and the holes not yet
joined, so the ring stays simple: at an acute H or V the
perpendicular slit can cross the hole's edge beside H, or the bridge,
though the bridge is clear. A hole with no such vertex is left out (the
tint covers it) and named in Tint.holesLeftOut.
The perpendicular slit is tried first because it is what the keyhole
always did: placing each end in its sector straight away left out more
holes near the ring than before Task 14c (31 traces over the 14c
review's four fuzz seeds), and any slit that passes the check is simple.
Its cost: at a convex vertex of the ring (nearly every box corner) the
perpendicular V' lies outside the face, up to 0.5 mm, so the tint
covers a sliver of the wall there, as it did before Task 14c; where a
later hole bridges to an earlier slit end the two add up: each chained
bridge adds at most 0.5 mm; about 1 mm in the reviews' fuzz
(0.99999979 mm).
The fallback chain, so an edit is never refused because of a tint:
- the keyholed ring, if it triangulates (
triangulationFornon-empty); - else the outer ring alone, if it triangulates;
- else the outer ring, which the room stores as an invisible, unfilled closed polyline.
accepts, when given, is the caller's own condition on the form of
step 1 or 2, asked only once that form triangulates here: accepts(step, points) false takes the chain's next step. The room passes its check of
the points it will store, in its local frame, and its test seam
(debugTintFailedSteps, Ruling 10-16) through it, so the chain has one
owner.
Implementation
Tint tintOf(List<Vector2> ring, List<List<Vector2>> holes,
{bool Function(int step, List<Vector2> points)? accepts}) {
final keyholed = <Vector2>[...ring];
final order = List<int>.generate(holes.length, (i) => i);
double rightmost(List<Vector2> r) =>
r.fold(double.negativeInfinity, (m, p) => math.max(m, p.x));
final right = [for (final h in holes) rightmost(h)];
order.sort((a, b) {
final c = right[b].compareTo(right[a]);
return c != 0 ? c : a.compareTo(b);
});
final leftOut = <int>[];
for (var k = 0; k < order.length; k++) {
// Clockwise inside the ring: the region lies to its left.
final hole = holes[order[k]].reversed.toList();
if (hole.length < 3) {
leftOut.add(order[k]);
continue;
}
var hi = 0;
for (var i = 1; i < hole.length; i++) {
if (hole[i].x > hole[hi].x) hi = i;
}
final h = hole[hi];
final byDistance = List<int>.generate(keyholed.length, (i) => i)
..sort((a, b) {
final c =
(keyholed[a] - h).length2.compareTo((keyholed[b] - h).length2);
return c != 0 ? c : a.compareTo(b);
});
final obstacles = [
keyholed,
for (var j = k; j < order.length; j++) holes[order[j]],
];
final later = [for (var j = k + 1; j < order.length; j++) holes[order[j]]];
final n = hole.length;
List<Vector2>? joined;
for (final i in byDistance) {
final v = keyholed[i];
if ((v - h).length2 == 0) continue;
if (_blocked(h, v, obstacles)) continue;
final d = (h - v).normalized();
final slit = Vector2(d.y, -d.x) * kSlit; // to the bridge's right
List<Vector2> keyhole(Vector2 hs, Vector2 vs) =>
[...keyholed]..insertAll(i + 1, [
for (var j = 0; j < n; j++) hole[(hi + j) % n],
hs,
vs,
]);
// The slit's three edges, the hole's last edge into H', the return
// H' → V' and V' onward, must cross and touch nothing, though the
// bridge itself is clear. First H' = H + s and V' = V + s, 0.5 mm to
// the bridge's right. Failing that, each end inside its own sector:
// H' between the bridge and the hole's last edge (anticlockwise from
// H → V to H → P), V' between the ring's next edge and the bridge
// (anticlockwise from V → next to V → H); at an acute H or V the
// perpendicular point lies outside it, or an edge from it cuts back
// across the bridge. Failing that too, the next vertex is tried.
var candidate = keyhole(h + slit, v + slit);
if (!_clear(candidate, [i + n, i + n + 1, i + n + 2], later)) {
final hs = _slitEnd(h, v - h, hole[(hi + n - 1) % n] - h, slit);
final vs =
_slitEnd(v, keyholed[(i + 1) % keyholed.length] - v, h - v, slit);
if (hs == h + slit && vs == v + slit) continue;
candidate = keyhole(hs, vs);
if (!_clear(candidate, [i + n, i + n + 1, i + n + 2], later)) continue;
}
joined = candidate;
break;
}
if (joined == null) {
leftOut.add(order[k]);
continue;
}
keyholed
..clear()
..addAll(joined);
}
leftOut.sort();
bool takes(int step, List<Vector2> r) =>
_triangulates(r) && (accepts == null || accepts(step, r));
if (takes(1, keyholed)) return Tint(1, keyholed, leftOut);
if (takes(2, ring)) return Tint(2, ring, leftOut);
return Tint(3, ring, leftOut);
}