Loja 2D aponta para recuperação rápida dos que dentro de um retângulo

Question

Eu tenho um grande número de pontos em 2D e eu quero começar rapidamente aqueles que se encontram em um determinado retângulo. Digamos que um '' é qualquer ponto e 'X' é um ponto que eu quero encontrar dentro de um retângulo que tem 'T' como TopLeft e 'B' como pontos BottomRight:

. . . . . .
. T-----+ .
. | X X | .
. +-----B .
. . . . . .

Eu tentei um std :: set com um functor tipo que classifica o ponto TopLeft no início e no BottomRight no final do set. Ao classificar por valor X em primeiro lugar, isso resultaria nos seguintes pontos que estão sendo encontrados.

. . . . . .
. T-----+ .
X | X X | X
. +-----B .
. . . . . .

Isso significa que eu teria que verificar cada ponto encontrado, se ele realmente está dentro do retângulo. Não é realmente bom.

O que seria uma maneira melhor de fazer isso?

A minha linguagem é C ++ (Windows) e eu tenho o STL, bem como aumentar disponível.

Atualização

Depois de ler as respostas até agora, percebi que eu não ter sido responsável por todos os parâmetros do meu problema: Não há um retângulo fixo. Retângulos pode ser definido pelo usuário em tempo de execução. Este meio de classificação do conjunto de pontos promete ser mais eficiente do que uma busca linear através de todos os aspectos, conforme sugerido pelo Artelius antes desta atualização. Eu ainda vou dar-lhe uma tentativa, embora! Eu não espero que o usuário defina um retângulo muito frequente. Assim, em relação ao esforço de implementação que poderia mostrar-se para ser uma boa solução para mim.

Answer 1

Você pode armazenar os pontos em um índice espacial usando quad ou r-árvores. Em seguida, dado o retângulo que você pode encontrar todos os nós da árvore que se sobrepõem-lo, você teria, então, para comparar cada ponto neste subconjunto para ver se ele cai no retângulo.

Em essência, a árvore espacial ajuda a podar o espaço de busca.

Você pode ser capaz de usar uma solução mais simples, como o particionamento os pontos em intervalos. Diz onde x é de 0,10, como um intervalo, como uma outra 11,20. Qualquer solução que permite que você podar o espaço de busca vai ajudar.

Answer 2

Por favor, veja esta questão . The Brook Algoritmo Repository Stony tem algumas implementações de KDTrees em C ++, embora eles não fazem parte do STL nem Boost.

Answer 3

Classificação de uma matriz leva O ( n log n ) tempo. Basta verificar cada ponto individualmente (sem ordenação) leva O ( n ) tempo.

Ergo, apenas passando e verificar cada ponto é mais rápido do que a classificação. E é mais rápido do que a construção de uma quadtree também.

EDIT: Se você tem muitos retângulos para verificação, é uma história diferente. Mas se você só precisa verificar um número pequeno, fixo de retângulos em seguida, basta fazê-lo da maneira "óbvia"!

Answer 4

usar uma quadtree, e você tem 3 tipos de nós Qtree:

1. nó está fora do retângulo alvo: ignore
2. nó está dentro do retângulo alvo: incluir todos os pontos dentro do nó
3. nó é parcialmente fora do retângulo: fazer uma limites verificar pontos dentro do nó

Answer 5

Após a ligação do Yuval F, achei Pesquisa Faixa , que parece ser o tipo exato de coisa que você está procurando. Eu segui alguns links de lá, e encontrou CGAL , uma biblioteca de código aberto C ++, que implementa uma pesquisa de escala, com exemplos aqui .

Answer 6

A sua função de classificação poderia verificar pontos como eles são adicionados para dentro-da-retângulo ness, e classificar todos os pontos dentro do retângulo antes de todos os pontos fora do retângulo. Você teria que manter o controle de quantos de cada existe, ou usar uma pesquisa binária em todo o conjunto para encontrar o ponto de corte em tempo de pesquisa.