你的问题本质是两层对应节点的非交叉布线问题，属于计算几何和图论中非交叉匹配的延伸场景。先直接给你几个高效的算法方向，再聊聊网格方案的优化空间：

一、优先考虑：单调链节点定位法 #

这是最直接且高效的解法，完全不需要暴力搜索，核心思路是利用单调顺序避免交叉：

1. 先统一排序点集
   假设你的两层是水平分布的（Layer1在上，Layer2在下），先把Layer1的点{A1,B1,C1,D1,E1}按x坐标从小到大（或从左到右）排序。因为A1对应A2、B1对应B2，所以Layer2的点也要跟着这个对应关系排序——也就是排序后Layer2的顺序是[A2,B2,C2,D2,E2]，对应Layer1排序后的顺序。

2. 生成中间层节点
   在Layer1和Layer2的垂直中线位置（或者任意你指定的中间层位置），生成一组和点对数量相同的跨层节点{S1,S2,S3,S4,S5}。让这些节点的x坐标和Layer1排序后的对应点x坐标保持一致（或者按完全相同的单调递增/递减顺序排列）。

3. 连线即可
   直接连接A1→S1→A2、B1→S2→B2……以此类推。因为所有连线都是按单调顺序排列的，Layer1到中间层、中间层到Layer2的连线都不会交叉。

这个方法的时间复杂度是O(n log n)（主要消耗在排序上），节点数量刚好等于点对数量，完全适配点顺序变化的场景——不管点怎么换顺序，只要重新排序中间节点就行，不需要调整节点数量。

二、复杂场景：平面嵌入非交叉路由算法 #

如果你的点在层内的排列不是单调的（比如Layer1的点是乱序分布的），可以用这个思路：
把Layer1和Layer2的点看作两个顶点集，对应点对是需要连接的边，中间层节点相当于把每条边拆成两段。我们需要让中间节点的排列顺序，同时满足Layer1→中间节点、中间节点→Layer2的所有连线都不交叉。

这里可以用贪心策略：

• 先固定Layer1点的遍历顺序（比如从左到右遍历Layer1的点），然后对Layer2的对应点，按它们在Layer1中的遍历顺序，将中间节点按相同顺序排列。这样两边的连线都会形成非交叉的匹配，不会出现交叉问题。

三、关于网格方案的优化价值 #

你的网格思路是有优化空间的，但完全不需要用全网格暴力搜索：

1. 砍掉冗余网格：不需要生成n×n的网格，只需要在中间层生成一条线性的候选节点线（比如两层的中线）就足够了。因为跨层节点只需要按顺序排列在这条线上，就能避免交叉，多余的网格点都是冗余的。
2. 替换暴力搜索：把网格方案简化为一维候选集后，直接用上面的单调排序法匹配节点，时间复杂度从O(n²)暴力搜索降到O(n log n)，效率提升非常明显。
3. 特殊场景适配：如果你的场景必须用二维网格（比如有空间约束不能用线性排列），可以用分层贪心选择：先按x坐标分组，再按y坐标排序，保证每组内的节点顺序和点对顺序一致，同样能避免交叉。

最后提醒一句：只要保证中间节点的排列顺序和Layer1、Layer2的对应点对顺序单调同序，就能从根本上避免层内连线交叉，这是解决这类问题的核心逻辑。

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