查找一组线串后面的点之间的最近距离

Question

我有两个点坐标数据集（代表电气装置），并且希望在给定的一组线串（代表电缆）之后找到两个数据集之间最接近的匹配。我们以以下情况为例：

points1 = gpd.GeoDataFrame({'geometry' : [Point(0,1), Point(3,3)]})
points3 = gpd.GeoDataFrame({'geometry' : [Point(1,0), Point(4,4)]})
lines = gpd.GeoDataFrame({'geometry' : [LineString([Point(0,0),Point(0,4)]),LineString([Point(0,4),Point(4,4)]), LineString([Point(2,4),Point(2,0)]),LineString([Point(1,0),Point(3,0), Point(3,3)])]})

在这里我们可以看到，沿着直线（距离 7）时，红点 (0,1) 最接近绿点 (4,4)，红点 (3,3) 最接近绿点 (1,0)。

如何自动计算每个红点最接近的绿点？这些线有时可以分成更小的线段，如示例中所示，并且并非所有红/绿点都必须位于其中一个线串的端点上。

Answer 1

我选择了 A* 算法来识别道路网络上红点和绿点之间的最短路径。然而，当红点位于线条中间时，会出现一个潜在的问题，导致路径比视觉上明显的更长。为了缓解这种情况，必须实现自定义 A* 函数来计算和排除后步。在当前示例中，从 (0, 0) 到 (0, 1) 有一个后退，必须在自定义 A* 函数中将其减去。总体而言，该程序似乎运行有效。

import matplotlib.pyplot as plt
import networkx as nx
from shapely.geometry import LineString, Point

roads = [LineString([(0, 0), (0, 4)]), LineString([(0, 4), (4, 4)]),
         LineString([(2, 4), (2, 0)]), LineString([(1, 0), (3, 0), (3, 3)])]

reds = [Point(0, 1), Point(3, 3)]
greens = [Point(1, 0), Point(4, 4)]

G = nx.Graph()

for road in roads:
    coords = list(road.coords)
    for i in range(len(coords) - 1):
        G.add_edge(coords[i], coords[i + 1], weight=road.length)

for road in roads:
    plt.plot(*road.xy, color='black')

for red_point in reds:
    plt.scatter(red_point.x, red_point.y, color='red', s=100)

for green_point in greens:
    plt.scatter(green_point.x, green_point.y, color='green', s=100)

for red_point in reds:
    
    for green_point in greens:
        try:
            start_node = min(G.nodes, key=lambda node: Point(node).distance(red_point))
            end_node = min(G.nodes, key=lambda node: Point(node).distance(green_point))

            path = nx.astar_path(G, start_node, end_node, weight='weight')
            path_line = LineString(path)
            plt.plot(*path_line.xy, color='c', linestyle='dashed')

            path_length = path_line.length
            text_position = (red_point.x + 0.5, red_point.y)
            plt.text(*text_position, f"Length: {path_length:.2f}", ha='center', va='center', color='purple')
        except nx.NetworkXNoPath:
            pass
plt.xlabel('X-axis')
plt.ylabel('Y-axis')
plt.grid(True)
plt.show()