Como pesquisar marcadores de ponto de interesse (POI) em um mapa de forma eficiente

May 01 2023

Na Booking.com, somos apaixonados por facilitar a vida de nossos usuários, fornecendo os melhores recursos de pesquisa de propriedades.

Na Booking.com, somos apaixonados por facilitar a vida de nossos usuários, fornecendo os melhores recursos de pesquisa de propriedades. Queremos que os nossos utilizadores tenham toda a informação para escolher o melhor alojamento. Provavelmente não é segredo que a localização da propriedade é um dos critérios mais importantes na escolha de uma acomodação, pois é uma parte importante da experiência da viagem.

O recurso de mapa da Booking.com é uma ferramenta poderosa, pois fornece informações de localização de uma forma muito visual. Em apenas alguns segundos, os usuários podem determinar se a propriedade está ou não em seu local preferido. Porém, geralmente não basta apenas ver a localização do imóvel em si. Também é importante mostrar a localização dos lugares mais interessantes para visitar durante a viagem. A que distância eles estão? Quão fácil é chegar até eles a partir da propriedade?

Para ajudar nossos usuários a responder a essas perguntas, além dos marcadores de propriedade, também exibimos os chamados marcadores de ponto de interesse (POI). Como o nome sugere, esses marcadores destacam locais de interesse para os viajantes, como praias, estações de esqui, pontos turísticos, bem como cidades e aeroportos, os quais fornecem uma melhor compreensão da localização da propriedade para o usuário.

Marcadores de cidade, atração e aeroporto no mapa

Como pesquisar no mapa?

Quando um usuário abre o mapa, geralmente uma área específica, chamada de caixa delimitadora (BBox), fica visível. Tecnicamente falando, um BBox é um retângulo, cujos cantos são representados por 4 pontos geográficos:

Noroeste (NW);
Nordeste (NE);
Sudeste (SE);
Sudoeste (SW).

Caixa delimitadora — a área visível do mapa.

Logicamente, basta mostrar apenas os marcadores de POI que estão dentro desta BBox, porque o resto do mundo não é visível para um usuário. Assim, podemos usar um BBox como nossa chave de pesquisa ao pesquisar o conteúdo do mapa.

Os usuários podem alterar a área visível movendo e ampliando o mapa e o número dessas interações pode ser relativamente alto. Queremos fornecer a melhor experiência ao usuário e fornecer as informações que são exibidas no mapa o mais rápido possível, o que exigiria um mecanismo de pesquisa eficiente que pudesse funcionar com a chave de pesquisa incomum do BBox.

Quando falamos de busca por chave, as árvores de busca são uma solução clássica, e claro que este caso não é exceção! Mas primeiro precisamos encontrar uma maneira de utilizar essa árvore e descobrir como um BBox pode ser usado como uma chave. Para resolver este problema, usaremos uma quadtree.

Quadtree

Uma quadtree é uma árvore de busca na qual cada nó interno tem exatamente quatro filhos. Por que quatro, você pergunta? Uma árvore de busca simples com dois nós filhos geralmente divide o conjunto de busca por dois em cada nível. Um mapa é uma estrutura bidimensional composta por latitude e longitude, em cada nível precisamos dividir cada dimensão em duas partes, o que resulta em quatro quadrantes. Cada nó dessa árvore também seria um BBox. O nó raiz seria o BBox que contém o mundo inteiro, cada nó filho seria um quadrante do BBox pai.

Pesquisa com uma quadtree.

Como nosso objetivo principal é encontrar marcadores para mostrar no mapa, cada nó da árvore também conterá uma quantidade (geralmente relativamente pequena) de marcadores. A representação de código do nó quadtree mais simples ficará assim:

class QuadTreeNode {
   private Set<Marker> markers;
   private BoundingBox bbox;
   private QuadTreeNode[] children; // Always size of 4
   private final int maxEntryCount;

   …
}

Vamos ver como podemos usar a quadtree para encontrar, por exemplo, cinco marcos que estão contidos no BBox. Assuma que cada nó da nossa árvore contém 10 marcos que estão dentro da BBox que representa o nó atual. Aplicamos um BFS e, como de costume, começamos com o nó raiz:

Itere sobre todos os marcadores neste nó e verifique se algum deles cruza o BBox, que é uma chave de pesquisa. É muito simples saber as coordenadas do marco, só precisamos verificar se essas coordenadas estão dentro do retângulo BBox. Se a condição
(SW lat <= Marker lat <= NE lat) && (SW lon <= Marker lon <= NE lon)
for verdadeira, então o marcador está dentro do BBox. Consideramos os marcadores na borda do BBox como interseção.
Salve os marcadores que se cruzam.
Se encontramos cinco pontos de referência, nossa busca acabou.
Se precisarmos encontrar mais pontos de referência, verificamos quais nós filhos se cruzam com a chave de pesquisa fornecida BBox e os salvamos na fila para verificação posterior. Pode ser de um a quatro nós.
Escolha o próximo nó da fila e vá para a etapa 1.

class QuadTree {
       private QuadTreeNode root;

       … 
  
