Thanks for Daniel and pkohut, your c code all very fast.
But I am not familiar with c, so I only have to do this in Lisp.
Now I use xy grid to sort the point. It seems that now it is quick a little than Evgeiny's. But my code is toooooooo long. Sorry, I need to improve my coding skill. But at least, I think this algorithm is effective. The next step, I want to study pkohut's kd-tree algorithm, it seems so amazing.
(vl-load-com)
;;entmake line
(defun entmakeline (pt1 pt2 layer)
(entmake (list (cons 0 "LINE") ;***
(cons 6 "BYLAYER") (cons 8 layer) (cons 10 pt1) ;***
(cons 11 pt2) ;***
(cons 39 0.0) (cons 62 256) (cons 210 (list 0.0 0.0 1.0))
)
)
)
;;The idea of gile
(defun getpointscor (/ ent n plst ss)
(if (setq n -1
ss (ssget '((0 . "POINT")))
)
(while (setq pubtime (car (_VL-TIMES)) ent (ssname ss (setq n (1+ n))))
(setq plst (cons (cdr (assoc 10 (entget ent))) plst))
)
)
)
;;the bounding box of the points set
(defun getboundingboxpointset (a)
(list (apply 'min (mapcar '(lambda (x) (car x)) a))
(apply 'max (mapcar '(lambda (x) (car x)) a))
(apply 'min (mapcar '(lambda (x) (cadr x)) a))
(apply 'max (mapcar '(lambda (x) (cadr x)) a))
)
)
;;;divide the points set according to a certain x or y or z space
(defun dividexyz (plst dis vmin vmax stringxyz / a b div end index lst1 res start)
(setq start vmin
div (+ (fix (/ (- vmax vmin) dis)) 1)
res nil
)
(repeat div
; (grdraw (list start 0 0) (list start 10000 0) 8)
(setq end (+ start dis)
index T
lst1 nil
)
(while (and plst index)
(if (< (setq a (car plst)
b (cond ((= stringxyz "x") (car a))
((= stringxyz "y") (cadr a))
((= stringxyz "z") (caddr a))
(T nil)
)
)
end
)
(setq lst1 (append
lst1
(list a)
)
plst (cdr plst)
)
(setq index nil)
)
)
(setq res (append
res
(list lst1)
)
)
(setq start (+ start dis))
)
res
)
;;;draw short line in each x region
;;;The idea of Leemac and gile
(defun drawshortline (plst limdis / a b tmp)
(if plst
(while (setq a (car plst))
(setq plst (cdr plst)
tmp plst
)
(while (setq b (car tmp))
(setq tmp (cdr tmp))
(if (< (distance a b) limdis)
(entmakeline a b "temp")
)
)
)
)
)
;;;draw short line in each two Neighbor x region
(defun drawshortline12 (plst1 plst2 limdis / a b x)
(if (and
plst1
plst2
)
(while (setq a (car plst1))
(foreach x plst2
(if (< (distance a x) limdis)
(entmakeline a x "temp")
)
)
(setq plst1 (cdr plst1))
)
)
)
;;draw line between two pointsets and manner
(defun dl12(a b limdis stringabc / ab lst1 lst2)
(cond ((= stringabc "90") (setq lst1 (reverse (cdr (reverse a))) lst2 (cdr b)))
((= stringabc "0") (setq lst1 a lst2 b))
((= stringabc "-45") (setq lst1 (cdr a) lst2 (reverse (cdr (reverse b)))))
((= stringabc "45") (setq lst1 (reverse (cdr (reverse a))) lst2 (cdr b)))
(T nil)
)
(setq ab (mapcar '(lambda (x y) (list x y)) lst1 lst2))
(foreach x ab
(if x
(drawshortline12 (car x) (cadr x) limdis)
)
)
)
;;draw line between the own pointsets
(defun dl1(pl1 limdis)
(foreach x pl1
(drawshortline x limdis)
)
)
;;Connect short line between each two points
;;by qjchen@gmail.com
;; Thanks to ronjonp, Lee Mac, and Gile and alanjt and Evgeniy
;;Version 1.0
(defun c:gap ( / a b bbox limdis plst plst1 plst2) ;(mylayer "temp")
;(starttimer)
(setq limdis 70 ) ;;The idea of gile
(setq plst (getpointscor)) ;;The idea of ronjonp
;;getting the boundingbox of all the points set
(setq bbox (getboundingboxpointset plst) )
;;;sort the point according to the x coordinate
(setq plst (vl-sort plst (function (lambda (x1 x2)
(< (car x1) (car x2))
)
)
)
) ;;Divde points list to several region according to the x value=>plst1
;;such like ((lst 0, contain x=0~70),(lst 1, contain x=70~140)........)
(setq plst1 (dividexyz plst limdis (nth 0 bbox) (nth 1 bbox) "x" )
plst2 nil
)
;;Divde each plst1 to several region according to the y value=>plst2
(foreach x plst1
(if x
(setq x (vl-sort x (function (lambda (x1 x2)
(< (cadr x1) (cadr x2))
)
)
)
plst2 (append
plst2
(list (dividexyz x limdis (nth 2 bbox) (nth 3 bbox) "y"))
)
)
(setq plst2 (append
plst2
(list nil)
)
)
)
)
;;Draw shortline in each x region,such like (0, contain x=0~70))
(while (setq a (car plst2)
b (cadr plst2)
plst2 (cdr plst2)
)
(if a
(progn
(dl1 a limdis)
(dl12 a a limdis "90")
(if b
(progn
(dl12 a b limdis "0")
(dl12 a b limdis "-45")
(dl12 a b limdis "45")
)
(progn
)
)
) ;else continue
)
)
(dl1 a limdis)
(dl12 a a limdis "90")
(princ (strcat "\n " (rtos (/ (- (car (_VL-TIMES)) pubtime) 1000.) 2 4) "sec."))
;(endtimer)
)
Now In my PC, it is about 0.79s for 10,000 points, and 160s for 500,000 points.
Evgeniy's code is about 1.6s for 10,000 points, and 288s for 500,000 points.
Sure master Evgeniy can easily improve the code and quick quick than me, but I am just try to study this funny algorithm.
The algorithm is as following picture.