Group Admins

  • Profile picture of Karim
  • Profile picture of Jean

OpenMusic

Public Group active 5 hours, 24 minutes ago

User group for OpenMusic and computer-aided composition. Visit the Forum for discussions.

Rearrange point-pairs list with "closest pairs" algorithm

Author 2 Subscribed Users |
Profile photo of Francesco Vitale
Francesco Vitale

Hi all,
I’m looking for a lisp code that rearranges a list (obtained with point-pairs from a bpf) so that the points which are the closest together are written consecutively in a new list. In other words, is there an OM implementation of a solution to the so-called “closest pair problem” (i.e.: given a list (x1,y1),(x2,y2),…,(xn,yn) of points, find the pair of points that are closest together)? Thanks in advance for your kind attention, as usual.
Best,
Francesco Vitale

June 22, 2018 at 17:59 #26839
Profile photo of Francesco Vitale
Francesco Vitale

To avoid much confusion, I’ll try to restate my purpose in a different way, hoping to make it clearer: what I’m looking for is a code that finds the closest point to a starting point (e.g. the first one in the original list from point-pairs), then takes the found one and repeat the search of closest one, rearranging the original list in the new found order. That would be a sorting loop that starts from a point, finds the nearest one, then takes the latter, finds the nearest and so on… Any help or suggestion is greatly appreciated.
All the best,
Francesco Vitale

June 27, 2018 at 18:08 #26870
Profile photo of JialinLiu
JialinLiu

Hey Francesco,

I have some similar functions and have tried to combine them together. It that what you mean?

(in-package :om)

(defmethod distance-2-points ((pair-a list) (pair-b list))
(sqrt (om+ (om^ (- (car pair-a) (car pair-b)) 2) (om^ (- (cadr pair-a) (cadr pair-b)) 2))))

(defun sort-list-nearst-cadr (num comb-lst)
(let* ((mat-tr-comb-lst (mat-trans comb-lst))
(lst (cadr mat-tr-comb-lst))
(sub-lst (om- lst num))
(abs-lst (om-abs sub-lst))
(mat-tr-lst (mat-trans (append (list abs-lst) (list comb-lst))))
(sort-lst (sort-list mat-tr-lst :key #’car))
(mat-tr-sort-lst (mat-trans sort-lst))
)
(cdr mat-tr-sort-lst)))

(defun sort-point-list-nearst (first-point other-point)
(let* ((dis-lst (mapcar #'(lambda (x) (distance-2-points first-point x)) other-point))
(trans-lst (mat-trans (list other-point dis-lst))))
(car (mat-trans (car (sort-list-nearst-cadr 0 trans-lst))))))
;(sort-point-list-nearst ‘(0 0) ‘((0 0) (3 5) (4 5) (5 3) (3 7) (9 9) (10 10)))

(defun point-closest-tree (point-lst)
(let* ((rest-point point-lst)
(col-point nil))
(loop for i to (- (length point-lst) 1)
do
(let* ((sorted-point (sort-point-list-nearst (car rest-point) (cdr rest-point))))
(setf col-point (append col-point (list (car rest-point)))
rest-point sorted-point)))
col-point))

(point-closest-tree ‘((0 0) (3 5) (4 5) (5 3) (3 7) (9 9) (10 10) (10 10.1) (9.99 10.0)))

; result ===> ((0 0) (3 5) (4 5) (3 7) (5 3) (9 9) (9.99 10.0) (10 10) (10 10.1))

Best,
Jialin

June 27, 2018 at 23:52 #26883
Profile photo of Francesco Vitale
Francesco Vitale

Dear Jialin,
I am very grateful to you for your code, since it seems to me to get where I meant. But I didn’t manage to make it work: here’s a simple patch (see the .omp attached). The result I get (see the screenshot.pdf) is a sequence of points that’s exactly like the original one, so the bpc (and the order of its points) is unchanged. What I’d need to get, from the starting bpc with its sequence of points (see 1.pdf), is a new bpc with the order of the connections between points rearranged on the base of the “closest point” criterion (see 2.pdf). Am I missing something? Thanks again for your help.
Best,
Francesco

Attachments:
  1. screenshot.pdf
June 28, 2018 at 11:01 #26894
Profile photo of JialinLiu
JialinLiu

Hi Francesco,

I could not get your omp file, it seems to be blank.
So I have tried with a similar Bpc, and it seems to be OK (see photo 1-3). I think you can try to remove the two textfiles, because it could lead to the problem with parenthesis, so that the mat-trans could not do the right job.

Best,
Jialin

Attachments:
  1. 1

    1.png

  2. 2

    2.png

June 28, 2018 at 12:23 #26903
Profile photo of Francesco Vitale
Francesco Vitale

Dear Jialin,
sorry for the blank patch.

June 28, 2018 at 12:52 #26910
Profile photo of Francesco Vitale
Francesco Vitale

Dear Jialin,
I try to attach it here again (applying your good suggestion to remove the two textiles). Judging from your screenshots, it all seems to work fine, but here, in my patch, I have the same result as the starting bpc. Let me know if you have any trouble in opening the .omp.
Best,
Francesco

June 28, 2018 at 12:53 #26913
Profile photo of Francesco Vitale
Francesco Vitale

Ok Jialin,
now it seems to work also for me. It didn’t work before simply because I made a silly error: I used a bpf box in the output instead of a bpc! Many thanks for your brilliant solution!
Best,
Francesco

June 28, 2018 at 13:02 #26916
Profile photo of JialinLiu
JialinLiu

Hi Francesco,

you are welcome! This kind of sortation is what I am working with now (to organize the instrumental gesture and so on), have fun with that!

Best,
Jialin

June 29, 2018 at 06:11 #26921
Profile photo of Francesco Vitale
Francesco Vitale

Hi Jialin,
that’s surely interesting: keep up your good work, and also keep us informed about its progress, if you wish.
Best,
Francesco

June 29, 2018 at 09:37 #26922

You must be logged in to reply to this topic.

Log in now