Running Depth First Search to find point cluster

Anonymous · ‎03-14-2021

Hello, I want to find point cluster from point list by DFS (Depth First Search).

My algorithm is below...
1. Get selection set by layer name.

2. Get the point list like this from selection set.

((77000.4 135874.0) (76979.0 135874.0) (77000.4 136238.0) (76979.0 136238.0) (147524.0 108880.0) (147502.0 108880.0) (147524.0 109243.0) (147502.0 109243.0) (152374.0 105518.0) (152353.0 105518.0) (152374.0 105882.0) (152353.0 105882.0))

3. Setting visited (= check array) false for all points.

4. Iterate points, and run depth first search from the point unless it is not visited.

I want to 1 point cluster by running 1 depth first search.

But, I got this error message,

Command: MYGETPOINT
Hard error occurred ***
internal stack limit reached (simulated)

So I attached my code..

(defun setNth (l n w)
  (cond
    ( (null l) '())
    ( (eq n 0) (cons w (cdr l)))
    ( (cons (car l) (setNth (cdr l) (- n 1) w)))))

(defun dfs(idx)
  (setq cur (nth idx vertex))
  (setq curx (nth 0 cur))
  (setq cury (nth 1 cur))
      
  (setq i 0)
  (while (< i (length vertex))
    (if (= (nth i visited) 0)
      (progn
        (setq nxt (nth i vertex))
	(setq nxtx (nth 0 nxt))
	(setq nxty (nth 1 nxt))
	(setq dist (+ (* (- curx nxtx) (- curx nxtx)) (* (- cury nxty) (- cury nxty))))
	(if (< dist 1000000) ; continue dfs if nxt point is sufficiently close to cur point
	  (progn
	    (setq cluster (append cluster (list i)))
	    (setNth visited i 1)
	    (dfs i)
	  )
        )
      )
    )
    (setq i (1+ i))
  )
)

(defun c:MyGetPoint()

  ; Selection Set
  (setq filter (list (cons 8 "polyline") (cons 0 "LWPOLYLINE")))
  (setq ss (ssget "_X" filter))

  ; Make vertex list
  (setq vertex nil)
  (setq i 0)
  (repeat (sslength ss)
    (setq e (ssname ss i)
	  eType (cdr (assoc 0 (entget e)))
	  ePoint (cdr (assoc 10 (entget e)))
	  i (1+ i)
    )
    (setq vertex (append vertex (list (list (nth 0 ePoint) (nth 1 ePoint)))))
  )

  (print vertex)
  ;(princ (length vertex))

  ; visited -> check array
  (setq i 0)
  (setq visited nil)
  (while (< i (length vertex))
    (setq visited (append visited '(0)))
    (setq i (1+ i))
  )

  ;(print visited)
  ;(print (length visited))

  (setq i 0)
  (while (< i (length vertex))
    (if (= (nth i visited) 0)
      (progn
	(setq cluster nil)
        (setNth visited i 1)
        (dfs i)
	; TODO: cluster should be the set of indices of points which are very close 
	(print cluster)
      )
    )
    (setq i (1+ i))
  )

)

Could you find the cause of this error?

Thanks in advance!

pbejse · ‎03-14-2021

@Anonymous wrote:

But, I got this error message,

Command: MYGETPOINT
Hard error occurred ***
internal stack limit reached (simulated)

Could you find the cause of this error?

The dfs sub is at at fault, its doing the Energizer bunny thing.. keeps going and going... what would be the correct value based on the point list you posted. that way we can analyze your code.

Anonymous · ‎03-15-2021

Thanks for quick reply. I expect this behavior..

I want to set list "cluster" after 1st call (dfs i) as below,

((77000.4 135874.0) (76979.0 135874.0) (77000.4 136238.0) (76979.0 136238.0))

and after 2nd dfs call "cluster" should be like this,
((147524.0 108880.0) (147502.0 108880.0) (147524.0 109243.0) (147502.0 109243.0))

3rd call
((152374.0 105518.0) (152353.0 105518.0) (152374.0 105882.0) (152353.0 105882.0))

Then no more dfs call since every points is visited.

Anonymous · ‎03-15-2021

Sorry, I should have replied to your answer but I replied to myself...
-----------------------------------------------------------------------------------------------

Thanks for quick reply. I expect this behavior..

I want to set list "cluster" after 1st call (dfs i) as below,

((77000.4 135874.0) (76979.0 135874.0) (77000.4 136238.0) (76979.0 136238.0))

and after 2nd dfs call "cluster" should be like this,
((147524.0 108880.0) (147502.0 108880.0) (147524.0 109243.0) (147502.0 109243.0))

3rd call
((152374.0 105518.0) (152353.0 105518.0) (152374.0 105882.0) (152353.0 105882.0))

Then no more dfs call since every points is visited.

pbejse · ‎03-15-2021

@Anonymous wrote:

Sorry, I should have replied to your answer but I replied to myself...

You dont really need to post again, everyone can see your reply

@Anonymous wrote:

I want to set list "cluster" after 1st call (dfs i) as below,

((77000.4 135874.0) (76979.0 135874.0) (77000.4 136238.0) (76979.0 136238.0))

....

Do you mean "group" by cluster, that is all im seeing. Then what is the criteria for the number of items on a cluster?

Now we have this as vertex variable

(setq vertex '((77000.4 135874.0) (76979.0 135874.0) (77000.4 136238.0) (76979.0 136238.0)
	       (147524.0 108880.0) (147502.0 108880.0) (147524.0 109243.0) (147502.0 109243.0)
	       (152374.0 105518.0) (152353.0 105518.0) (152374.0 105882.0) (152353.0 105882.0)
	      )
)

and visited as

(0 0 0 0 0 0 0 0 0 0 0 0)

and then

(setNth visited i 1)
(1 0 0 0 0 0 0 0 0 0 0 0)

; TODO: cluster should be the set of indices of points which are very close

Then 'm lost after that. maybe another example can gives us more insight on what you want to do.

pbejse · ‎03-15-2021

@Anonymous wrote:

....

I want to set list "cluster" after 1st call (dfs i) as below,

....

Then no more dfs call since every points is visited.

Apolgies @Anonymous I did not know that Depth First Search is an actual thing hence my ignorant response. It looks intresting though. Let me see if I can find time to explore this.

pbejse · ‎03-15-2021

Here's what i change on your code:

The RED color is the main thing

(defun dfs (idx v / cur curx cury n nxt nxtx nxty dist)
  (setq cur (nth idx v))
  (setq curx (nth 0 cur))
  (setq cury (nth 1 cur))

  (setq n 0)
  (while (< n (length v))
    (if	(= (nth n visited) 0)
      (progn
	(setq nxt (nth n v))
	(setq nxtx (nth 0 nxt))
	(setq nxty (nth 1 nxt))
	(setq dist (+ (* (- curx nxtx) (- curx nxtx))
		      (* (- cury nxty) (- cury nxty))
		   )
	)
	(if (< dist 1000000)		; continue dfs if nxt point is sufficiently close to cur point
	  (progn
	    (setq cluster (append  cluster  (list (nth n v))))
	    (setq visited (setNth visited n 1))
	    (dfs n v)
	  )
	)
      )
    )
    (setq n (1+ n))
  )  
  cluster
)

(defun c:MyGetPoint ( / filter ss vertex i e eType ePoint visited)
; Selection Set
  (setq filter (list  (cons 8 "polyline")  (cons 0 "LWPOLYLINE")))
  (setq ss (ssget "_X" filter))
; Make vertex list
  (setq vertex nil)
  (setq i 0)
  (repeat (sslength ss)
    (setq e	 (ssname ss i)
	  eType	 (cdr (assoc 0 (entget e)))
	  ePoint (cdr (assoc 10 (entget e)))
	  i	 (1+ i)
    )
    (setq vertex
	   (append vertex (list (list (nth 0 ePoint) (nth 1 ePoint))))
    )
  )
;;(print vertex)
;(princ (length vertex))

; visited -> check array
  (setq i 0)
  (setq visited nil)
  (while (< i (length vertex))
    (setq visited (append visited '(0)))
    (setq i (1+ i))
  )
;(print visited)
;(print (length visited))
  
  (setq i 0)
  (while (< i (length vertex))
    (if	(= (nth i visited) 0)
      (progn
	(setq cluster nil)
	(setNth visited i 1)
	(print (dfs i vertex))
; TODO: cluster should be the set of indices of points which are very close
	;; (print cluster)
      )
    )
    (setq i (1+ i))
  )
  (princ)
)

((152374.0 105518.0) (152353.0 105518.0) (152374.0 105882.0) (152353.0 105882.0))
((147502.0 108880.0) (147524.0 108880.0) (147502.0 109243.0) (147524.0 109243.0))
((77000.4 135874.0) (76979.0 135874.0) (77000.4 136238.0) (76979.0 136238.0))

HTH

Anonymous · ‎03-19-2021

Thank you so much! Your code works very well.

Ah, was the main problem this line?

(setq visited (setNth visited n 1))

It was

(setNth visited i 1)

in my code. I thought n-th element of "visited" was set, but it wasn't maybe.

Anyway visited list is a kind of global variable, right?

I'm very confused about LISP's variable scope..

Community

Running Depth First Search to find point cluster

Running Depth First Search to find point cluster

Running Depth First Search to find point cluster