Author Topic: Sorting a triangle list on z value  (Read 1741 times)

0 Members and 1 Guest are viewing this topic.

ymg

  • Guest
Sorting a triangle list on z value
« on: June 26, 2011, 11:13:32 AM »
How would you go about sorting a list of triangle on the max z value of individual triangles.

Currently the list is formatted like so.

Code: [Select]
(
 ((2455.6 695.636 10.0) (2241.51 1048.67 15.1) (2304.6 871.301 12.0))
 ((2069.42 69.732 22.2) (1888.23 124.665 18.8) (1818.56 140.657 18.3))
 ((2462.35 249.15 18.3) (2173.55 135.927 20.7) (2069.42 69.732 22.2))
 ((2591.77 477.032 9.5) (2455.6 695.636 10.0) (2441.41 517.957 11.5))
 ((2591.77 477.032 9.5) (2441.41 517.957 11.5) (2585.43 387.857 9.8))
 ((2585.43 387.857 9.8) (2441.41 517.957 11.5) (2462.35 249.15 18.3))
 ((2455.6 695.636 10.0) (2298.4 460.399 12.0) (2441.41 517.957 11.5))
 ((2462.35 249.15 18.3) (2298.4 460.399 12.0) (2173.55 135.927 20.7))
 ((2462.35 249.15 18.3) (2441.41 517.957 11.5) (2298.4 460.399 12.0))
 ((2455.6 695.636 10.0) (2304.6 871.301 12.0) (2298.4 460.399 12.0))
 )

Each line in above code is a triangle.  What I want after sorting is each triangle  in increasing order of Z.
Z for an individual triangle is max of the Z of the 3 vertexes.

Have to admit I am Lamda and mapcar challenged   :?

ymg

Lee Mac

  • Seagull
  • Posts: 12906
  • London, England
Re: Sorting a triangle list on z value
« Reply #1 on: June 26, 2011, 11:33:49 AM »
Here are two ways, the second is far more efficient than the first because there are far fewer operations within the sort predicate function.

Code: [Select]
(defun SortByZ ( lst )
  (vl-sort lst
    (function
      (lambda ( a b )
        (< (apply 'max (mapcar 'caddr a)) (apply 'max (mapcar 'caddr b)))
      )
    )
  )
)

Code: [Select]
(defun SortByZ2 ( lst )
  (mapcar
    (function
      (lambda ( n ) (nth n lst))
    )
    (vl-sort-i (mapcar '(lambda ( x ) (apply 'max (mapcar 'caddr x))) lst) '<)
  )
)

Code: [Select]
_$ (Benchmark '((SortbyZ lst) (SortbyZ2 lst)))
Benchmarking ................Elapsed milliseconds / relative speed for 8192 iteration(s):

    (SORTBYZ2 LST).....1295 / 2.69 <fastest>
    (SORTBYZ LST)......3479 / 1 <slowest>

For a list with 100 triangles:

Code: [Select]
(defun test ( / lst sub1 sub2 )
  (repeat 100
    (repeat 3
      (repeat 3
        (setq sub1 (cons (_rand) sub1))
      )
      (setq sub2 (cons sub1 sub2) sub1 nil)
    )
    (setq lst (cons sub2 lst) sub2 nil)
  )
  (Benchmark '((SortbyZ lst) (SortbyZ2 lst)))
)

(defun _rand ( / mod )
  (/ (setq mod 4294967296.0 seed (rem (1+ (* 1664525.0 (cond (seed) ((getvar 'DATE))))) mod)) mod)
)

Code: [Select]
_$ (test)
Benchmarking .............Elapsed milliseconds / relative speed for 1024 iteration(s):

    (SORTBYZ2 LST).....1357 / 7.33 <fastest>
    (SORTBYZ LST)......9953 / 1 <slowest>

Note that since your example list contains duplicate maximum Z-values, the above functions may return different results.

For more information about how to use mapcar/lambda, perhaps have a read of this short tutorial.

More information about the Sorting process can be found here.

« Last Edit: June 26, 2011, 11:44:52 AM by Lee Mac »

ymg

  • Guest
Re: Sorting a triangle list on z value
« Reply #2 on: June 26, 2011, 11:42:04 AM »
Quote
Here are two ways, the second is far more efficient than the first because there are far fewer operations within the sort predicate function.

Thanks a lot Lee!

With that kind of fast answer I'm bound to become lazy

ymg