classes.c51_quadtree_splitter

  1import random
  2from typing import NamedTuple
  3
  4
  5Coordinates = tuple[float, float, float, float]
  6
  7
  8class KQuadtreeNode(NamedTuple):
  9    """A single quadtree node.
 10
 11    Attributes:
 12            coords: Rectangle as (x, y, width, height).
 13            depth: Depth level where this node appears.
 14            nodeIndex: Stable breadth-first index used for lineage.
 15    """
 16
 17    coords: Coordinates
 18    depth: int
 19    nodeIndex: int
 20
 21
 22class KQuadtreeSplitter:
 23    """Reusable quadtree splitter with Fibonacci-biased subdivision."""
 24
 25    Node = KQuadtreeNode
 26
 27    def __init__(
 28        self,
 29        splitBias: float = 0.65,
 30        splitDecay: float = 0.55,
 31        minSize: float = 36,
 32        seed: int | None = None,
 33    ):
 34        self.splitBias = splitBias
 35        self.splitDecay = splitDecay
 36        self.minSize = minSize
 37        self.seed = seed
 38
 39    def _fib(self, n: int) -> int:
 40        a, b = 1, 1
 41        for _ in range(n):
 42            a, b = b, a + b
 43        return a
 44
 45    def _fibRatio(self, step: int) -> float:
 46        # Consecutive Fibonacci division ratio, converging toward ~0.618.
 47        return self._fib(step + 2) / self._fib(step + 3)
 48
 49    def _split4Fib(
 50        self,
 51        coords: Coordinates,
 52        depth: int,
 53        focusPoint: tuple[float, float],
 54    ) -> list[Coordinates]:
 55        x, y, w, h = coords
 56
 57        rxBase = self._fibRatio(depth)
 58        ryBase = self._fibRatio(depth + 1)
 59
 60        fx, fy = focusPoint
 61        cx = x + w * 0.5
 62        cy = y + h * 0.5
 63
 64        # Keep Fibonacci ratio and flip direction toward one focus point.
 65        rx = 1 - rxBase if fx >= cx else rxBase
 66        ry = 1 - ryBase if fy >= cy else ryBase
 67
 68        wLeft = w * rx
 69        wRight = w - wLeft
 70        hBottom = h * ry
 71        hTop = h - hBottom
 72
 73        return [
 74            (x, y, wLeft, hBottom),
 75            (x + wLeft, y, wRight, hBottom),
 76            (x, y + hBottom, wLeft, hTop),
 77            (x + wLeft, y + hBottom, wRight, hTop),
 78        ]
 79
 80    def buildNodes(
 81        self,
 82        coords: Coordinates,
 83        maxDepth: int,
 84    ) -> list[KQuadtreeNode]:
 85        """Build quadtree nodes and return them as named tuples."""
 86        rng = random.Random(self.seed)
 87
 88        x, y, w, h = coords
 89        focusPoint = (x + w * rng.random(), y + h * rng.random())
 90
 91        level: list[tuple[Coordinates, int]] = [(coords, 0)]
 92        nodes: list[KQuadtreeNode] = []
 93
 94        for depth in range(maxDepth + 1):
 95            for nodeCoords, nodeIndex in level:
 96                nodes.append(
 97                    KQuadtreeNode(
 98                        coords=nodeCoords,
 99                        depth=depth,
100                        nodeIndex=nodeIndex,
101                    )
102                )
103
104            if depth < maxDepth:
105                nextLevel: list[tuple[Coordinates, int]] = []
106                for c, nodeIndex in level:
107                    _, _, cw, ch = c
108                    forceFirstSplit = maxDepth > 0 and depth == 0 and nodeIndex == 0
109                    splitOk = cw > self.minSize and ch > self.minSize
110                    splitProb = self.splitBias * (self.splitDecay**depth)
111                    splitGate = rng.random() < splitProb
112                    canSplit = forceFirstSplit or (splitOk and splitGate)
113
114                    if canSplit:
115                        children = self._split4Fib(
116                            c,
117                            depth=depth,
118                            focusPoint=focusPoint,
119                        )
120                        for childIndex, child in enumerate(children):
121                            nextLevel.append((child, nodeIndex * 4 + childIndex + 1))
122                    else:
123                        # Keep some nodes un-split for in-between visual density.
124                        nextLevel.append((c, nodeIndex))
125
126                level = nextLevel
127
128        return nodes