Dago:Algoritmo Quadtree

Algorithm::QuadTree - Uma classe Algorithm QuadTree Algorithm em Perl puro.

Outros links

• http://linux.softpedia.com/progDownload/Paramesh-Download-30235.html

Descricao

Algoritmo::QuadTree implementa um algoritmo quadtree (QTA) em puro Perl. Essencialmente, um I<QTA> é usado para acessar uma determinada área de um mapa muito rapidamente. Isto é especialmente útil em encontrar objetos dentro de uma determinada região, ou na detecção de interseção entre os objetos. Na verdade, eu escrevi este módulo de pesquisa rápida através de objetos em um widget L<Tk::Canvas>, mas tenho utilizado em outros programas não-Tk com êxito. É um clássico trade-off entre memória/velocidade.

Muita informação sobre QTAs podem ser encontrados na web. Mas, muito sucintamente, uma quadtree é um modelo de dados hierárquico que recursivamente decompuser um mapa em pequenas regiões. Cada nó na árvore tem 4 nós filhos, cada um dos quais representa um quarto da área que o pai representa. Então, o nó raiz representa o mapa completo. Este mapa é então dividido em 4 quartos iguais, cada um dos quais é representado por um nó filho. Cada uma dessas crianças é agora tratado como um pai, e sua área é recursivamente dividido em 4 áreas iguais, e assim por diante até uma profundidade desejada.

Aqui está um diagrama:

                  ------------------------------
                 |AAA|AAB|       |              |
                 |___AA__|  AB   |              |
                 |AAC|AAD|       |              |
                 |___|___A_______|      B       |
                 |       |       |              |
                 |       |       |              |
                 |   AC  |   AD  |              |
                 |       |       |              |
                  -------------ROOT-------------
                 |               |              |
                 |               |              |
                 |               |              |
                 |      C        |      D       |
                 |               |              |
                 |               |              |
                 |               |              |
                  ------------------------------

que corresponde a quadtree:

                   __ROOT_
                  /  / \  \
                 /  /   \  \
           _____A_  B   C   D
          /  / \  \
         /  /   \  \
    ____AA  AB  AC  AD
   /  / \  \
  /  /   \  \
AAA AAB AAC AAD

Nos diagramas acima, mostro somente os nós através da primeiro ramo de cada nível. A mesma estrutura existe em cada nó. Esta quadtree tem uma profundidade de 4.

Cada objeto no mapa é atribuída ao nodos que intersecta. Por exemplo, se temos um objeto retangular que sobrepões regiões I<AAA> e I<AAC>, será atribuído aos nós I<root>, I<A>, I<AA>, I<AAA> e I<AAC>. Agora, suponhamos que queremos encontrar todos os objetos que cruzam uma determinada área. Em vez de checar todos os objetos, nós verificamos para ver qual dos filhos do nó raiz intersectam a área. Para cada um desses nós, nós recursivamente verificamos I<their> nós crianças, e assim por diante até chegar as folhas da árvore. Finalmente, encontramos todos os objetos que são atribuídos a esses nós folhas e verificamos eles por sobreposições com a área inicial.

Modo de usar

   use Algorithm::QuadTree;

   # cria um objeto quadtree
   my $qt = Algorithm::QuadTree->new(
        -xmin  => 0, -xmax  => 1000, -ymin  => 0, -ymax  => 1000, -depth => 6);

   # adiciona objetos randomicamente
   my $x = my $tag = 1;
   while ($x < 1000) {
     my $y = 1;
     while ($y < 1000) {
       $qt->add($tag++, $x, $y, $x, $y);

       $y += int rand 200;
     }
     $x += int rand 100;
   }

   # acha os objetos dentro de uma certa região
   my $r_list = $qt->getEnclosedObjects(400, 300, 689, 799);