encontrando casas em um raio

Durante uma entrevista, perguntaram-me o seguinte: Um aplicativo imobiliário que lista todas as casas que estão atualmente no mercado (ou seja, à venda) a uma determinada distância (digamos, por exemplo, que o usuário queira encontrar todas as casas a 30 quilômetros), como você projetaria seu aplicativo (estrutura de dados e alogiritmo) para criar esse tipo de serviço?

Alguma ideia? Como você o implementaria? Eu disse a ele que não sabia porque nunca fiz nada relacionado a áreas geográficas antes.

Eles provavelmente estão atrás de uma resposta mencionando a indexação espacial , provavelmente selecionando um banco de dados que fornece indexação espacial pronta para uso , mas você também pode obter alguns pontos ao mencionar que ela pode ser implementada no próprio aplicativo, se necessário, por exemplo, implementando um R -Árvore (pode ser útil se a seleção do banco de dados for corrigida por outros motivos? Mas também demonstrar que você sabe como os bancos de dados espaciais funcionam). A indexação espacial permitirá que você obtenha rapidamente um subconjunto de locais que se encaixam dentro de uma caixa de pesquisa. Você pode refinar ainda mais calculando a distância real (se necessário, apenas o retângulo pode ser bom o suficiente) para que cada um deles faça uma pesquisa verdadeira círculo / elipse

Dado que as distâncias são provavelmente de 20M ou menos, você provavelmente está bem assumindo uma terra plana para calcular a distância, embora você comece a ver erros perceptíveis no final dos 20M, se faixas muito maiores forem necessárias com precisão, você também precisará começar a procurar melhores modelos de distância para o globo, por exemplo, distância de Haversine

é claro que também há uma infinidade de outros detalhes que poderiam ser discutidos, como design da interface do usuário, esquema do banco de dados, que poderiam ser tópicos inteiros por si só

Sempre que você se deparar com uma pergunta como essa e simplesmente não tiver experiência no domínio do problema, é bom fazer algumas coisas.

Primeiro, reconheça que você não possui conhecimentos específicos neste domínio do problema.

Segundo , explique como você resolveria o problema.

Embora não tenha experiência específica ao trabalhar com pesquisa geográfica, estou confiante de que existem algoritmos bem documentados e tecnologias existentes para resolver o problema. Eu os exploraria para obter conhecimento de soluções comuns disponíveis para mim e fazer uma escolha sobre a implementação com base nos requisitos do projeto.

Terceiro , sempre reduza problemas como esse até seus componentes básicos. Você sabe que os locais em um mapa são distribuídos bidimensionalmente. Você sabe que, se você receber x arbitrário, coordenadas y, a distância de cada coordenada a partir de outra coordenada é calculada através da formação de um triângulo e da resolução pelo comprimento desconhecido. Você também deve saber que, se for solicitado que você encontre todas as coordenadas em uma caixa delimitadora, poderá fazer isso simplesmente calculando as extensões da caixa que deseja encontrar e usando simples maior que, menos que lógica ao longo de ambos os eixos.

Por último , nunca contratei um desenvolvedor que parecia desistir de perguntas. Se eu fizer uma pergunta e a pessoa disser "Eu não sei" e nem tentar pensar verbalmente, isso me dá a impressão de que ela não contribuirá para as sessões de brainstorming - o que é crítico nas organizações que estão desenvolvendo software. .

Provavelmente isso é óbvio, mas para muitas aplicações a solução lenta do pobre homem pode ser boa.

Tenha uma tabela em um banco de dados relacional que armazene latitude e longitude. Consulte todos os locais com latitude dentro de 30 milhas e longitude dentro de 20 milhas. Isso fornece um retângulo delimitador do tamanho do menor retângulo delimitador que contém o raio que você realmente deseja pesquisar (e ignora também a curvatura da terra).

Depois, você pega o conjunto retornado (por uma consulta usando índices) e o filtra usando um cálculo preciso da distância.

Portanto, desempenho não eficiente, mas muito eficiente na hora de se desenvolver. Para muitos aplicativos, essa pode ser uma escolha melhor.

Provavelmente, a maneira mais fácil é usar um quadtree para armazenar os locais de suas casas, assumindo a distribuição em um cenário 2D. A pesquisa deve ser bastante direta.

Se você estiver usando um RDBMS habilitado para GIS para armazenar suas coisas, não precisará se preocupar com isso. Veja esta pergunta para obter algumas informações sobre o desempenho dos principais jogadores.