deadleaves.acceleration.quadtree
================================

.. py:module:: deadleaves.acceleration.quadtree

.. autoapi-nested-parse::

   Spatial acceleration for dead leaves coverage tracking.

   A quadtree that tracks which regions of the canvas still contain uncovered
   pixels.  Fully covered subtrees are pruned from future queries, so late in
   the sampling process, when most of the canvas is filled, only the sparse
   frontier of remaining gaps is visited.



Classes
-------

.. autoapisummary::

   deadleaves.acceleration.quadtree.CoverageQuadTree


Module Contents
---------------

.. py:class:: CoverageQuadTree(image_shape: tuple[int, int], position_mask: torch.Tensor, segmentation_map: torch.Tensor, min_tile: int = 16)

   Quadtree that tracks uncovered pixels in the segmentation map.

   Build once before the sampling loop, then call :meth:`query_live_tiles`
   to get only the leaf tiles that (a) still contain uncovered pixels *and*
   (b) overlap a given AABB.  After writing into the segmentation map,
   call :meth:`update_tile` on each affected tile to propagate coverage
   status upward.

   Args:
       image_shape:
           (H, W) of the canvas.
       position_mask:
           Integer tensor (H, W) — 1 where sampling is allowed.  Tiles
           that fall entirely outside the position mask are born dead.
       min_tile:
           Minimum tile edge length.  Must be a power of two.


   .. py:attribute:: _seg
      :type:  torch.Tensor

      Segmentation map



   .. py:attribute:: _pos
      :type:  torch.Tensor

      Position mask



   .. py:attribute:: _min_tile
      :type:  int
      :value: 16


      Minimum tile edge length.



   .. py:attribute:: _H
      :type:  int

      Height of canvas



   .. py:attribute:: _W
      :type:  int

      Width of canvas



   .. py:attribute:: _root
      :type:  Node

      Root node of Quadtree



   .. py:method:: _build(y0: int, x0: int, y1: int, x1: int) -> Node

      Build node for given canvas region

      Args:
          y0, x0, y1, x1:
              Half-open pixel region [y0, y1) x [x0, x1).



   .. py:property:: has_live_nodes
      :type: bool


      True while any uncovered, mask-allowed pixel remains.



   .. py:method:: query_live_tiles(y_min: int, x_min: int, y_max: int, x_max: int) -> list[Node]

      Return all alive leaf nodes overlapping the given AABB.

      Args:
          y_min, x_min, y_max, x_max:
              Query bounding box (not clipped — can exceed canvas).

      Returns:
          List of alive leaf Node objects whose regions intersect the
          query box.



   .. py:method:: _query(node: Node, y_min: int, x_min: int, y_max: int, x_max: int, out: list[Node]) -> None

      Recursively collect all leaf nodes that overlap a query rectangle.

      Starting from ``node``, this method traverses the tree and appends
      all *alive* leaf nodes whose bounding boxes overlap the given
      axis-aligned query region to ``out``.

      Args:
          node (Node):
              The current node to test and recurse into.
          y_min, x_min, y_max, x_max:
              Boundaries of query rectangle.
          out (list[Node]):
              List that is populated in-place with all matching leaf nodes.



   .. py:method:: update_tile(tile: Node) -> None

      Re-check a leaf tile and propagate status up the tree.

      Call this after writing pixels into the segmentation map within
      *tile*'s region.  If the tile is now fully covered, it is marked
      dead and the change bubbles up.



   .. py:method:: _propagate_up() -> None

      Walk the entire tree bottom-up and collapse dead subtrees.

      This is cheap because the tree has O(N / min_tile²) leaf nodes and
      is only called when a tile dies — which can happen at most once per
      tile over the whole run.



   .. py:method:: _propagate_node(node: Node) -> bool

      Returns True if node is alive.