生成不交叉无重复点的LineString：代码效率优化问询

import pandas as pd
import geopandas as gpd
import itertools
from shapely.geometry import Point, LineString, MultiLineString

points = pd.DataFrame({'X':[1, 1, 1, 1, 4, 4, 4, 4],
                     'Y': [1, 2, 3, 4, 1, 2, 3, 4]})

gdf_points = gpd.GeoDataFrame(points, geometry=gpd.points_from_xy(x=points.X, y=points.Y))
gdf_points = gdf_points['geometry']

max_string = 3
start_point = Point(2, 0.5)

需求说明 #

• 从红色点start_point出发创建LineString；
• 每个LineString最多连接max_string个点；
• 当LineString连接点数达到max_string时，从start_point新建LineString；
• 生成的线段不得交叉；
• 每个点仅属于一条线段。

优化需求 #

当前实现通过遍历点的全排列筛选合规线段，但点数量较多时执行时间急剧上升，寻求代码优化方案或辅助工具包。

优化方案 #

1. 核心思路：用极坐标排序替代全排列 #

全排列的时间复杂度是O(n!)，完全没必要。换用极坐标排序的思路：将所有点按相对于start_point的极角排序，按顺序批量取点生成线段，天然满足「不交叉」「点不重复」的要求，时间复杂度仅为O(n log n)（排序的时间）。

2. 代码实现 #

import math

# 计算点相对于起点的极角（用于排序）
def get_polar_angle(point, start):
    dx = point.x - start.x
    dy = point.y - start.y
    return math.atan2(dy, dx)

# 按极角排序所有点
sorted_points = sorted(gdf_points, key=lambda p: get_polar_angle(p, start_point))

# 批量生成符合要求的LineString
line_list = []
for idx in range(0, len(sorted_points), max_string):
    # 每次取max_string个点，不足则取剩余所有
    batch_points = sorted_points[idx:idx+max_string]
    # 线段从start_point出发，依次连接批次内的点
    line_coords = [start_point] + batch_points
    line_list.append(LineString(line_coords))

# 最终生成MultiLineString结果
final_lines = MultiLineString(line_list)

3. 特殊场景处理 #

如果存在多个点与起点的极角相同（即点在同一条射线），可以在排序时增加「到起点的距离」作为二次排序依据，避免线段重叠：

def get_polar_angle_and_distance(point, start):
    dx = point.x - start.x
    dy = point.y - start.y
    angle = math.atan2(dy, dx)
    distance = math.hypot(dx, dy)
    return (angle, distance)

# 先按极角排序，极角相同则按距离远的在后排序
sorted_points = sorted(gdf_points, key=lambda p: get_polar_angle_and_distance(p, start_point))

4. 方案合理性说明 #

• 所有线段从起点出发，沿极角递增/递减的方向连接点，相当于向外辐射的射线，天然不会交叉；
• 每个点仅被分配一次，完全满足「点不重复」要求；
• 批量取点的逻辑自动满足「每条线段最多连接max_string个点」的规则。

内容的提问来源于stack exchange，提问作者Paul