       public Set<Marker> findMarkers(BoundingBox bbox, int n) {
        Set<Marker> foundEntries = new HashSet<>();
        Queue<QuadTreeNode> nextNodesToCheck = new LinkedList<>();
        nextNodesToCheck.add(root);

        while (foundEntries.size() < n && !nextNodesToCheck.isEmpty()) {
            int stillToFind = n - foundEntries.size();
            QuadTreeNode nodeToCheck = nextNodesToCheck.poll();

            List<Marker> currentEntries = nodeToCheck.getIntersectingEntries(bbox, stillToFind);
            foundEntries.addAll(currentEntries);

            if (foundEntries.size() < n) {
                nextNodesToCheck.addAll(
                  nodeToCheck.getIntersectingChildren(bbox)
                );
            }
        }

        return foundEntries;
    }
}

Os marcadores mais importantes serão mantidos no nó raiz, você os verá se diminuir a escala do mapa para o nível em que o mundo inteiro estiver visível. Quando o usuário amplia o mapa, ele verá os marcadores que são os mais importantes para a área visível, mesmo que não estivessem visíveis no nível de zoom inferior.

A importância de um marcador é baseada em critérios personalizados que podem ser definidos por requisitos de negócios. Por exemplo, podemos basear a importância dos marcadores de referência nas avaliações dos usuários.

Caso extremo

Há também um caso interessante que devemos mencionar. Imagine como é o mapa mundi de papel simplista: é um retângulo, cujas bordas laterais são o meridiano 180º à direita e o meridiano -180º à esquerda. Então imagine que o usuário procura aqui por um imóvel.

A caixa delimitadora cruza as “bordas” do mapa.

Neste caso, a longitude SW da BBox será maior que a longitude NE. Precisamos considerar este caso ao verificar o marcador dentro do retângulo BBox. Por exemplo:

Digamos que as coordenadas BBox sejam SW (160, 60), NE (-160, 70). É um BBox válido.
O marcador com coordenadas (-162, 62)não será considerado como interseção com o BBox, pois .SW lon > Marker lon

BCaixa1:SW (160, 60), NE (180, 70)
BBox2:SW (-180, 60), NE (-160, 70)

Divida o BBox em duas partes.

Edifício Quadtree

Felizmente, as árvores de busca não se materializam do nada, então essa é uma das razões pelas quais os engenheiros de software ainda têm seus empregos. Vamos ver como podemos implementar uma quadtree que satisfaça nosso caso de uso.

A princípio, nossa árvore terá apenas um nó raiz que é o mundo inteiro e não conterá marcadores, estará vazio.

Para preencher a árvore com marcadores, precisamos iterar sobre todos os marcadores que temos e inserir cada marcador na árvore. Digamos que cada nó pode conter até 10 marcadores. Então, em cada inserção, fazemos:

Coloque o marcador atual no conjunto de marcadores do nó atual.
Se o tamanho do conjunto de marcadores for <= 10, terminamos — o marcador encontrou seu lugar. Iterar para o próximo marcador.
Se o tamanho do conjunto de marcadores for > 10, precisamos obter o marcador menos importante desse nó e enviá-lo para um dos filhos. (Lembre-se: quanto mais próximo o nó da raiz, maior a importância dos marcadores no nó).
Crie filhos do nó atual se ainda não tiverem sido criados dividindo o BBox do nó em quatro sub-BBoxes.
Procure o BBox filho que cruza com o marcador de prioridade mais baixa.
Coloque recursivamente este marcador no nó filho (ou seja, vá para a etapa 1 acima com o marcador menos importante e o nó filho como entradas).

É assim que a implementação de inserção pode parecer:

class QuadTreeNode {
   // Keeps the lowest priority markers on top of the queue
   private PriorityQueue<Marker> markers; 
   private BoundingBox bbox;
   private QuadTreeNode[] children; // Always size of 4
   private final int maxEntryCount;

   …

   public void insert(Marker marker) {
       markers.add(marker);
       if (markers.size() > maxEntryCount) {
           if (children == null) {
               children = initializeChildren(); // Create 4 quad tree nodes
           }
      
           Marker entryToPassToChild = markers.poll(); // Get the lowest priority marker
           List<QuadTreeNode> intersectingChildren = 
               getIntersectingChildren(entryToPassToChild.getBoundingBox());

           // Marker can be on the edge of the node. 
           // As edge is a shared area among multiple nodes, 
           // markers can belong to multiple nodes.
           for (QuadTreeNode intersectingChild : intersectingChildren) {
               intersectingChild.insert(entryToPassToChild);
           }
      }
   }
     …
}

Conclusão

Uma quadtree é um conceito relativamente simples e (ao mesmo tempo) poderoso que resolve perfeitamente a busca de marcadores por tarefa BBox. Também achamos essa solução altamente escalável, porque tudo o que precisamos fazer para lidar com a carga crescente é dimensionar horizontalmente nosso serviço.

Por exemplo, uma quadtree que armazena mais de 300k marcadores (dependendo da carga do serviço) leva menos de 1 a ~5,5ms para 99%, o que é extremamente rápido para nossos propósitos.