graph - 验证 2D 图中的所有边是否彼此相距足够远

Question

我有一个图，其中每个节点都有二维坐标（它实际上是一个地理图，有纬度和经度。）我需要验证如果两条边之间的距离小于 MAX_DIST 则它们共享一个节点。当然，如果它们相交，那么它们之间的距离为零。

蛮力算法很琐碎，有没有更高效的算法？

我正在考虑尝试使https://en.wikipedia.org/wiki/Closest_pair_of_points_problem适应图形边缘（并忽略具有共享节点的边缘对），但这样做并非易事。

Answer 1

我很想看看 rtree 索引的想法是如何执行的，所以我创建了一个小脚本来使用两个非常酷的 Python 库对其进行测试：Rtree和shapely
该片段生成1000 个片段，其中1 < 长度 < 5，坐标位于[0, 100]间隔，填充索引，然后计算比MAX_DIST==0.1更接近的对（使用经典和基于索引的方法）。在我的测试中，使用上述条件，
索引方法的速度提高了大约25 倍；对于您的数据集，这可能会有很大差异，但结果令人鼓舞：

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