許多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。