设为首页收藏本站

晓东CAD家园-论坛

 找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 375|回复: 29

[研讨] 【已解决】(指定起始点的相对最短路径连线)自交的多段线变成顶点不变的不自交的...

[复制链接]

签到天数: 748 天

连续签到: 3 天

[LV.9]以坛为家II

已领礼包: 19个

财富等级: 恭喜发财

发表于 2018-2-8 21:24:56 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 Lisphk 于 2018-2-10 02:22 编辑


各位大师,如下图,自交的多段线,如何才能变成单独的一根,顶点不变的,不自交的多段线呢?

搜狗截图20180208212222.png
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!

签到天数: 1385 天

连续签到: 10 天

[LV.10]以坛为家III

已领礼包: 604个

财富等级: 财运亨通

发表于 2018-2-8 22:02:56 | 显示全部楼层
你这个有什么实际的使用吗?答案可能不止一种。其中一种是凸包,剩下的再凸包,由外往里绕。
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

签到天数: 748 天

连续签到: 3 天

[LV.9]以坛为家II

已领礼包: 19个

财富等级: 恭喜发财

 楼主| 发表于 2018-2-8 22:07:07 | 显示全部楼层

谢谢黄总回复,这个可以是解不走交叉路的遍历所有顶点。凸包好像不行吧,包来包去的还是有交叉,黄总给个代码?
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

签到天数: 748 天

连续签到: 3 天

[LV.9]以坛为家II

已领礼包: 19个

财富等级: 恭喜发财

 楼主| 发表于 2018-2-8 23:40:23 | 显示全部楼层
本帖最后由 Lisphk 于 2018-2-8 23:51 编辑

下面程序我想找到一些点的最短的路径,
下图是程序找到的从黄色点开始的,遍历所有顶点的最短的路径。但是有交叉,我想进一步的求出接近最短路径的不交叉的那条路径,所以用凸包那些是解决不了的。

搜狗截图20180208233521.gif
84个点,程序找到的最短路径

搜狗截图20180208234732.gif

337个点,程序找到的最短路径

