Jump to content

[Help] Sort a list point by distance


ketxu

Recommended Posts

I have a list of point (x y z). Now i want to start draw a pline from a point in list (variable ), go to the next point so the distance from that point to next point is min, and repeat until the end

Since my poor E, I post a picture here.I received list point from user sort as list

(1 2 3 4 5 6 7 8) in the screen, and now i want re-sort it like (1 2 6 7 8 5 4 3)

I tried with some loop but it qite hard to newbie in lisp.Please help me, (and can be use recursive ?)

Untitled-1.jpg

Thanks all for reading

Link to comment
Share on other sites

This should get you started:

 

(defun _SortPtListByDist  (ptList)
 ;; Argument: Point list
 ;; Returns: Point list, sorted by distance from first point
 (vl-load-com)
 (mapcar
   '(lambda (x / ptList2)
      (setq ptList2 (append (cdr x) ptList2)))
   (vl-sort
     (mapcar
       '(lambda (x / pt ptlist2)
          (setq ptlist2
                 (append
                   (cons
                     (distance
                       (cond
                         (pt)
                         ((setq pt (car ptList))))
                       x)
                     x)
                   ptlist2)))
       ptList)
     '(lambda (x y)
        (< (car x) (car y))))))

 

Example:

 

(defun _GetPoints  (/ pt ptList)
 ;; Returns: Point list
 (while (/= nil (setq pt (getpoint)))
      (setq ptList (cons pt ptList)))
 (reverse ptList))

 

(_SortPtListByDist (_GetPoints))

 

Hope this helps!

Link to comment
Share on other sites

Mat, you could decrease your sort process with the following...

 

