在一个二维平面上有 N 个随机点，求画出一条不交差路径，来串联这些点

[3img]

现在情况是，按最小距离来画，画出来后，会有线交差情况，求一个思路

[hearfish]

不要求最短路径的话沿着一个方向连起来就行啊

[NCry]

画圆，这是我的第一反应

[Hilong]

贪吃蛇

[northernlights]

z 形的线，极端的情况就是 N 条平行的线全部覆盖了整个面。

[jieee]

有几个最短路径算法，也可以启发式算法搜索路径

[coderluan]

只是要求不交叉吗？直接按 x 轴顺序连接就完了呗，画完了是个心电图，肯定不交叉。

[zagreb]

旅行商问题。看你描述到下一个最近的点，这是局部优化解。用遗传算法吧，我以前用过，答案是很漂亮的不交叉的圈。当然也可能掉进局部优化的坑里，结果是 8 字形。

[iloahz]

从左到右，从上到下，从外到内，从内到外都可以吧。

写了个从左到右的 demo：jsfiddle.net/437p9e8b/37/show

[Xs0ul]

挑个坐标系，按其中一个轴单调增连起来不就行了。前面说的按 x 轴，或者选个中心点极坐标绕圈。

[3img]

@iloahz 感谢 demo，起点是中心点

[3img]

@Xs0ul 绕圈也考虑过，极限情况还是会出现线段重叠的

[dlsflh]

@3img #10 中心点？火影看过没？搓一个螺旋丸不就好了。阿基米德螺旋线这种的？

[LuffyGu]

找出最左，或最右，或最上，或最下的点。然后向这个点的反方向，把点一个一个的连接起来，一条折线。

[SCaffrey]

极角排序？

[Yafeng043]

以中心点为原点左右划分为竖向两块，分别按照楼上说的心电图的走法即可。应该解决问题了吧

[limitsy]

用凸包做？绕圈。

[iloahz]

给定起点的话感觉极角排序比较靠谱，只是注意选取起始角度的问题，当所有点在一个半平面内时需要从边上开始