Remove duplicate points from a list

Anonymous · ‎09-09-2016

Chaps,

Can anybody speed up this code that removes duplicate coordinates from a list? Six points obviously isn't a problem but I'm working mainly with 100k points.

(setq TRI_Points '((0.0 0.0 0.0) (0.0 0.0 0.0) (10.0 0.0 0.0) (10.0 0.0 0.0) (0.0 0.0 0.1) (10.0 0.0 0.0)))
; stripped to :  '((0.0 0.0 0.0) (10.0 0.0 0.0) (0.0 0.0 0.1))
(setq TRI_StrippedPoints (list (car TRI_Points))
      TRI_Points (cdr TRI_Points)
      )
(repeat (length TRI_Points)
  (setq TRI_checkpoint (car TRI_Points)
	TRI_checkX (car TRI_checkpoint)
	TRI_checkY (cadr TRI_checkpoint)
	TRI_checkZ (caddr TRI_checkpoint)
	TRI_check T
	)
  (foreach TRI_temp TRI_StrippedPoints
    (setq TRI_tempX (car TRI_temp)
	  TRI_tempY (cadr TRI_temp)
	  TRI_tempZ (caddr TRI_temp)
	  )
    (if (and
	  (equal TRI_tempX TRI_checkX 0.0001)
	  (equal TRI_tempY TRI_checkY 0.0001)
	  (equal TRI_tempZ TRI_checkZ 0.0001)
	  )
      (setq TRI_check nil)
      )
    )
  (if TRI_check
    (setq TRI_StrippedPoints (append TRI_StrippedPoints (list TRI_checkpoint)))
    )
  (setq TRI_Points (cdr TRI_Points))
  )

patrick_35 · ‎09-09-2016

Hi

For example

(while TRI_Points
  (setq lst (cons (car TRI_Points) lst)
	TRI_Points (vl-remove (car TRI_Points) TRI_Points)
  )
)

(reverse lst)

An another from @_gile

(defun remove_doubles (lst)
  (if lst
    (cons (car lst) (remove_doubles (vl-remove (car lst) lst)))
  )
)

(remove_doubles '((0.0 0.0 0.0) (0.0 0.0 0.0) (10.0 0.0 0.0) (10.0 0.0 0.0) (0.0 0.0 0.1) (10.0 0.0 0.0)))

@+

Les Lisps de Patrick_35

Anonymous · ‎09-09-2016

(setq TRI_Points '((0.0 0.0 0.0) (0.0 0.0 0.0) (10.0 0.0 0.0) (10.0 0.0 0.0) (0.0 0.0 0.1) (10.0 0.0 0.0)))
(setq TRI_StrippedPoints nil)

(setq n 0)

(repeat (length TRI_Points)
	(setq item (nth n TRI_Points))
	(if (not (member item TRI_StrippedPoints))
		(progn
			(setq TRI_StrippedPoints (cons item TRI_StrippedPoints))
		);progn
	);if
	(setq n (1+ n))
);repeat

CADaSchtroumpf · ‎09-09-2016

Hi,

An another one, I don't know if is fastest!

(defun remove_multi ( l / nw_l )
  (mapcar
    '(lambda (x)
      (if (not (member x nw_l))
        (setq nw_l (cons x nw_l))
      )
    )
    l
  )
  nw_l
)

(remove_multi tri_points) -> ((0.0 0.0 0.1) (10.0 0.0 0.0) (0.0 0.0 0.0))

Anonymous · ‎09-09-2016

Thanks to all.

I had started along these lines but then headed off along the "compare" route which was clearly the wrong direction.

Kent1Cooper · ‎09-09-2016

Another way:

(foreach pt TRI_Points
  (if (not (member pt TRI_StrippedPoints))
    (setq TRI_StrippedPoints (cons pt TRI_StrippedPoints))
  )
  (reverse TRI_StrippedPoints); [only if necessary]
)

or, if you want them in the original order, a way without the (reverse) function:

(foreach pt TRI_Points
  (if (not (member pt TRI_StrippedPoints))
    (setq TRI_StrippedPoints (append TRI_StrippedPoints (list pt)))
  )
  TRI_StrippedPoints
)

But I do wonder: If any of these points could come from some kind of calculation, such as a (polar) function based off another point, or extracted from objects' entity data compared with something like Object-snap selections of the same points, and they wouldn't always be "clean" whole-number coordinates, then you might get points that are "duplicates" for your purposes but that AutoLisp would not consider the same [i.e. with differences 12 or 15 decimal places down]. If such things are possible, a comparison function using (equal) with a fuzz factor, such as in your code in Post 1, would be needed.

Kent Cooper, AIA

stevor · ‎09-10-2016

Cannot figure what direction you meant,

but a common method of removing doubles

is, as Kent mentioned, by the proximities.

L would be your list of 3 element lists, ie points;

and D as the nearness distance, maybe 1e-14,

or even 1e-4 for manual measurements.

; remove_doubles, SomeBuddy+
(defun L_RemEqu (L D / X)
(cond ((atom L) L)

(T (cons (car L) (L_RemEqu
(vl-remove-if '(lambda (x) (equal (car L) X D)) L) D)))) ) ;

For very big lists, a slightly different code may be needed.

S

martti.halminen · ‎09-12-2016

If we are having performance problems due to long lists, using APPEND is a bad idea: it has to copy all its arguments except the last. The CONS + REVERSE trick is much faster.

One undocumented trick for the comparisons: EQUAL works with a fuzz factor also for lists of numbers in addition to single numbers, so you can compare the whole point at once instead of each coordinate separately.

--

Anonymous · ‎09-13-2016

Ah yes: CONS v APPEND. One I normally follow. I had APPEND in the original test code to ease comparison between the two lists but neglected to change it to CONS for the final.

Thanks again to all.

stevor · ‎09-13-2016

Appears that Gile's is the fastest of a few tested:

Note that some only remove the 'duplicates'

to the Autocad exactness.

Points: 5000, Duplicated in place: 400
Remove_Multi: 3.6090E+00, Rem: 4600
Remove_Doubles: 2.9850E+00, Rem: 4600 [ Gile ]
PL_RemEqua: 1.1390E+01, Rem: 4600
L_RemEqu: 1.6203E+01, Rem: 4600

; Remove Equals, resolution D, explicit, SCG,etal
(defun PL_RemEqua ( L D / U Q F V ) ;
   (while (setq P (car L)) (setq L (cdr L) F NIL V U)
     (while (setq Q (car V)) ; terminate on find,
        (if (equal P Q D) (setq F T V nil) (setq V (cdr V))) )
           (if (not F) (setq U (cons P U)))
    ) (reverse U) ) ; def ~1/3 speed of CADaStroumph, Remove_Multi

S

patrick_35 · ‎09-13-2016

Hi

The result of benchmark

Elapsed milliseconds / relative speed for 131072 iteration(s):

(REMOVE_DOUBLES TRI_POINTS).....1887 / 1.23 <fastest>
(PATRICK_35 TRI_POINTS).........1904 / 1.22
(KENT1COOPER1 TRI_POINTS).......2168 / 1.07
(KENT1COOPER2 TRI_POINTS).......2215 / 1.05
(REMOVE_MULTI TRI_POINTS).......2278 / 1.02
(THAVASI1982 TRI_POINTS)........2325 / 1 <slowest>

An another

Elapsed milliseconds / relative speed for 131072 iteration(s):

(PATRICK_35 TRI_POINTS).........1903 / 1.24 <fastest>
(REMOVE_DOUBLES TRI_POINTS).....1935 / 1.22
(KENT1COOPER1 TRI_POINTS).......2246 / 1.05
(REMOVE_MULTI TRI_POINTS).......2262 / 1.04
(KENT1COOPER2 TRI_POINTS).......2293 / 1.03
(THAVASI1982 TRI_POINTS)........2355 / 1 <slowest>

(defun patrick_35(TRI_Points / lst)
  (while TRI_Points
    (setq lst (cons (car TRI_Points) lst)
	  TRI_Points (vl-remove (car TRI_Points) TRI_Points)
    )
  )
  (reverse lst)
)

(defun remove_doubles (lst)
  (if lst
    (cons (car lst) (remove_doubles (vl-remove (car lst) lst)))
  )
)

(defun thavasi1982(TRI_Points / n item TRI_StrippedPoints)
  (setq n 0)
  (repeat (length TRI_Points)
	  (setq item (nth n TRI_Points))
	  (if (not (member item TRI_StrippedPoints))
	    (progn
	      (setq TRI_StrippedPoints (cons item TRI_StrippedPoints))
	    );progn
	  );if
	  (setq n (1+ n))
  )
  TRI_StrippedPoints
)

(defun remove_multi ( l / nw_l )
  (mapcar
    '(lambda (x)
      (if (not (member x nw_l))
        (setq nw_l (cons x nw_l))
      )
    )
    l
  )
  nw_l
)

(defun Kent1Cooper1(TRI_Points / pt TRI_StrippedPoints)
  (foreach pt TRI_Points
    (if (not (member pt TRI_StrippedPoints))
      (setq TRI_StrippedPoints (cons pt TRI_StrippedPoints))
    )
    (reverse TRI_StrippedPoints); [only if necessary]
  )
)

(defun Kent1Cooper2(TRI_Points / pt TRI_StrippedPoints)
  (foreach pt TRI_Points
    (if (not (member pt TRI_StrippedPoints))
      (setq TRI_StrippedPoints (append TRI_StrippedPoints (list pt)))
    )
    TRI_StrippedPoints
  )
)

(setq TRI_Points '((0.0 0.0 0.0) (0.0 0.0 0.0) (10.0 0.0 0.0) (10.0 0.0 0.0) (0.0 0.0 0.1) (10.0 0.0 0.0))) 

(benchmark (list '(patrick_35 TRI_Points)
		 '(remove_doubles TRI_Points)
		 '(thavasi1982 TRI_Points)
		 '(remove_multi TRI_Points)
		 '(Kent1Cooper1 TRI_Points)
		 '(Kent1Cooper2 TRI_Points)
	   )
)

@+

Les Lisps de Patrick_35

martti.halminen · ‎09-14-2016

Another trick you can try on performance-critical code: VL-POSITION is clearly faster than MEMBER (or at least it was last time I measured it).

- in general code I don't recommend this (unless you are really interested in the position), as it hides the programmer intent.

- This is an implementation error in AutoLISP: as VL-POSITION does more work, it should actually be slower, so the MEMBER implementation is somehow bungled.

--

joselggalan · ‎09-14-2016

another method:

(defun RemoveEqualPts (LstPts fuzz / lstRet)
  (mapcar (function (lambda (pt / )
   (if (not (vl-some (function (lambda (x) (if (equal pt x fuzz) x nil))) lstRet))
    (setq lstRet (cons pt lstRet))
   );c.if
  )) LstPts)
  lstRet
 );c.defun

example:

(RemoveEqualPts
 '((0.0 0.0 0.0) (0.0 0.0 0.0) (10.0 0.0 0.0) (10.0 0.0 0.0) (0.0 0.0 0.1) (10.0 0.0 0.0)) 
 0.0001
)

--
linkedin - José-Luis García Galán
Hispacad -La Marmita del CAD

Community

Remove duplicate points from a list

Remove duplicate points from a list

Remove duplicate points from a list