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

Question

我试图根据点terrestical度量创建河流横截面配置文件。当试图用一系列具有通用id的点创建Shapely LineString时，我意识到给定点的顺序非常重要，因为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) 

这将产生图像：

问：是否有内匀称任何内置的方法，将自动创建最逻辑（又名：最短，最不复杂，最不是十字交叉，......）通过给定的随机2D点列表？

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

Answer 1

这是什么解决了我的横断面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) 

Answer 2

有一个在功能上没有建成，但身材匀称有一个distance功能。

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

官方github回购中有一些examples。