点表连线求最优算法

kele99kele

已知点表，排列布置为下图：

目的为做所有点的连线，确保每个点与周围最近的点均保持连接（点表为空间点，z坐标
不同）希望实现如下图所示：

设计思路：每个点与点表所有成员测量距离，在距离≤设置值的时候，做两点连线，
所绘线段加入选择集,图完毕选择所绘制的线段查找重复单元并删除重复obj。

缺点：当点表排布不均匀时
1.设置距离过大会越过最近点向下一个点连线。
2.当设置距离过小时会漏掉部分必要连线
如下图：

求思路优化

newbuser

这个似乎很难的哦。你看，就连那么成熟的cass生成的三角网都不是那么规矩的。

kele99kele

newbuser 发表于 2015-8-20 19:16
这个似乎很难的哦。你看，就连那么成熟的cass生成的三角网都不是那么规矩的。

cass三角网生成的点位需要计算，那个是比较困难的，我只是想实现已经定好点位的连线，应该要简单好几个数量级的

kele99kele

没有人愿意出手，我先把我的笨办法贴上来吧，欢迎指正

2. (defun N::MakeLineFromPointList (lst maxdistance / ptn lsts)
   
3.   (setq lsts lst)
   
4.         (while lsts
   
5.                 (setq ptn (car lsts))
   
6.                 (foreach x lst
   
7.                         (if (and (> (distance ptn x) 0) (< (distance ptn x) maxdistance))
   
8.                                 (command "LINE" ptn x "")
   
9.                         )
   
10.                 )
    
11.                 (setq lsts (cdr lsts))
    
12.         )
    
13. )

(defun N::MakeLineFromPointList (lst maxdistance / ptn lsts)<br />   (setq lsts lst)<br />         (while lsts<br />                 (setq ptn (car lsts))<br />                 (foreach x lst<br />                         (if (and (> (distance ptn x) 0) (< (distance ptn x) maxdistance))<br />                                 (command "LINE" ptn x "")<br />                         )<br />                 )<br />                 (setq lsts (cdr lsts))<br />         )<br /> )

kele99kele

设定的maxdistance不同，生成的连线区别很大，而且随point的分布情况会有很多不同

第一种点：

这张图是理想连线





第二种点：

这张图是理想连线


怎么算出最优连线的设置距离呢，这个现在一点思路也没有

edata

你的算法有重复，应该是第一项和二项之后比较，二项和三项之后比较，以此循环。。。。
再提个思路，一个点只能和最近的最多4个点相连接，且连线不相交。

vectra

感觉maxdistance不会是个固定值，而是要动态调整的，在点密集的地方，这个值需要变小

fl202

说说我的思路：
1  先出所有点的点表b1   '(pt1 pt2 pt3 pt4 ...) 。
2  算出第一点与其它点的连线的点表b2  '( '(pt1 pt2) '(pt1 pt3)...)  。将该点从b1中删除,  '(pt2 pt3 pt4 ...)。

3 算出第2点与其它点的连线的点表b3   '( '(pt2 pt3) '(pt2 pt4)...)  .  将该点从b1中删除,(pt3 pt4 pt5 ...)。
4  b2 b3 对比，有交点的，选择距离短的加入到b4中。无交点的加入到b4中。将b4 =b2 再循环计算

步骤3  4依次进行到最后一个点为止。

根据b2 生成所有的线。

点的数量越多，计算花费的时间越长。 如果再加设定距离对比值，计算时间可以相对短点。

陨落

是做网架么，
这样的问题
用犀牛直接就搞定了

陨落

犀牛里面有很多插件，可以直接划分三维网格，结合其三维投影等强大的三维功能，是为做网架之必备神器