Python中实现无相交直线的点列表排序方法咨询

核心思路 #

利用平面几何的特性就能直接解决问题：

• points2是垂直直线上的等距点，先按Y坐标升序（或降序）排序，得到连续有序的点序列
• 将points1也按Y坐标做相同方向的排序
• 此时两组点按索引一一连接的直线，必然不会相交

方法可行性说明 #

因为points1所有点都在points2所在垂直线的同一侧，当两组点都按Y坐标同方向排序后，任意两条连线都不会形成交叉——这是同侧有序点连线的基本几何结论，无需额外交叉检测即可保证结果正确。

Python 实现代码 #

def rearrange_points(points1, points2):
    # 对points2按Y坐标升序排序
    sorted_points2 = sorted(points2, key=lambda p: p.Y)
    # 对points1按Y坐标做相同顺序的排序
    sorted_points1 = sorted(points1, key=lambda p: p.Y)
    
    # 可选：验证结果（调试用，确保无相交连线）
    def validate(s1, s2):
        lines = [Line(s1[i], s2[i]) for i in range(len(s1))]
        for i in range(len(lines)):
            for j in range(i+1, len(lines)):
                if isIntersect(lines[i], lines[j]):
                    return False
        return True
    
    # 验证通过后返回结果（输入符合条件时必然通过）
    if validate(sorted_points1, sorted_points2):
        return sorted_points1, sorted_points2
    else:
        raise ValueError("排序后仍存在相交连线，请检查输入条件或isIntersect函数")

特殊情况适配 #

如果需要按降序排序（比如原始points2是从上到下排列），只需修改排序参数：

# 降序排序版本
sorted_points2 = sorted(points2, key=lambda p: p.Y, reverse=True)
sorted_points1 = sorted(points1, key=lambda p: p.Y, reverse=True)

关键优势 #

• 时间复杂度仅为O(n log n)，来自排序操作，效率远高于暴力检测重排
• 严格符合要求：不修改点本身，仅调整列表顺序
• 无需依赖复杂的交叉检测逻辑，几何特性保证结果正确性

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