搜狗截图20180208234854.gif

  1. (defun c:tt ()
  2.   (if (setq ss (ssget '((0 . "point"))))
  3.     (progn (setq pts nil
  4.                  i   -1
  5.            )
  6.            (while (setq e (ssname ss (setq i (1+ i))))
  7.              (setq pt  (cdr (assoc 10 (entget e)))
  8.                    pts (cons pt pts)
  9.              )
  10.            );;收集顶点

  11.            (setq pts  (cons '(0 0 0) pts)
  12.                  pt   (car pts)
  13.                  pts1 nil
  14.            )
  15.            (while (cdr pts)
  16.              (setq mindis 1e10)
  17.              (foreach n        pts
  18.                (setq dis (distance pt n))
  19.                (if (< dis mindis)
  20.                  (setq mindis dis
  21.                        ptmin n
  22.                  )
  23.                )
  24.              )
  25.              (setq pts1        (cons ptmin pts1)
  26.                    pts        (vl-remove ptmin pts)
  27.              )
  28.              (setq pt ptmin)
  29.            )
  30.            (setq pts1 (cdr (reverse (cons (last pts) pts1))))
  31.            (setq pts1 (mapcar '(lambda (x) (list 10 (car x) (cadr x))) pts1))
  32.            (entmake (append (list '(0 . "LWPOLYLINE")
  33.                                   '(100 . "AcDbEntity")
  34.                                   '(410 . "Model")
  35.                                   '(100 . "AcDbPolyline")
  36.                                   (cons 90 (length pts1))
  37.                             )
  38.                             pts1
  39.                     )
  40.            )
  41.     )
  42.   )
  43.   (princ)
  44. )



请点击此处下载

查看状态:需购买或无权限

您的用户组是:游客

文件名称:最短路径.rar 
下载次数:14  文件大小:32.43 KB 
下载权限: 不限 以上  [免费赚D豆]



论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

签到天数: 1327 天

连续签到: 11 天

[LV.10]以坛为家III

已领礼包: 1325个

财富等级: 财源广进

发表于 2018-2-9 10:40:52 | 显示全部楼层
外框bo行不&#128513;
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

签到天数: 1918 天

连续签到: 2 天

[LV.Master]伴坛终老I

已领礼包: 2996个

财富等级: 家财万贯

发表于 2018-2-9 11:30:16 | 显示全部楼层
chlh_jd前辈的帖子:点集最短回路(TSP问题)讨论

http://bbs.mjtd.com/thread-96730-1-1.html

评分

参与人数 1D豆 +5 收起 理由
Lisphk + 5 热心帮忙奖!

查看全部评分

论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

签到天数: 524 天

连续签到: 2 天

[LV.9]以坛为家II

已领礼包: 20个

财富等级: 恭喜发财

发表于 2018-2-9 13:38:04 | 显示全部楼层
搜狗截图20180209133214.png

找起点出来的第一个交叉点分析

1、8,9段 和15,16段交叉
2、图中可以看到,第二个线段的起点15和第一个线段的终点9 之间的 顺序互换,15变成9,14变成13...9变成15,然后 8 和 原来的15相连,原来的9(15)和原来的16相连,就变成不交叉的通路了。

所以,程序需要找出交叉段的起点索引和端点索引,然后交换, 下面每次遇到的都相同处理。
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

签到天数: 1985 天

连续签到: 83 天

[LV.Master]伴坛终老I

已领礼包: 5895个

财富等级: 富甲天下

发表于 2018-2-9 14:11:05 | 显示全部楼层
谢谢分享。
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复

使用道具 举报

签到天数: 109 天

连续签到: 1 天

[LV.6]常住居民II

已领礼包: 67个

财富等级: 招财进宝

发表于 2018-2-9 16:00:29 | 显示全部楼层
谢谢分享~!
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复

使用道具 举报

签到天数: 524 天

连续签到: 2 天

[LV.9]以坛为家II

已领礼包: 20个

财富等级: 恭喜发财

发表于 2018-2-9 19:48:51 | 显示全部楼层
本帖最后由 marting 于 2018-2-9 20:01 编辑

用上面分析的,写了代码,试试,你那个337个点的图变成这样了

之前:

搜狗截图20180209194039.png

之后:


搜狗截图20180209194020.png


XD::List:Nth-- 、XD::List:Nth++ 函数见:



  1. (defun c:tt ()
  2.   (defun _reverse_swap (pts from to)
  3.     (setq lst0 (XD::List:Nth-- pts from nil)
  4.           lst1 (XD::List:Nth++ pts from (1+ (- to from)))
  5.           lst2 (XD::List:Nth++ pts (1+ to) nil)
  6.     )
  7.     (append lst0 (reverse lst1) lst2)
  8.   )
  9.   (defun _entmake (pts)
  10.     (setq pts1 (mapcar '(lambda (x) (list 10 (car x) (cadr x))) pts))
  11.     (entmake (append (list '(0 . "LWPOLYLINE")
  12.                            '(100 . "AcDbEntity")
  13.                            '(410 . "Model")
  14.                            '(100 . "AcDbPolyline")
  15.                            (cons 90 (length pts1))
  16.                      )
  17.                      pts1
  18.              )
  19.     )
  20.     (entlast)
  21.   )
  22.   (if (setq e (car (entsel "\n拾取多段线<退出>:")))
  23.     (progn
  24.       (vla-startundomark
  25.         (setq doc (vla-get-activedocument (vlax-get-acad-object)))
  26.       )
  27.       (setq pts (vl-remove-if '(lambda (x) (/= (car x) 10)) (entget e))
  28.             pts (mapcar 'cdr pts)
  29.       )
  30.       (setq i   0
  31.             len (length pts)
  32.       )
  33.       (setq bHadCrossingSegments t
  34.             bself nil
  35.             bar 0
  36.       )
  37.       (while (< i (1- len))
  38.         (setq p1 (nth i pts))
  39.         (setq p2 (nth (1+ i) pts))
  40.         (setq j  0
  41.               tf t
  42.         )
  43.         (if (= bar 0)
  44.           (progn (princ "\n") (setq bar (1+ bar)))
  45.         )
  46.         (princ
  47.           (strcat "\r当前进度:" (rtos (* 100 (/ i len 1.0)) 2 0) "%")
  48.         )
  49.         (princ)
  50.         (while (and tf (< j (1- len)))
  51.           (setq p_1 (nth j pts))
  52.           (setq p_2 (nth (1+ j) pts))
  53.           (if (and (not (equal p1 p_1 1e-3))
  54.                    (not (equal p1 p_2 1e-3))
  55.                    (not (equal p2 p_1 1e-3))
  56.               )
  57.             (progn (if (setq ints (inters p1 p2 p_1 p_2))
  58.                      (progn (if (> i j)
  59.                               (setq from (1+ j)
  60.                                     to   i
  61.                               )
  62.                               (setq from (1+ i)
  63.                                     to   j
  64.                               )
  65.                             )
  66.                             (setq pts (_reverse_swap pts from to))
  67.                             (setq bHadCrossingSegments t
  68.                                   bself t
  69.                             )
  70.                      )
  71.                    )
  72.             )
  73.           )
  74.           (if bHadCrossingSegments
  75.             (setq tf nil)
  76.           )
  77.           (setq j (1+ j))
  78.         )
  79.         (setq i (1+ i))
  80.         (if bHadCrossingSegments
  81.           (setq i (min (max (1- i) 0) (max j 0))
  82.                 bHadCrossingSegments nil
  83.           )
  84.         )
  85.       )
  86.       (if bself
  87.         (progn (entdel e) (_entmake pts))
  88.       )
  89.       (princ "\r当前进度:100%")
  90.       (vla-endundomark doc)
  91.     )
  92.   )
  93.   (princ)
  94. )


论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

签到天数: 1873 天

连续签到: 136 天

[LV.Master]伴坛终老I

已领礼包: 5502个

财富等级: 富甲天下

发表于 2018-2-9 22:05:42 | 显示全部楼层
厉害了。     
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

签到天数: 748 天

连续签到: 3 天

[LV.9]以坛为家II

已领礼包: 19个

财富等级: 恭喜发财

 楼主| 发表于 2018-2-10 02:18:17 | 显示全部楼层

谢谢老师,把你的代码和我的合到一起,写了个可以指定起始点的 相对最短路径的代码,自己想的,也不知道能贴到哪类算法里面去,代码要比网上看到的短很多,实用上可以了。

最短路径.gif

游客,如果您要查看本帖隐藏内容请回复

论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

签到天数: 1985 天

连续签到: 83 天

[LV.Master]伴坛终老I

已领礼包: 5895个

财富等级: 富甲天下

发表于 2018-2-10 06:21:10 | 显示全部楼层
楼主很牛哦!
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

签到天数: 1124 天

连续签到: 16 天

[LV.10]以坛为家III

已领礼包: 1202个

财富等级: 财源广进

发表于 2018-2-10 06:54:45 | 显示全部楼层
看图片好像还有更短的路径
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

签到天数: 1124 天

连续签到: 16 天

[LV.10]以坛为家III

已领礼包: 1202个

财富等级: 财源广进

发表于 2018-2-10 07:46:20 | 显示全部楼层
本帖最后由 aimisiyou 于 2018-2-10 08:03 编辑

如果是在二次曲线上的一些点,那么很容易通过排序来获得最短路径。那么能否通过某种方式将其转换到二次曲线上呢?好像不对,变换不能保证长度同一变化。
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|申请友链|小黑屋|手机版|Archiver|辽公网安备|晓东CAD家园 ( 辽ICP备15016793号 )  

GMT+8, 2018-10-17 11:31 , Processed in 0.235816 second(s), 68 queries , Gzip On, WinCache On.

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表