Quadtrees are trees used to efficiently store data of points on a two-dimensional space. In this tree, each node has at most four children. In nim language.

qt.nim

import std/math

type
  Point* = object
    x*, y*: float

  Node* = object
    pos*: Point
    data*: int
    radius*: float

  Quad* = ref object
    topLeft*, botRight*: Point
    n*: ptr Node
    topLeftTree*, topRightTree*, botLeftTree*, botRightTree*: Quad

proc distance*(p1, p2: Point): float =
  let dx = p1.x - p2.x
  let dy = p1.y - p2.y
  return sqrt(dx * dx + dy * dy)

proc overlaps*(node1, node2: Node): bool =
  let dist = distance(node1.pos, node2.pos)
  return dist <= (node1.radius + node2.radius)

proc newPoint*(x, y: float): Point =
  result.x = x
  result.y = y

proc newNode*(pos: Point, data: int, radius: float): Node =
  result.pos = pos
  result.data = data
  result.radius = radius

proc newQuad*(topL, botR: Point): Quad =
  new(result)
  result.topLeft = topL
  result.botRight = botR

# proc inBoundary*(self: Quad, p: Point, radius: float = 0): bool =
#   echo "Checking boundary for point (", p.x, ", ", p.y,
#        ") with radius ", radius,
#        " against quad (", self.topLeft.x, ",", self.topLeft.y,
#        ") to (", self.botRight.x, ",", self.botRight.y, ")"
#   result =
#     p.x - radius >= self.topLeft.x and
#     p.x + radius <= self.botRight.x and
#     p.y - radius >= self.topLeft.y and
#     p.y + radius <= self.botRight.y
#   echo "In boundary result: ", result

proc inBoundary*(self: Quad, p: Point, radius: float = 0): bool =
  let
    expandedTopLeft = newPoint(self.topLeft.x - radius, self.topLeft.y - radius)
    expandedBotRight = newPoint(self.botRight.x + radius, self.botRight.y + radius)
  result =
    p.x >= expandedTopLeft.x and
    p.x <= expandedBotRight.x and
    p.y >= expandedTopLeft.y and
    p.y <= expandedBotRight.y

proc insert*(self: var Quad, node: Node) =
  echo "Attempting to insert node at (", node.pos.x, ", ", node.pos.y, ")"

  if self == nil:
    echo "Quad is nil"
    return

  if not self.inBoundary(node.pos, node.radius):
    echo "Node is outside quad boundary"
    return

  if abs(self.topLeft.x - self.botRight.x) <= 1 and
     abs(self.topLeft.y - self.botRight.y) <= 1:
    if self.n == nil:
      echo "Inserting node in leaf quad"
      self.n = createShared(Node)
      self.n[] = node
    return

  let midX = (self.topLeft.x + self.botRight.x) / 2
  let midY = (self.topLeft.y + self.botRight.y) / 2

  if midX >= node.pos.x:
    if midY >= node.pos.y:
      if self.topLeftTree == nil:
        self.topLeftTree = newQuad(
          self.topLeft,
          newPoint(midX, midY)
        )
      self.topLeftTree.insert(node)
    else:
      if self.botLeftTree == nil:
        self.botLeftTree = newQuad(
          newPoint(self.topLeft.x, midY),
          newPoint(midX, self.botRight.y)
        )
      self.botLeftTree.insert(node)
  else:
    if midY >= node.pos.y:
      if self.topRightTree == nil:
        self.topRightTree = newQuad(
          newPoint(midX, self.topLeft.y),
          newPoint(self.botRight.x, midY)
        )
      self.topRightTree.insert(node)
    else:
      if self.botRightTree == nil:
        self.botRightTree = newQuad(
          newPoint(midX, midY),
          self.botRight
        )
      self.botRightTree.insert(node)

proc quadIntersectsSearchArea(quadTopLeft, quadBotRight: Point, center: Point, radius: float): bool =
    let
      closestX = clamp(center.x, quadTopLeft.x, quadBotRight.x)
      closestY = clamp(center.y, quadTopLeft.y, quadBotRight.y)
      closestPoint = newPoint(closestX, closestY)
      dist = distance(center, closestPoint)
    echo "Quad area check: dist = ", dist, " radius = ", radius  # Debugging line
    return dist <= radius

proc traverseQuad(quad: Quad, center: Point, radius: float, result: var seq[ptr Node]) =
    if quad == nil: return

    # Если в квадранте есть узел
    if quad.n != nil:
      let dist = distance(quad.n.pos, center)
      echo "Checking node at (", quad.n.pos.x, ", ", quad.n.pos.y,
           ") with dist: ", dist, " radius: ", radius,
           " node radius: ", quad.n.radius  # Debugging line
      if distance(quad.n.pos, center) <= radius + quad.n.radius:
        result.add(quad.n)
      return

    # Проверка пересечения квадранта с областью поиска
    let canTraverseTopLeft = quad.topLeftTree != nil and
      quadIntersectsSearchArea(quad.topLeftTree.topLeft, quad.topLeftTree.botRight, center, radius)
    let canTraverseTopRight = quad.topRightTree != nil and
      quadIntersectsSearchArea(quad.topRightTree.topLeft, quad.topRightTree.botRight, center, radius)
    let canTraverseBottomLeft = quad.botLeftTree != nil and
      quadIntersectsSearchArea(quad.botLeftTree.topLeft, quad.botLeftTree.botRight, center, radius)
    let canTraverseBottomRight = quad.botRightTree != nil and
      quadIntersectsSearchArea(quad.botRightTree.topLeft, quad.botRightTree.botRight, center, radius)

    # Рекурсивный спуск в пересекающиеся квадранты
    if canTraverseTopLeft: traverseQuad(quad.topLeftTree, center, radius, result)
    if canTraverseTopRight: traverseQuad(quad.topRightTree, center, radius, result)
    if canTraverseBottomLeft: traverseQuad(quad.botLeftTree, center, radius, result)
    if canTraverseBottomRight: traverseQuad(quad.botRightTree, center, radius, result)

proc findNearbyNodes*(self: Quad, center: Point, radius: float): ref seq[ptr Node] =
  new(result)  # Allocate a new reference to a sequence
  result[] = @[]  # Initialize the sequence inside the reference
  traverseQuad(self, center, radius, result[])  # Pass the actual radius
  return result

# Пример использования
proc main() =
  # Создаем QuadTree с большими границами
  var center = newQuad(newPoint(0, 0), newPoint(10, 10))

  # Создаем узлы с радиусами
  let a = newNode(newPoint(1, 1), 1, 0.5)
  let b = newNode(newPoint(2, 5), 2, 0.3)
  let c = newNode(newPoint(7, 6), 3, 1.0)
  let d = newNode(newPoint(1.6, 1.6), 4, 0.4)

  # Вставляем узлы
  center.insert(a)
  center.insert(b)
  center.insert(c)
  center.insert(d)

  # Проверка коллизий для точки с радиусом поиска
  let searchPoint = newPoint(1.5, 1.5)
  let searchRadius = 5.0
  let nearbyNodes = center.findNearbyNodes(searchPoint, searchRadius)

  echo "Nearby nodes for point (", searchPoint.x, ", ", searchPoint.y, ") with radius ", searchRadius, ":"
  for node in nearbyNodes[]:
    let dist = distance(node.pos, searchPoint)
    echo "Node data: ", node.data,
         " at (", node.pos.x, ", ", node.pos.y,
         ") with radius ", node.radius,
         " (distance: ", dist, ")"

main()