(defun sortMyNitchUp (pointlist)
 ((lambda (point) (cons point (vl-sort (cdr pointlist) '(lambda (a b) (< (distance point a) (distance point b))))))
   (car pointlist)
 )
))

Link to comment
Share on other sites

This would be fraught with problems:

 

[b][color=BLACK]([/color][/b]defun ptl2pol [b][color=FUCHSIA]([/color][/b]pl / fl mx md p1 p2 tp[b][color=FUCHSIA])[/color][/b]

[b][color=FUCHSIA]([/color][/b]defun remove [b][color=NAVY]([/color][/b]expr lst[b][color=NAVY])[/color][/b][color=#8b4513];;;TonyT or VNesterowski[/color]
   [b][color=NAVY]([/color][/b]apply 'append [b][color=MAROON]([/color][/b]subst nil [b][color=GREEN]([/color][/b]list expr[b][color=GREEN])[/color][/b] [b][color=GREEN]([/color][/b]mapcar 'list lst[b][color=GREEN])[/color][/b][b][color=MAROON])[/color][/b][b][color=NAVY])[/color][/b][b][color=FUCHSIA])[/color][/b]

 [b][color=FUCHSIA]([/color][/b]setq mx 0[b][color=FUCHSIA])[/color][/b]
 [b][color=FUCHSIA]([/color][/b]foreach p pl
   [b][color=NAVY]([/color][/b]foreach v pl
      [b][color=MAROON]([/color][/b]if [b][color=GREEN]([/color][/b]> [b][color=BLUE]([/color][/b]distance p v[b][color=BLUE])[/color][/b] mx[b][color=GREEN])[/color][/b]
          [b][color=GREEN]([/color][/b]setq mx [b][color=BLUE]([/color][/b]distance p v[b][color=BLUE])[/color][/b] p1 p p2 v[b][color=GREEN])[/color][/b][b][color=MAROON])[/color][/b][b][color=NAVY])[/color][/b][b][color=FUCHSIA])[/color][/b]
 [b][color=FUCHSIA]([/color][/b]setq fl [b][color=NAVY]([/color][/b]list p1[b][color=NAVY])[/color][/b][b][color=FUCHSIA])[/color][/b]
 [b][color=FUCHSIA]([/color][/b]setq pl [b][color=NAVY]([/color][/b]remove p1 pl[b][color=NAVY])[/color][/b][b][color=FUCHSIA])[/color][/b]

 [b][color=FUCHSIA]([/color][/b]repeat [b][color=NAVY]([/color][/b]length pl[b][color=NAVY])[/color][/b]
    [b][color=NAVY]([/color][/b]setq md [b][color=MAROON]([/color][/b]distance p1 p2[b][color=MAROON])[/color][/b][b][color=NAVY])[/color][/b]
    [b][color=NAVY]([/color][/b]foreach v pl
       [b][color=MAROON]([/color][/b]if [b][color=GREEN]([/color][/b]< [b][color=BLUE]([/color][/b]distance [b][color=RED]([/color][/b]car fl[b][color=RED])[/color][/b] v[b][color=BLUE])[/color][/b] md[b][color=GREEN])[/color][/b]
           [b][color=GREEN]([/color][/b]setq md [b][color=BLUE]([/color][/b]distance [b][color=RED]([/color][/b]car fl[b][color=RED])[/color][/b] v[b][color=BLUE])[/color][/b]
                 tp v[b][color=GREEN])[/color][/b][b][color=MAROON])[/color][/b][b][color=NAVY])[/color][/b]
    [b][color=NAVY]([/color][/b]setq fl [b][color=MAROON]([/color][/b]cons tp fl[b][color=MAROON])[/color][/b][b][color=NAVY])[/color][/b]
    [b][color=NAVY]([/color][/b]setq pl [b][color=MAROON]([/color][/b]remove tp pl[b][color=MAROON])[/color][/b][b][color=NAVY])[/color][/b][b][color=FUCHSIA])[/color][/b]

 [b][color=FUCHSIA]([/color][/b]command [color=#2f4f4f]"_.PLINE"[/color][b][color=FUCHSIA])[/color][/b]
 [b][color=FUCHSIA]([/color][/b]foreach v [b][color=NAVY]([/color][/b]reverse fl[b][color=NAVY])[/color][/b]
      [b][color=NAVY]([/color][/b]command v[b][color=NAVY])[/color][/b][b][color=FUCHSIA])[/color][/b]
 [b][color=FUCHSIA]([/color][/b]command [color=#2f4f4f]""[/color][b][color=FUCHSIA])[/color][/b]
 [b][color=FUCHSIA]([/color][/b]prin1[b][color=FUCHSIA])[/color][/b][b][color=BLACK])[/color][/b]

 

 

All points need to be on the same plane

 

What if 2 points are same distance from another point?

 

Just to name a couple.

 

This will be VERY slow with large lists.

 

HTH -David

Link to comment
Share on other sites

Not efficient, but is this not the desired result:

 

(defun sort ( lst / _sort )
 (defun _sort ( a b )
   (if a (cons a (_sort (car (setq b (vl-sort b '(lambda ( c d ) (< (distance a c) (distance a d)))))) (cdr b))))
 )
 (_sort (car lst) (cdr lst))
)

 

Or have I misunderstood?

Link to comment
Share on other sites

Wow, thank all so much. It's all of my expected.Great !!! It took me a day to think and coding, but some hours with you^^

Thanks all again :thumbsup:

 

@David, Lee : it's oke

 

@alanjt,RenderMan : i've tested with bellow list and feel it contains a mis

 

lst: ((33.2729 24.8458 0.0) (55.1007 36.1349 0.0) (63.4068 25.8106 0.0) (81.4679

39.2225 0.0) (82.7234 13.6531 0.0) (43.8004 7.67083 0.0) (44.8629 15.1969 0.0))

and make a pline:
(defun pllst (lst)(command "pline")(foreach x lst (command x))(command ""))

(pllst (sortMyNitchUp lst)) ;mis at (55.1007 36.1349 0.0) and (63.4068 25.8106 0.0)

(pllst (_SortPtListByDist lst)) ;mis same point at (55.1007 36.1349 0.0) and (63.4068 25.8106 0.0)

Edited by ketxu
After test
Link to comment
Share on other sites

Actually, David's algorithm gives better results since the best order also depends on the starting point.

 

The following list is a good example for differentiating between the algorithms:

 

(setq lst
'(
   ( 0.0 0.0 )
   ( 1.0 1.0 )
   (-1.0 1.1 )
   ( 2.0 2.0 )
   (-2.0 2.1 )
   ( 3.0 3.0 )
   (-3.0 3.1 )
   ( 4.0 4.0 )
   (-4.0 4.1 )
   ( 5.0 5.0 )
   (-5.0 5.1 )
 )
)

With Alan/Renderman's method:

 

test1.png

 

With my code above:

 

test2.png

 

With David's code above:

 

test3.png

 

This is the result of choosing a correct starting point to begin the algorithm. So I might improve my code with:

 

(defun sort ( lst / _sort a b d e l p )
 (defun _sort ( a b )
   (if a (cons a (_sort (car (setq b (vl-sort b '(lambda ( c d ) (< (distance a c) (distance a d)))))) (cdr b))))
 )
 (setq l (cdr lst)
       d (distance (setq p (car lst)) (car l))
 )
 (while (setq a (car l))
   (foreach b (setq l (cdr l))
     (if (< d (setq e (distance a b))) (setq p a d e))
   )
 )
 (_sort p (vl-remove p lst))
)

Which now results in:

 

test3.png

 

But although more concise, mine is probably far less efficient than David's due to its recursive nature.

Edited by Lee Mac
Link to comment
Share on other sites

Well, I guess that's what I get for not reading the thread and just looking at posted code. LoL

 

I actually drew points per the OP specified layout, and took into account specific point selection order (again, per the OP).

Link to comment
Share on other sites

@Lee : i tried to draw pline from first point in list (if point which user choice not is first, i will put it on in list ^^)

so the first method of you is what i need ^^

I also write a method to do samething :

(defun sort (lst start / lstRT 1st item lstDis) ;start : position to start
(setq 1st (nth start lst) lstRT (list 1st) lst (append lstRT (vl-remove 1st lst)))
(while (> (length lst) 1)
(setq lst (vl-remove (setq item (nth (1+ (vl-position (setq mindis (apply 'min (setq lstDis (cdr (mapcar '(lambda(x) (distance 1st x)) lst))))) lstDis)) lst)) lst))
(setq lstRT (cons item lstRt))
(setq 1st (car lstRT))
)
(reverse lstRT)
)

 

With list in Lee post, i want it like (sort lst 0), and Lee method like (sort lst 10).

This is "common" way, but i feel it's faster slightly than other ??Is it ?

 

P/s : @RenderMen : Does OP mean ?? Sorry my Eng not well, so, it's difficult to me to understand "Abbreviation" (i have use Google to write any char :( )

Link to comment
Share on other sites

I actually drew points per the OP specified layout, and took into account specific point selection order (again, per the OP).

 

Sorry, I was just looking to write for a general point list, not a specific layout - in fact, that's how I view pretty much all of the problems on here, I don't like to have code that works only for some specific cases. Of course, its not always possible to account for all cases - I would think even David's or my code would also fail for some specific point lists, but I try to minimise these cases.

Link to comment
Share on other sites

P/s : @RenderMen : Does OP mean ?? Sorry my Eng not well, so, it's difficult to me to understand "Abbreviation" (i have use Google to write any char :( )

 

OP = Original Post ( the first post in this thread )

 

@ ketxu - Sorry I missed your post, I had a barbecue to attend yesterday (Mmmm steak, and chicken!)... thankfully David has answered your question.

 

Sorry, I was just looking to write for a general point list, not a specific layout - in fact, that's how I view pretty much all of the problems on here, I don't like to have code that works only for some specific cases. Of course, its not always possible to account for all cases - I would think even David's or my code would also fail for some specific point lists, but I try to minimise these cases.

 

@ Lee - I understand, and appreciate your doing so, as this correctly helps far more users than the individual OP for any given issue.

 

I just need more time (something I am running very short on these days!) to improve my reasoning, logic, etc. especially with lists, recursion... clearly my code is the inverse of your own in that it is only applicable for a limited number of situations. Development fundamentals, and knowing when to leverage the correct combination of functions is often where I've found I make mistakes.

 

This is something that I would like to improve on.

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.

Guest
Unfortunately, your content contains terms that we do not allow. Please edit your content to remove the highlighted words below.
Reply to this topic...

×   Pasted as rich text.   Restore formatting

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×
×
  • Create New...