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?

Question

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?

#1 resposta do (5 votos)

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

algorithms graph graph-traversal path-finding

por Qqwy 13.03.2017 / 18:48

fonte

1 resposta

Tags algorithms graph graph-traversal path-finding

Como fazer a Integração Contínua quando as ramificações de desenvolvimento separadas têm diferentes datas de implementação de produção? REST anêmico e DDD

score 5 · Answer 1

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 .