验证2D图中的所有边是否足够远

Question

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

蛮力算法是微不足道的，有没有更有效的算法？

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

Answer 1

[我很想知道rtree索引的想法如何执行，所以我创建了一个小脚本来使用两个非常酷的Python库进行测试：Rtree和shapely该代码段生成

1000个段，这些段的1 并以[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))