V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
3img
V2EX  ›  程序员

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

  •  
  •   3img · 2018-09-19 10:13:22 +08:00 · 3035 次点击
    这是一个创建于 2017 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

    第 1 条附言  ·  2018-09-19 10:46:27 +08:00
    现在准备设几个权重
    1.点之间的距离
    2.离起点的半径
    难道要搞个神经网络?反正公司没事干,搞个网络试试
    17 条回复    2018-09-19 14:08:57 +08:00
    hearfish
        1
    hearfish  
       2018-09-19 10:32:44 +08:00 via Android
    不要求最短路径的话沿着一个方向连起来就行啊
    NCry
        2
    NCry  
       2018-09-19 10:35:27 +08:00 via iPhone
    画圆,这是我的第一反应
    Hilong
        3
    Hilong  
       2018-09-19 10:40:45 +08:00 via Android
    贪吃蛇
    northernlights
        4
    northernlights  
       2018-09-19 10:43:08 +08:00
    z 形的线,极端的情况就是 N 条平行的线全部覆盖了整个面。
    jieee
        5
    jieee  
       2018-09-19 10:48:24 +08:00
    有几个最短路径算法,也可以启发式算法搜索路径
    coderluan
        6
    coderluan  
       2018-09-19 11:15:49 +08:00
    只是要求不交叉吗?直接按 x 轴顺序连接就完了呗,画完了是个心电图,肯定不交叉。
    zagreb
        7
    zagreb  
       2018-09-19 11:17:46 +08:00 via iPhone   ❤️ 1
    旅行商问题。看你描述到下一个最近的点,这是局部优化解。用遗传算法吧,我以前用过,答案是很漂亮的不交叉的圈。当然也可能掉进局部优化的坑里,结果是 8 字形。
    iloahz
        8
    iloahz  
       2018-09-19 11:25:48 +08:00 via Android   ❤️ 1
    从左到右,从上到下,从外到内,从内到外都可以吧。

    写了个从左到右的 demo:jsfiddle.net/437p9e8b/37/show
    Xs0ul
        9
    Xs0ul  
       2018-09-19 11:26:04 +08:00
    挑个坐标系,按其中一个轴单调增连起来不就行了。前面说的按 x 轴,或者选个中心点极坐标绕圈。
    3img
        10
    3img  
    OP
       2018-09-19 11:42:10 +08:00
    @iloahz 感谢 demo,起点是中心点
    3img
        11
    3img  
    OP
       2018-09-19 11:43:05 +08:00
    @Xs0ul 绕圈也考虑过,极限情况还是会出现线段重叠的
    dlsflh
        12
    dlsflh  
       2018-09-19 11:54:07 +08:00
    @3img #10 中心点?火影看过没?搓一个螺旋丸不就好了。阿基米德螺旋线这种的?
    LuffyGu
        13
    LuffyGu  
       2018-09-19 11:57:48 +08:00
    找出最左,或最右,或最上,或最下的点。然后向这个点的反方向,把点一个一个的连接起来,一条折线。
    SCaffrey
        14
    SCaffrey  
       2018-09-19 11:59:24 +08:00 via Android   ❤️ 1
    极角排序?
    Yafeng043
        15
    Yafeng043  
       2018-09-19 13:02:19 +08:00 via iPhone
    以中心点为原点左右划分为竖向两块,分别按照楼上说的心电图的走法即可。应该解决问题了吧
    limitsy
        16
    limitsy  
       2018-09-19 13:25:24 +08:00
    用凸包做?绕圈。
    iloahz
        17
    iloahz  
       2018-09-19 14:08:57 +08:00 via Android
    给定起点的话感觉极角排序比较靠谱,只是注意选取起始角度的问题,当所有点在一个半平面内时需要从边上开始
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2717 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 30ms · UTC 15:30 · PVG 23:30 · LAX 08:30 · JFK 11:30
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.