python - 许多 2D 点之间的最短路径（Shapely LineString 中的旅行推销员？）

Question

我试图根据点地面测量创建河流横截面剖面。当尝试LineString从具有公共 ID 的一系列点创建 Shapely 时，我意识到给定点的顺序确实很重要，因为它LineString只会“按索引”连接给定点（以列表给定的顺序连接点）。下面的代码说明了默认行为：

from shapely.geometry import Point, LineString
import geopandas as gpd
import numpy as np
import matplotlib.pyplot as plt

# Generate random points
x=np.random.randint(0,100,10)
y=np.random.randint(0,50,10)
data = zip(x,y)

# Create Point and default LineString GeoSeries
gdf_point = gpd.GeoSeries([Point(j,k) for j,k in data])
gdf_line = gpd.GeoSeries(LineString(zip(x,y)))

# plot the points and "default" LineString
ax = gdf_line.plot(color='red')
gdf_point.plot(marker='*', color='green', markersize=5,ax=ax)

这将产生图像：

问题： Shapely 中是否有任何内置方法可以通过给定的随机 2D 点列表自动创建最合乎逻辑的（又名：最短、最简单、最不交叉……）线？

与默认（红色）相比，您可以在下面找到所需的线（绿色）。

score 3 · Accepted Answer

这是解决我的横截面LineString简化问题的方法。但是，我的解决方案没有正确解决计算上更复杂的任务，即找到通过给定点的最终最短路径。正如评论者所建议的那样，有许多库和脚本可用于解决该特定问题，但如果有人想保持简单，您可以使用对我有用的方法。随意使用和评论！

def simplify_LineString(linestring):

    '''
    Function reorders LineString vertices in a way that they each vertix is followed by the nearest remaining vertix.
    Caution: This doesn't calculate the shortest possible path (travelling postman problem!) This function performs badly
    on very random points since it doesn't see the bigger picture.
    It is tested only with the positive cartesic coordinates. Feel free to upgrade and share a better function!

    Input must be Shapely LineString and function returns Shapely Linestring.

    '''

    from shapely.geometry import Point, LineString
    import math

    if not isinstance(linestring,LineString):
        raise IOError("Argument must be a LineString object!")

    #create a point lit
    points_list = list(linestring.coords)

    ####
    # DECIDE WHICH POINT TO START WITH - THE WESTMOST OR SOUTHMOST? (IT DEPENDS ON GENERAL DIRECTION OF ALL POINTS)
    ####
    points_we = sorted(points_list, key=lambda x: x[0])
    points_sn = sorted(points_list, key=lambda x: x[1])

    # calculate the the azimuth of general diretction
    westmost_point = points_we[0]
    eastmost_point = points_we[-1]

    deltay = eastmost_point[1] - westmost_point[1]
    deltax = eastmost_point[0] - westmost_point[0]

    alfa = math.degrees(math.atan2(deltay, deltax))
    azimut = (90 - alfa) % 360

    if (azimut > 45 and azimut < 135):
        #General direction is west-east
        points_list = points_we
    else:
        #general direction is south-north
        points_list = points_sn

    ####
    # ITERATIVELY FIND THE NEAREST VERTIX FOR THE EACH REMAINING VERTEX
    ####

    # Create a new, ordered points list, starting with the east or southmost point.
    ordered_points_list = points_list[:1]

    for iteration in range(0, len(points_list[1:])):

        current_point = ordered_points_list[-1]  # current point that we are looking the nearest neighour to
        possible_candidates = [i for i in points_list if i not in ordered_points_list]  # remaining (not yet sortet) points

        distance = 10000000000000000000000
        best_candidate = None
        for candidate in possible_candidates:
            current_distance = Point(current_point).distance(Point(candidate))
            if current_distance < distance:
                best_candidate = candidate
                distance = current_distance

        ordered_points_list.append(best_candidate)

    return LineString(ordered_points_list)

score 1 · Accepted Answer

没有内置功能，但 shapely 具有距离功能。

您可以轻松地遍历这些点并计算它们之间的最短距离并构建“最短”路径。

官方 github repo 中有一些示例。

score 0 · Accepted Answer

Google 的 OR-Tools 为解决旅行商问题提供了一种很好且有效的方法：https ://developers.google.com/optimization/routing/tsp 。

遵循他们网站上的教程将为您提供一个解决方案（基于您的示例代码）：

对此：

python - 许多 2D 点之间的最短路径（Shapely LineString 中的旅行推销员？）

3 回答 3

Related

Reference