Самый короткий путь между многими двумерными точками (коммивояжер в Shapely LineString?)

Question

Я пытался создать профили поперечного сечения реки на основе точечных измерений. При попытке создать Shapely LineString из серии точек с общим идентификатором я понял, что порядок заданных точек действительно имеет значение, так как 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) 

Это будет производить изображение:

Вопрос: Есть ли встроенный метод в стройную, который автоматически создает наиболее логический (ака: кратчайший, наименее сложный, наименьший крест-крест, ...) через данный список случайных двумерных точек?

Ниже вы можете найти нужную строку (зеленый) по сравнению с по умолчанию (красный).

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.