Condado Braveheart

A primeira imagem tem mais um rolê legal também que é o particionamento das regiões não-passáveis do mapa em retângulos alinhados, essa é a imagem sem a parte da R-Tree em si:



Inclusive, esse particionamento usa um algoritmo de aproximação bem bom (o fator de aproximação é tipo, O(√log n)). O problema é que ele funciona pra retângulos sobrepostos, que eu não queria, então tive que fazer clipping, que é n^2 e dá uma zoada no fator de aproximação do algoritmo, mas digamos que tá decente ainda haha.

A R-Tree vai ajudar bem a otimizar essa parte do clipping (cai pra O(n log n) esperado \o/), e também vai ser bem útil pra uns plugins que eu queria fazer aqui hihihi
Só preciso adaptar ela pra informação dinâmica agora, porque no momento ela está 100% estática 'w'