Author Topic: Sorting points clockwise  (Read 3878 times)

0 Members and 1 Guest are viewing this topic.

yarik

  • Newt
  • Posts: 32
Sorting points clockwise
« on: January 26, 2011, 04:36:13 PM »
Hi everybody

how can i sort a list of point clockwise??

ex ' ((367662.0 3.50951e+006 0.0)
(367746.0 3.5095e+006 0.0) (367763.0 3.50937e+006 0.0))(367794.0 3.50946e+006 0.0) (367798.0 3.50941e+006
0.0) 367624.0 3.50945e+006 0.0) (367779.0 3.50939e+006 0.0) )

obtain

'((367624.0 3.50945e+006 0.0) (367662.0 3.50951e+006 0.0)
(367746.0 3.5095e+006 0.0) (367794.0 3.50946e+006 0.0) (367798.0 3.50941e+006
0.0) (367779.0 3.50939e+006 0.0) (367763.0 3.50937e+006 0.0))

i appreciate any suggestion



any idea??

T.Willey

  • Needs a day job
  • Posts: 5251
Re: Sorting points clockwise
« Reply #1 on: January 26, 2011, 05:03:12 PM »
Code: [Select]
(setq ptList (vl-sort ptList (function (lambda ( a b ) (> (angle '(0. 0. 0.) a) (angle '(0. 0. 0.) b))))))
Tim

I don't want to ' end-up ', I want to ' become '. - Me

Please think about donating if this post helped you.

SOFITO_SOFT

  • Guest
Re: Sorting points clockwise
« Reply #2 on: January 26, 2011, 06:09:21 PM »
Hello:
Code: [Select]
( defun orden-senti-horar ( l /    ;;; <<< Sorting  clockwise
  centro salida n ang-min ang punto
)
( setq centro ( PointAverage l ) )
( while l
  ( setq ang-min 0.0 punto nil )
  ( foreach n l
     ( if ( > ( setq ang ( angle centro n ) ) ang-min )
       ( setq ang-min ang punto n )
     )
  )
  ( setq l (  vl-remove  punto  l ) )
  ( setq salida ( append salida ( list punto ) ) )
)
salida
)

(defun PointAverage ( l / )    ;<<<< centroide
  ( (lambda ( n ) (mapcar '/ (apply 'mapcar (cons '+ l)) (list n n n)))
    (float (length l))
  )
)

(defun clockwise-p (p1 p2 p3 / )   <<<< clockwise 2 points
    (< (sin (- (angle p1 p3) (angle p1 p2))) -1e-14)
)

- first calculated the centroid of the points
- then sweeps clockwise, looking for the best angle from the centroid.
the first of the returned items is not necessarily the same as in your post. The order does.

T. Willey solution I do not work well.
Regards...

Lee Mac

  • Seagull
  • Posts: 12906
  • London, England
Re: Sorting points clockwise
« Reply #3 on: January 26, 2011, 07:02:24 PM »
Sorting points clockwise requires a basepoint around which to sort - in Tim's code the origin is used, perhaps this offers an alternative:

Code: [Select]
(
  (lambda ( ref )
    (vl-sort ptlist
      (function
        (lambda ( a b ) (> (angle ref a) (angle ref b)))
      )
    )
  )
  (
    (lambda ( n )
      (mapcar '/ (apply 'mapcar (cons '+ ptlist)) (list n n n))
    )
    (float (length ptlist))
  )
)

Or, to be certain of the angle, perhaps:

Code: [Select]
(
  (lambda ( ref 2pi )
    (vl-sort ptlist
      (function
        (lambda ( a b ) (> (2pi (angle ref a)) (2pi (angle ref b))))
      )
    )
  )
  (
    (lambda ( n )
      (mapcar '/ (apply 'mapcar (cons '+ ptlist)) (list n n n))
    )
    (float (length ptlist))
  )
  (lambda ( a ) (rem (+ pi pi a) (+ pi pi)))
)
« Last Edit: January 26, 2011, 07:08:59 PM by Lee Mac »

yarik

  • Newt
  • Posts: 32
Re: Sorting points clockwise
« Reply #4 on: January 27, 2011, 11:49:43 AM »
Are great solutions, many thanks to everyone.
I'll be testing.


SOFITO I'm happy to find you here thanks for your help

SOFITO_SOFT

  • Guest
Re: Sorting points clockwise
« Reply #5 on: January 28, 2011, 08:13:42 PM »
Hello swamp people:
Here I find more help than I am.
Greetings from Madrid.