here is a way to sort list of points
;;;=========================================================================
;;; Sort a list of 3d elements
;;;=========================================================================
;;; From: "Tony Tanzillo" <tony.tanzillo at caddzone dot com>
;;; Newsgroups: autodesk.autocad.customization
;;; Subject: Re: How can I sort a list of 3d points?
;;; Date: Wed, 19 Mar 2003 10:37:20 -0500
;;;
;;; You can use vl-sort, with a comparison function that
;;; weights the ordinates in whatever way you want.
;;;
;;; Here's an example that gives the greatest weight
;;; to the X ordinate, and the least weight to the Z
;;; ordinate:
;;; sort on three keys (x, y, and z)
;|
(defun-q compare-points (a b / fuzz)
(setq fuzz 1.0e-6) ;; comparison precision
(if (equal (car a) (car b) fuzz)
(if (equal (cadr a) (cadr b) fuzz)
(> (caddr a) (caddr b))
(> (cadr a) (cadr b))
)
(> (car a) (car b))
)
)
;;; example (vl-sort <list-of-points> 'compare-points)
;;; If you search this newsgroup, you'll find a much
;;; more powerful sorting function along with a good
;;; discussion on why (vl-sort) can be very dangerous.
;;; For that reason, I suggest you replace the built-in
;;; vl-sort with this:
(defun-q vl-sort (lst func)
(mapcar
'(lambda (x) (nth x lst))
(vl-sort-i lst func)
)
)
|;
;;; This will ensure that (vl-sort) does not remove
;;; elements that it sees as equal.
;;;=========================================================================
;;; LSORT.LSP Copyright 1992-98 Tony Tanzillo all rights reserved
;;;
;;; ----------------------------------------------------------------
;;; Merging complex list sort
;;;
;;; LSORT.LSP implements a modified version of the classic
;;; merge sort algorithm that sorts arbitrarily-complex lists
;;; using a caller-defined relational predicate function.
;;;
;;; (lsort <list> <OnCompare>)
;;;
;;; <OnCompare> is a function that takes two arguments,
;;; and returns non-nil if the first argument is greater
;;; than the second, or nil otherwise. The arguments are
;;; the elements of the list to be sorted. This argument
;;; must be quoted.
;;;
;;; The default sort order is descending. To change the
;;; sort order to ascending, the <OnCompare> function can
;;; return the logical complement (not) of it's result.
;;;
;;; Examples:
;;;
;;; 1. Sort a list of coordinates on the Y-component:
;;;
;;; Assume unsorted data is in 'UNSORTED
;;;
;;; (setq sorted
;;; (lsort unsorted
;;; '(lambda (a b)
;;; (> (cadr a) (cadr b))
;;; )
;;; )
;;; )
;;;
;;;
;;; 2. Sort a list of entity names by layer:
;;;
;;; (setq sorted
;;; (lsort unsorted
;;; '(lambda (e1 e2)
;;; (> (cdr (assoc 8 (entget e1)))
;;; (cdr (assoc 8 (entget e2)))
;;; )
;;; )
;;; )
;;; )
;;;
;;; 3. Sort a list of coordinates on multiple
;;; keys (first by the X ordinate, and then
;;; by the Y ordinate):
;;;
;;; (setq epsilon 1e-6)
;;;
;;; (defun-q compare-points (p1 p2)
;;; (cond
;;; ( (equal (car p1) (car p2) epsilon) ; if x are equal,
;;; (> (cadr p1) (cadr p2))) ; then compare y,
;;; (t (> (car p1) (car p2))) ; else compare x
;;; )
;;; )
;;;
;;; (setq sorted (lsort unsorted 'compare-points))
;;;=========================================================================
(defun-q lsort (input OnCompare / fun)
(setq fun (cond (OnCompare) (t '>)))
(lsort-aux input)
)
(defun-q lsort-aux (input)
(if (cdr input)
( (lambda (tlist)
(lsort-merge
(lsort-aux (car tlist))
(lsort-aux (cadr tlist))
)
)
(lsort-split input)
)
input
)
)
(defun-q lsort-split (right / left)
(repeat (/ (length right) 2)
(setq
left (cons (car right) left)
right (cdr right)
)
)
(list left right)
)
(defun-q lsort-merge (left right / out)
(while (and left right)
(if (apply fun (list (car left) (car right)))
(setq
out (cons (car left) out)
left (cdr left)
)
(setq
out (cons (car right) out)
right (cdr right)
)
)
)
(append (reverse out) left right)
)
