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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 2257 天前的主题，其中的信息可能已经有所发展或是发生改变。

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

第 1 条附言 · 2018-09-19 10:46:27 +08:00

现在准备设几个权重
1.点之间的距离
2.离起点的半径
难道要搞个神经网络？反正公司没事干，搞个网络试试

随机点

交差

串联

平面

17 条回复 • 2018-09-19 14:08:57 +08:00

hearfish

2018-09-19 10:32:44 +08:00 via Android

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

NCry

2018-09-19 10:35:27 +08:00 via iPhone

画圆，这是我的第一反应

Hilong

2018-09-19 10:40:45 +08:00 via Android

贪吃蛇

northernlights

2018-09-19 10:43:08 +08:00

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

jieee

2018-09-19 10:48:24 +08:00

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

coderluan

2018-09-19 11:15:49 +08:00

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

zagreb

2018-09-19 11:17:46 +08:00 via iPhone

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

iloahz

2018-09-19 11:25:48 +08:00 via Android

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

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

Xs0ul

2018-09-19 11:26:04 +08:00

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

3img

2018-09-19 11:42:10 +08:00

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

3img

2018-09-19 11:43:05 +08:00

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

dlsflh

2018-09-19 11:54:07 +08:00

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

LuffyGu

2018-09-19 11:57:48 +08:00

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

SCaffrey

2018-09-19 11:59:24 +08:00 via Android

极角排序？

Yafeng043

2018-09-19 13:02:19 +08:00 via iPhone

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

limitsy

2018-09-19 13:25:24 +08:00

用凸包做？绕圈。

iloahz

2018-09-19 14:08:57 +08:00 via Android

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