Pré RTree passo: Dividir um conjunto de pontos em regiões rectangulares, cada uma contendo um ponto

Question

dada a minha posição atual (lat, long) eu quero encontrar rapidamente o vizinho mais próximo em alguns pontos de problema de interesse. Assim, eu pretendo usar um banco de dados R-Tree, que permite a pesquisa rápida. No entanto, pela primeira vez o banco de dados deve ser preenchido - é claro. Portanto, eu preciso determinar as regiões retangulares que cobre a área, onde cada região contém um ponto de interesse.

A minha pergunta é como faço para pré-processar os dados, isto é, como faço para subdividir a área em destas sub-regiões retangulares? (Eu quero regiões retangulares, porque eles são facilmente adicionados ao RTree - em contraste com as regiões mais gerais Voronoi)

.

/ John

Answer 1

Editar: O abaixo funciona abordagem, mas ignora a característica crítica de R árvores - que o comportamento de divisão de nós R-árvores é bem definido, e mantém uma árvore equilibrada (através B- árvore-como propriedades). Então, na verdade, tudo que você tem a fazer é:

1. Escolha o número máximo de retângulos por página
2. Criar retângulos de sementes (pontos de uso mais distantes um do outro, centroids, qualquer que seja).
3. Para cada ponto, escolha um retângulo para colocá-lo em
   4. Se já cai em um único retângulo, colocá-lo lá
   5. Se isso não acontecer, estender o retângulo que deve ser prorrogado menos (diferentes maneiras de medir saídas "menos" - Obras área)
   6. Se vários retângulos aplicar - escolher um baseado em quão cheia é, ou alguma outra heurística
4. Se ocorrer estouro - use a partição quadrática para mover as coisas ao redor ...
5. E assim por diante, usando algoritmos R-árvores saído de um livro de texto.

Eu acho que o método abaixo é ok para encontrar seus retângulos iniciais de sementes; mas você não deseja preencher todo o seu R-tree dessa forma. Fazendo as divisões e reequilibrar o tempo todo pode ser um pouco caro, então você provavelmente vai querer fazer um pedaço decente do trabalho com a abordagem KD abaixo; não apenas todo o trabalho.

---

A abordagem KD:. Tudo enclose em um retângulo

Se o número de pontos do retângulo é> limiar, varredura na direção D até cobrir a metade dos pontos.

Dividir em retângulos esquerda e direita (ou acima e abaixo) o ponto de divisão).

Chamar o mesmo procedimento recursivamente sobre os novos retângulos, com a próxima direção (se você estava indo para a esquerda para a direita, agora você vai de cima para baixo, e vice-versa).

A vantagem que isso tem sobre a dividir em quadrados abordagem oferecidas por outro cartaz é que ele acomoda distribuições pontuais distorcidas melhor.

Answer 2

Oracle Spatial Cartucho documentação descreve algoritmo tessellation que pode fazer o que quiser. Em suma:

• coloque todos os seus pontos no quadrado
• Se praça contém 1 ponto - índice quadrado
• Se praça não contém pontos - ignorá-lo
• Se praça contém mais de 1 ponto
  • quadrado dividido em 4 quadrados iguais e análise de repetição para cada novo quadrado

resultado deve ser algo como isto:
alt texto http: // Download- uk.oracle.com/docs/cd/A64702_01/doc/cartridg.805/a53264/sdo_ina5.gif

Answer 3

Eu acho que você a algo que falta na declaração do problema. Suponha que você tenha N pontos (x, y) tal que cada ponto tem um X- única e coordenada y. Você pode dividir sua área em retângulos N seguida por apenas dividindo-a em n colunas verticais. Mas isso não ajudá-lo a resolver o problema POI mais próximo facilmente, não é? Então eu acho que você está pensando em algo sobre a estrutura retângulo que você ainda não articulada.

Ilustração:

| | | | |5| | |
|1| | | | |6| |
| | |3| | | | |
| | | | | | | |
| |2| | | | | |
| | | | | | |7|
| | | |4| | | |

Os números são destinos e as linhas verticais mostram uma subdivisão em 7 áreas rectangulares. Mas, claramente, não há muita informação "interessante" na subdivisão. Existe algum critério adicional sobre a subdivisão que você não mencionou?