如何对非凸形状的GPS点进行顺时针排序以生成赛车线

我需要为某高度非凸的赛道生成赛车线，但手里只有无顺序的边界GPS点。想把这些点按顺时针方向排序，让车辆能循迹。尝试过基于重心的旋转排序函数，但对非凸形状无效，函数代码如下：

def rotational_sort(list_of_xy_coords):
    cx, cy = list_of_xy_coords.mean(0)
    x, y = list_of_xy_coords.T
    angles = np.arctan2(x-cx, y-cy)
    indices = np.argsort(angles)
    return list_of_xy_coords[indices]

问题原因 #

基于重心的旋转排序仅适用于凸多边形：它依赖所有点相对于重心的角度单调变化，非凸赛道会存在部分点的角度交叉，导致排序后点的顺序混乱，无法形成连续边界。

解决方案：基于Delaunay三角剖分的边界提取与排序 #

通过三角剖分找到点的邻接关系，提取边界边后构建连续序列，最后调整为顺时针方向：

1. 构建Delaunay三角剖分

利用三角剖分建立点之间的拓扑关系，为后续提取边界做准备：

from scipy.spatial import Delaunay
import numpy as np
from collections import defaultdict

# 替换为你的GPS点数组（N×2的numpy数组）
points = np.array(your_gps_points)
tri = Delaunay(points)

2. 筛选边界边

Delaunay三角剖分中，仅出现在单个三角形内的边即为边界边：

edge_count = defaultdict(int)
edges = []

# 遍历所有三角形的边，统计出现次数
for simplex in tri.simplices:
    for i in range(3):
        p1, p2 = simplex[i], simplex[(i+1)%3]
        # 按点索引排序存储，避免重复统计
        edge_key = tuple(sorted((p1, p2)))
        edge_count[edge_key] += 1
        edges.append((p1, p2))

# 提取仅出现一次的边界边
boundary_edges = [edge for edge in edges if edge_count[tuple(sorted(edge))] == 1]

3. 构建连续的边界点序列

从任意边界点出发，沿着边界边依次连接，形成闭合的边界点序列：

# 构建边界点的邻接表
adj = defaultdict(list)
for p1, p2 in boundary_edges:
    adj[p1].append(p2)
    adj[p2].append(p1)

# 生成闭合边界序列
start_point = boundary_edges[0][0]
current_point = start_point
prev_point = None
boundary_sequence = [current_point]

while True:
    # 获取下一个邻接点（排除前一个点）
    neighbors = adj[current_point]
    next_point = neighbors[0] if neighbors[0] != prev_point else neighbors[1]
    if next_point == start_point:
        break
    boundary_sequence.append(next_point)
    prev_point = current_point
    current_point = next_point

# 得到初步排序的边界点
sorted_points = points[boundary_sequence]

4. 调整为顺时针方向

通过多边形面积的符号判断当前序列方向，若为逆时针则反转序列：

def is_clockwise(points):
    x, y = points.T
    # 计算多边形有向面积，面积为负表示顺时针
    signed_area = np.dot(x, np.roll(y, 1)) - np.dot(y, np.roll(x, 1))
    return signed_area < 0

# 若当前为逆时针，反转序列得到顺时针
if not is_clockwise(sorted_points):
    sorted_points = sorted_points[::-1]

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