여러 2D 점 사이의 최단 경로 (Shapely LineString 내의 세일즈맨)

Question

필자는 육로 측정을 기반으로 강 단면 프로필을 만들려고했습니다. Shadely LineString을 공통 ID가있는 일련의 점에서 만들려고 할 때 LineString은 주어진 점 'indexwise'(목록에 지정된 점에 연결)을 연결하기 때문에 주어진 점의 순서가 실제로 중요하다는 것을 깨달았습니다. . 아래 코드는 기본 동작을 보여 이미지를 생성 할

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) 

:

질문 : 자동으로 대부분을 만들 것 매끈한 내의 내장 방법이 있나요 논리적 인 012 점의 주어진리스트를 통해 논리적 인 (일명 가장 짧은, 가장 복잡하지 않은 것, 최소 십자가, ...) 줄을?

다음은 기본값 (빨간색)과 비교하여 원하는 행 (녹색)을 찾을 수 있습니다. 매끈한 아무 기능 내장 없지만,

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 repo에 일부 examples이 있습니다.