Analisando algoritmos: QuadTree
Olá!
Esse texto faz parte de uma série. Você encontra os textos anteriores nos links abaixo:
Problema
Imagine que você está desenvolvendo algum tipo de aplicação que represente coordenadas em um espaço 2D. Se o plano em questão for muito grande, como você efetuaria buscas nesse plano de forma eficiente?
Esse tipo de problema pode ocorrer em jogos, buscas espaciais e até mesmo compressão de imagens. Em jogos, você pode querer buscar objetos nesse plano sem percorrer cada coordenada, pois isso seria muito ineficiente. Em aplicações relacionadas a buscas espaciais, parece relativamente intuitivo armazenar os dados de uma forma otimizada para buscas posteriores. Por fim, em compressão de imagens, podemos otimizar a compressão ao representar a imagem como um plano 2D e dividi-la em partes, para aplicar técnicas de compressão em partes específicas ao invés de percorrer a matriz completamente.
Então, como percorrer espaços 2D de forma eficiente?
Um algoritmo que resolve essa categoria de problemas muito bem são QuadTrees.
Como funciona
O Quadtree divide recursivamente o espaço em quadrantes, organizando os dados em uma estrutura de árvore. Cada nó na árvore representa um quadrante no espaço e pode ter até quatro filhos, correspondentes aos quadrantes menores. A divisão continua até que os quadrantes atinjam um tamanho mínimo ou uma condição específica seja satisfeita.
Essa estrutura permite uma busca eficiente em regiões específicas do espaço, reduzindo a complexidade de tempo em comparação com abordagens que não utilizam subdivisão. Perceba a subdivisão acontecendo em quadrados progressivamente menores, como no exemplo abaixo:
Implementação em código
Aqui está um exemplo básico de implementação de um Quadtree em Python para representar pontos em um espaço bidimensional:
import random
import matplotlib.pyplot as plt
# classe que representa um ponto no plano
class Point:
def __init__(self, x, y):
self.x = x
self.y = y
# classe que representa a quadtree em si
class QuadTree:
def __init__(self, boundary, capacity):
self.boundary = boundary
self.capacity = capacity
self.points = []
self.divided = False
# funcão que divide a quadtree
# perceba que são usadas os quatro vértices de um quadrado para
# se encontrar os limites e subdividir o quadrado em partes menores
# dentro desse espaço
def subdivide(self):
x = self.boundary.x
y = self.boundary.y
w = self.boundary.w
h = self.boundary.h
ne = Rectangle(x + w / 2, y + h / 2, w / 2, h / 2)
self.northeast = QuadTree(ne, self.capacity)
nw = Rectangle(x - w / 2, y + h / 2, w / 2, h / 2)
self.northwest = QuadTree(nw, self.capacity)
se = Rectangle(x + w / 2, y - h / 2, w / 2, h / 2)
self.southeast = QuadTree(se, self.capacity)
sw = Rectangle(x - w / 2, y - h / 2, w / 2, h / 2)
self.southwest = QuadTree(sw, self.capacity)
self.divided = True
# insere um ponto em um lugar válido na quadtree
def insert(self, point):
# está dentro dos limites?
if not self.boundary.contains(point):
return False
# está dentro da capacidade?
if len(self.points) < self.capacity:
self.points.append(point)
return True
else:
# a subdivisão ocorre sob demanda
# ao tentar adicionar um ponto novo
if not self.divided:
self.subdivide()
if self.northeast.insert(point):
return True
elif self.northwest.insert(point):
return True
elif self.southeast.insert(point):
return True
elif self.southwest.insert(point):
return True
# exibe a quadtree
def show(self):
plt.xlim(-500, 500)
plt.ylim(-500, 500)
self.boundary.show()
# exibe os pontos
for point in self.points:
plt.plot(point.x, point.y, "bo")
# se foi divida, exibe os vertices
if self.divided:
self.northeast.show()
self.northwest.show()
self.southeast.show()
self.southwest.show()
# abstração de um quadrado
class Rectangle:
def __init__(self, x, y, w, h):
self.x = x
self.y = y
self.w = w
self.h = h
# o ponto está dentro do espaço que esse objeto representa?
def contains(self, point):
return (
point.x >= self.x - self.w
and point.x <= self.x + self.w
and point.y >= self.y - self.h
and point.y <= self.y + self.h
)
# desenha o objeto no plano 2D, pela matplotlib
def show(self):
plt.gca().add_patch(
plt.Rectangle(
(self.x - self.w, self.y - self.h),
2 * self.w,
2 * self.h,
fill=False,
color="red",
)
)
# altere aqui as opções da quadtree
# essa linha altera o tamanho
boundary = Rectangle(0, 0, 400, 400)
# essa linha altera a quantidade de pontos dentro
# do quadrado
quadtree = QuadTree(boundary, 3)
for _ in range(100):
# Inserir alguns pontos aleatórios
point = Point(random.uniform(-500, 500), random.uniform(-500, 500))
quadtree.insert(point)
# Mostrar a quadtree
quadtree.show()
plt.show()Rodando esse código, temos o seguinte resultado:
Lembrando que como os pontos são aleatórios no código, caso você execute esse código o resultado será diferente da imagem.
Se o código te pareceu contra-intuitivo ou algo difícil demais, tá tudo bem, ninguém acorda de manhã com a ideia de uma QuadTree e com a implementação pronta na cabeça. Eu achei esse material bem esclarecedor sobre o assunto se você quiser acompanhar passo-a-passo.
Opções alternativas
Octrees pode ser usada para espaços tridimensionais, como jogos 3D. Esse tipo de algoritmo pode ser usado para detecção de colisões. Apesar de parecer simples a ideia, detecção de colisões é um assunto a parte dentro do desenvolvimento de jogos e possui uma complexidade considerável.
KD-trees podem ser usadas para além de busca em espaços multidimensionais, também podem ser usadas para problemas de classificação e agrupamento de dados.
No exemplo abaixo, cada ponto (em vermelho), é uma árvore que possui dados adicionais. A direita da imagem, o ponto (51,75) foi expandido, revelando uma arvóre com 8 nós, o que seria uma forma de representar que esses dados estão relacionados de alguma forma:
Esse tipo de algoritmo geralmente pode ser usado em conjunto com uma técnica de análise chamada K-Nearest Neighbors (KNN). Não vou adentrar em muitos detalhes porque está fora da minha área de expertise, mas eu espero que a relação entre este mecanismo e análise de dados agrupados tenha ficado explícita, pelo menos.
Em todos esses exemplos, a ideia é a mesma (recursividade na divisão de um espaço, para otimizar a busca de pontos exibidos em um plano). O que muda entre eles é a complexidade da busca em si e o qual o propósito pretendido.
Portanto, a mensagem desse texto é: esse tipo de algoritmo existe. Caso um dia você precise resolver algum problema similar, ter visto esse material alguma vez na vida pode te ajudar. Espero que este texto seja útil para você de alguma forma, afinal, escrevi para isso! =)
Até!
Você gostou do conteúdo e gostaria de fazer mentoria comigo? Clique aqui e descubra como.
