Seleção agrupada de vizinhos mais próximos em QGIS

14

Eu tenho uma lista contendo mais de 100.000 pontos no formato lat / long que eu importei no qgis.

Agora, o que estou tentando fazer aqui é agrupar todos esses pontos em grupos de caixas e com isso quero dizer basicamente que quero dividir o mapa em caixas delimitadoras.

Meus requisitos são os seguintes:

  • nenhum grupo em caixa deve ter menos de 100 e não mais de 200 pontos
  • nenhum ponto deve estar localizado em mais de um grupo
  • todos os pontos devem ser baseados no vizinho mais próximo

Como eu consegui isso através do qgis?

Estou assumindo que alguém pode passar algum código de consulta personalizado e salvar os resultados ou as caixas criadas como um shapefile correto? Alguém poderia explicar como isso poderia ser feito e como seria o código?

Como mencionado, meu objetivo é exibir um monte de caixas quadradas como uma camada de shapefile, em que dentro de cada caixa existem pelo menos 100 propriedades e não mais que 200.

qgis postgis postgresql sql proximity NetConstructor.com
fonte
6
Para todos que marcaram esta pergunta como "favorita": por que não a votaram também? Alguém poderia pensar que sua pergunta favorita deve ser uma boa pergunta.
Underdark
1
Por que você precisa de boxe? Se você criar caixas com base na contagem, elas terão tamanhos diferentes de qualquer maneira, portanto, o ladrilho está fora de questão. Provavelmente é mais fácil agrupar polígonos (isto é, casco convexo).
21411
@diciu obrigado pela resposta. Sim, eu acho que um casco convexo seria bom, pois eu poderia transformá-los em caixas depois disso. Qual código eu precisaria usar para fazer isso usando a abordagem do casco convexo?
NetConstructor.com
2
Se você usar cascos convexos, suas caixas delimitadoras (envolvendo os cascos) se sobreporão e sua exigência de um ponto em um único BBOX não será mais satisfeita. Cascos convexos não funcionam como um passo intermediário em direção ao BBOX, mas como um substituto. E mesmo assim, a criação de uma solução genérica estará bastante envolvida.
diciu 21/10

Respostas:

13

Posso levá-lo até lá, assumindo que você descobriu como solicitar (a) a metade mais a leste de um conjunto de pontos e (b) a metade mais a norte de um conjunto de pontos. Destas, é possível obter, é claro, facilmente (c) a metade mais ocidental ou (d) a metade mais austral. (Eu não conheço o QGIS, mas uma maneira de fazer (a) em geral é solicitar a coordenada x mediana e buscar todos os pontos cujas coordenadas x excedem isso. As soluções para (b) - (d) são semelhantes .)

Usando esse recurso, a solução é obtida com uma recursão fácil. Para descrevê-lo, vamos assumir que existe um procedimento Half, implementando as operações anteriores, que recebe dois argumentos: o primeiro é um conjunto de pontos e o segundo é um código igual a truequando o particionamento leste-oeste é desejado e igual ao falsecontrário. Retorna dois subconjuntos de sua entrada que a particionam conforme solicitado.

Procedure Box(P: set of points, i: boolean, n: integer)
Begin
    If (Count(P) > 2*n) then
        {R,S} = Half(P,i)
        Q = Box(R,!i,n) + Box(S,!i,n)
    Else
        Q = {P}
    Endif
    Return Q
End

Nesse pseudocódigo, R e S partem P; Caixa (R,! I, n) é uma partição de R na direção ortogonal , Caixa (S,! I, n) é uma partição de S na direção ortogonal, "+" significa formar a união da teoria dos conjuntos e {} designa um conjunto. (Alternar a direção de divisão cria caixas em vez de faixas.) O parâmetro n especifica o tamanho mínimo de um grupo na partição; o tamanho máximo é 2 n .

Exemplo

Aqui, como ilustração, está um conjunto P de 12.891 pontos aleatórios divididos Box(P,true,100)em grupos com tamanho entre 100 e 200. O algoritmo cria 128 caixas, das quais 37 têm 100 pontos e 91 têm 101 pontos.

whuber
fonte
2
O algoritmo é eficiente. Executando em um único núcleo, processou dez vezes mais pontos (128.910) em 18 segundos. Escala como O (n log (n) log (n)) para n pontos. (Pode ser melhorada para remover um destes elementos de registo (n), mas o esforço é improvável que seja vantajoso.)
whuber
1
@W você usou uma classificação lexicográfica para facilitar o particionamento das coordenadas do ponto?
2
@whuber isto é incrível
dassouki
1
@ Dan Um tipo lexical ajudaria, mas não é necessário. Observe que uma mediana de n valores pode ser encontrada no tempo O (n) (não no tempo O (n log (n))); portanto, a partição de pontos em metades leste-oeste ou metades norte-sul é assintoticamente um O (n ) computação.
whuber