Qual è l'algoritmo più veloce per individuare il punto di Tipo 1 più vicino per ogni punto di Tipo 2 su una griglia rettangolare?

Question

Qual è l'algoritmo più veloce per individuare il punto di Tipo 1 più vicino per ogni punto di Tipo 2 su una griglia rettangolare?

#1 da (5 voti)

5

Nel mio esempio forzato, ho una griglia rettangolare di nodi, dove ogni nodo è vuoto, di Tipo 1 o di Tipo 2. Tutti i nodi sono diretti agli otto nodi attorno a loro (orizzontale, verticale, diagonale). Per ognuno dei nodi di Tipo 1, voglio trovare la distanza dal nodo più vicino di Tipo 2. Per tutti i punti, le loro posizioni (x, y) sulla griglia sono note.

L'approccio ingenuo a cui riesco a pensare è qualcosa del genere (in pseudocodice):

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

posta Qqwy 13.03.2017 - 18:48

fonte

1 risposta

Leggi altre domande sui tag algorithms graph graph-traversal path-finding

Cosa fare con i rami storici SVN dopo il passaggio a GitFlow? Nome variabile che a volte si riferisce a un oggetto ea volte a una stringa

score 5 · Answer 1

È probabile che un algoritmo efficiente utilizzi R-trees . L'algoritmo sarebbe qualcosa come

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

La maggior parte delle lingue dovrebbe avere un'implementazione di R-tree decente da qualche parte; puoi anche vedere l'articolo wiki collegato per gli schizzi di implementazione di insert e nearest-neighbor .