验证二维图中的所有边彼此之间是否足够远

Question

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

暴力算法很简单，有没有更高效的算法？

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

Answer 1

我很好奇 rtree 索引的想法会如何执行，所以我创建了一个小脚本来使用两个非常酷的库来测试它 Python：Rtree and shapely
该代码段生成 1000 段 1 < 长度 < 5 并且坐标在 [0, 100]间隔，填充 index 然后计算比 MAX_DIST==0.1 更接近的对（使用经典和索引-基于方法）。
在我的测试中，使用上述条件，索引方法大约快 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))

验证二维图中的所有边彼此之间是否足够远

Verify that all edges in a 2D graph are sufficiently far from each other

graph

gis

closest-points