点集中最近两点-->>(距离 (p1 p2))

韩飞翔 · 发表于 2025-7-24 10:57:53

本帖最后由韩飞翔于 2025-7-27 16:31 编辑

10000个点0.6秒完成，有需要的下载
;; =============================================
;; |       点集中距离最近的两点          |
;; =============================================
;;说明:点集中距离最近两点-->>得到表 (距离 (p1 p2))
;;参数:ptn:点集
;;参数:mode: t 点集来自点选择集  nil其他图元处理得到的点集
;;返回:  (fx-ptn-minNear2pt ptn t)

gzxl · 发表于 2025-7-26 06:18:41

guosheyang 发表于 2025-7-25 09:01
哦记错了是递归哥曾经写过

高大侠写过。
http://bbs.mjtd.com/forum.php?mo ... E%D0%A1%BE%E0%C0%EB

韩飞翔 · 发表于 2025-7-25 09:33:35

gzxl 发表于 2025-7-24 21:18
综合经验来说（个人观点），lisp 与 arx 以一万个点求解最近点对的话，在同一算法基础上两者速度综合约10~2 ...

;测试代码；直接复制到命令行；同时加载那个vlx文件；看看大概差多少
(defun c:tt(/ fx-ssget-10pt-ptn fx-time-st l ptn)
(defun fx-ssget-10pt-ptn (ss / i l a b c)
(setq i 0)
(if ss
(repeat (sslength ss)
(setq a (ssname ss i))
(setq i (1+ i))
(setq b (entget a))
(setq c (cdr (assoc 10 b)))
(setq l (cons c l))
)
)
(reverse l)
)
(setq ptn (fx-ssget-10pt-ptn (ssget '((0 . "point")))))
(setq fx-time-st (car (_vl-times)))
(setq l (fx-ptn-minNear2pt ptn t))
(if fx-time-st (print (strcat "花费" (rtos (* 0.001 (- (car (_vl-times)) fx-time-st)) 2 4) "秒")))
(vl-princ-to-string l)
)

aws · 发表于 2025-7-24 13:51:48

以前收集的，粗暴的解决方式，感觉执行效率或许有点差强人意

;---点集的最远点和最近点（提前删除重复点）
(defun xpts-lensort (plst / pt d maxd mind maxl minl)
(setq minl(list(car plst)(cadr plst)))
(setq mind(apply 'distance minl))
(setq maxd 0)
(while
(setq pt(car plst))
(setq plst(cdr plst))
(foreach n plst
(setq d(distance n pt))
(cond
((< maxd d)(setq maxd d maxl(list n pt)))
((> mind d)(setq mind d minl(list n pt)))
)
)
)
(list maxl minl)
)

guosheyang · 发表于 2025-7-24 12:15:22

好像高飞鸟版主也写过这个

bskidtf · 发表于 2025-7-24 13:57:03

本帖最后由 bskidtf 于 2025-7-24 14:08 编辑

我可以说下我用C++写过的一个思路
点集根据先Y后X排序，排序时候就把重合点检测出来。有重合点那么就自然是距离最近的点了。
然后用四叉树，把点放进树里，第一个点和第二个点暂时当做是结果距离最近的两个点，记录距离，
然后遍历点集，每个点在这个记录的最近距离范围内搜索点，看有没有比那个距离更小的点，记录那对点计算过距离，减少计算量。有点话就更新那个记录的最短距离和对应的点索引，这样遍历完就拿到了结果。我这十多年前的破电脑，10W点是秒出。20毫秒吧大概。

czb203 · 发表于 2025-7-24 14:46:29

感谢韩天师的分享

bskidtf · 发表于 2025-7-24 14:51:04

bskidtf 发表于 2025-7-24 13:57
我可以说下我用C++写过的一个思路
点集根据先Y后X排序，排序时候就把重合点检测出来。有重合点那么就自然 ...

这里关键点是四叉树，lisp不好解决这个问题，所以慢，并不是思路的问题。你可以说说你的思路，用C++写出来试试

韩飞翔 · 发表于 2025-7-24 15:13:38

bskidtf 发表于 2025-7-24 14:51
这里关键点是四叉树，lisp不好解决这个问题，所以慢，并不是思路的问题。你可以说说你的思路，用C++写出 ...

1、求得点集数量为n，按照每堆100个点分堆；即n/100; 2、得到点集的9点坐标的p1和p9点；以p1和p9的距离除以分堆数量；得到一个距离dis；根据这个距离将点集划分成小网格；每个网格的p1和p9再外扩这个dis的1/10；相当于让每个相邻网格都进行了部分重叠；然后每个网格内；形成点集；再根据你上面的算法得到最小距离的两点；然后最后取小网格的点集对比得到最小距离两点

bskidtf · 发表于 2025-7-24 16:10:42

分治法，这样的重复计算量也不小的。我感觉速度不会比我说的那样快

gzxl · 发表于 2025-7-24 16:18:38

本帖最后由 gzxl 于 2025-7-24 16:29 编辑

分治算法求解最近点对，速度也是可以的。

分治算法求解最近点对核心代码
http://bbs.mjtd.com/thread-191978-1-1.html

gzxl · 发表于 2025-7-24 21:18:34

综合经验来说（个人观点），lisp 与 arx 以一万个点求解最近点对的话，在同一算法基础上两者速度综合约10~20倍。lisp的速度 10000个点2秒那么应该不是最佳的算法。

账号		自动登录	找回密码
密码			注册

[函数] 点集中最近两点-->>(距离 (p1 p2))

本帖子中包含更多资源

评分

点评

点评

点评

点评

点评

本帖子中包含更多资源

点评

点评

浏览过的版块