如何用无自交直角折线连接随机点？求可行算法

以下是几种能解决你遇到的点间距过近导致自交问题的实用方法：

1. 凸包分层连接法 #

• 先对所有点计算凸包，将凸包上的点按顺时针（或逆时针）顺序排列，用轴对齐的直角折线连接相邻凸包点（比如从点A(x1,y1)到点B(x2,y2)，选择A→(x1,y2)→B或A→(x2,y1)→B，优先选不穿过凸包内部的路径）。
• 递归处理凸包内部的剩余点，计算内层凸包，再将内层凸包的任意一个点与外层凸包上的某点用直角折线连接——选择外层凸包上离该内层点最近的边，从内层点引直角线到这条边的中点（或任意不与其他线段交叉的位置），确保内层连接被外层包裹，不会产生跨层交叉。
• 这种分层逻辑从外到内构建，天然避免了嵌套交叉的问题，无需频繁调整点的顺序。

2. 网格映射+生成树替换法 #

• 将所有点映射到虚拟网格（每个点对应网格节点，网格精度可根据点的最小间距设置）。
• 使用Prim或Kruskal算法生成最小生成树（MST），生成树本身无环无交叉，保证了点之间的连接逻辑是无自交的。
• 把生成树中的每条直线边替换为轴对齐的直角边：对于两点P(x1,y1)和Q(x2,y2)，有两种直角路径可选，每次替换时检查新路径是否与已存在的直角线段相交（轴对齐线段的相交判断非常简单：水平线段y=a，x范围[x1,x2]；垂直线段x=b，y范围[y1,y2]，只需判断b在[x1,x2]且a在[y1,y2]即可），若相交则切换另一种路径。

3. 排序+固定方向约束法 #

• 先对所有点按x坐标排序（x相同则按y坐标排序），依次连接相邻点。
• 设定固定的方向规则：比如奇数索引的点连接时，先沿水平方向移动到下一个点的x坐标，再垂直移动；偶数索引的点则先垂直移动到下一个点的y坐标，再水平移动。
• 若遇到点间距过近的情况，仅调整当前连接的方向优先级（比如把“先水平后垂直”换成“先垂直后水平”），而非调整点的排序顺序。有序的点序列加上交替的方向约束，能大幅降低后续线段交叉的概率。

补充提示 #

轴对齐线段的交叉判断无需复杂计算，只需比较坐标范围即可，实现成本极低，可集成到任意一种方法中做实时校验。

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