Убедитесь, что все ребра в 2D-графике достаточно далеко друг от друга - PullRequest
Новая
       32

Убедитесь, что все ребра в 2D-графике достаточно далеко друг от друга

0 голосов
/ 07 марта 2020

У меня есть график, где каждый узел имеет координаты в 2D (на самом деле это географический c график с широтой и долготой.) Мне нужно проверить, что если расстояние между двумя ребрами меньше, чем MAX_DIST, то они разделяют узел , Конечно, если они пересекаются, то расстояние между ними равно нулю.

Алгоритм грубой силы тривиален, есть ли более эффективный алгоритм?

Я пытался адаптировать https://en.wikipedia.org/wiki/Closest_pair_of_points_problem к ребрам графа (и игнорировать пары ребер с общим узлом), но это не тривиально.

1 Ответ

1 голос
/ 12 марта 2020

Я был в восторге ios, чтобы посмотреть, как будет работать идея индекса rtree, поэтому я создал небольшой скрипт, чтобы протестировать его, используя две действительно классные библиотеки для Python: Rtree и shapely
Фрагмент генерирует 1000 сегментов с 1 <длина <5 </strong> и координатами в интервале [0, 100] , заполняет index , а затем подсчитывает пары, которые ближе MAX_DIST == 0,1 (с использованием classi c и метода на основе индекса).
В моих тестах метод индекса был примерно 25x быстрее, используя условия выше; это может сильно различаться для вашего набора данных, но результат обнадеживает: 

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

Производительность и правильность метода индекса зависят от того, как распределены ваши сегменты (сколько близко, если у вас очень длинные сегменты , используемые параметры). 

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))
...