Saya memiliki grafik di mana setiap node memiliki koordinat dalam 2D ​​(sebenarnya grafik geografis, dengan lintang dan bujur.) Saya perlu memverifikasi bahwa jika jarak antara dua sisi kurang dari MAX_DIST maka mereka berbagi node. Tentu saja, jika mereka berpotongan, maka jarak di antara mereka adalah nol.

Algoritma brute force sepele, apakah ada algoritma yang lebih efisien?

Saya berpikir untuk mencoba mengadaptasi https://en.wikipedia.org/wiki/Closest_pair_of_points_problem untuk membuat grafik tepi (dan mengabaikan pasangan tepi dengan simpul bersama), tetapi tidak sepele untuk melakukannya.

0
lorg 7 Maret 2020, 17:47

1 menjawab

Jawaban Terbaik

Saya ingin tahu bagaimana kinerja ide indeks rtree, jadi saya membuat skrip kecil untuk mengujinya menggunakan dua pustaka yang sangat keren untuk Python: Rtree dan dengan baik
Cuplikan menghasilkan 1000 segmen dengan 1 < panjang < 5 dan koordinat dalam interval [0, 100], mengisi indeks< /strong> lalu menghitung pasangan yang lebih dekat dari MAX_DIST==0.1 (menggunakan metode klasik dan berbasis indeks).
Dalam pengujian saya, metode indeks sekitar 25x lebih cepat menggunakan kondisi di atas; ini mungkin sangat bervariasi untuk kumpulan data Anda tetapi hasilnya menggembirakan:

found 532 pairs of close segments using classic method
7.47 seconds for classic count
found 532 pairs of close segments using index method
0.28 seconds for index count

Kinerja dan kebenaran metode indeks tergantung pada bagaimana segmen Anda didistribusikan (berapa banyak yang dekat, jika Anda memiliki segmen yang sangat panjang, parameter yang digunakan).

import time
import random
from rtree import Rtree
from shapely.geometry import LineString


def generate_segments(number):
    segments = {}
    for i in range(number):
        while True:
            x1 = random.randint(0, 100)
            y1 = random.randint(0, 100)
            x2 = random.randint(0, 100)
            y2 = random.randint(0, 100)
            segment = LineString([(x1, y1), (x2, y2)])
            if 1 < segment.length < 5:  # only add relatively small segments
                segments[i] = segment
                break
    return segments


def populate_index(segments):
    idx = Rtree()
    for index, segment in segments.items():
        idx.add(index, segment.bounds)
    return idx


def count_close_segments(segments, max_distance):
    count = 0
    for i in range(len(segments)-1):
        s1 = segments[i]
        for j in range(i+1, len(segments)):
            s2 = segments[j]
            if s1.distance(s2) < max_distance:
                count += 1
    return count


def count_close_segments_index(segments, idx, max_distance):
    count = 0
    for index, segment in segments.items():
        close_indexes = idx.nearest(segment.bounds, 10)
        for close_index in close_indexes:
            if index >= close_index:  # do not count duplicates
                continue
            close_segment = segments[close_index]
            if segment.distance(close_segment) < max_distance:
                count += 1
    return count


if __name__ == "__main__":
    MAX_DIST = 0.1
    s = generate_segments(1000)
    r_idx = populate_index(s)
    t = time.time()
    print("found %d pairs of close segments using classic method" % count_close_segments(s, MAX_DIST))
    print("%.2f seconds for classic count" % (time.time() - t))
    t = time.time()
    print("found %d pairs of close segments using index method" % count_close_segments_index(s, r_idx, MAX_DIST))
    print("%.2f seconds for index count" % (time.time() - t))
1
Alonme 31 Maret 2020, 08:00