Qual é o algoritmo mais rápido para descobrir qual ponto do Tipo 1 está mais próximo para cada ponto do Tipo 2 em uma grade retangular?

5

No meu exemplo inventado, eu tenho uma grade retangular de nós, onde cada nó está vazio, do Tipo 1 ou do Tipo 2. Todos os nós são direcionados para os oito nós ao redor deles (horizontal, vertical, diagonal). Para cada um dos nós do Tipo 1, quero encontrar a distância até o nó mais próximo do Tipo 2. Para todos os pontos, suas posições (x, y) na grade são conhecidas.

A abordagem ingênua em que posso pensar é algo assim (em pseudocódigo):

for p1 ∈ Type1Points
    min = ∞
    for p2 ∈ Type2Points
        possibility = max(abs(p1.x-p2.x), abs(p1.y-p2.y))
        if possibility < min
            min = possibility
    output min

Isso parece ser executado em O(|Type1Points|*|Type2Points|) (onde |a| indica o tamanho do conjunto de pontos) No entanto, estou me perguntando se há abordagens ainda mais rápidas para resolver esse problema.

    
por Qqwy 13.03.2017 / 18:48
fonte

1 resposta

5

Um algoritmo eficiente é provavelmente aquele que faz uso de R-trees . O algoritmo seria algo como

type1RTree = new RTree()
for p1 in Type1Points
    type1RTree.insert(p1)
min = inf
for p2 in Type2Points
    nearest_p1 = type1RTree.nearest-neighbor(p2)
    possibility = distance(p2, nearest_p1)
    if possibility < min
        min = possibility
output min

A maioria das linguagens deve ter uma implementação decente de R-tree em algum lugar; você também pode ver o artigo wiki vinculado para esboços de implementação de insert e nearest-neighbor .

    
por 13.03.2017 / 19:42
fonte