Administrateur

  • Profile picture of Karim
  • Profile picture of Jean

OpenMusic

Groupe Public active 20 hours et 30 minutes ago

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

Rearrange point-pairs list with "closest pairs" algorithm

Auteur 2 Utilisateurs souscrits |
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

Juin 22, 2018 à 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

Juin 27, 2018 à 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

Juin 27, 2018 à 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
Juin 28, 2018 à 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

Juin 28, 2018 à 12:23 #26903
Profile photo of Francesco Vitale
Francesco Vitale

Dear Jialin,
sorry for the blank patch.

Juin 28, 2018 à 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

Juin 28, 2018 à 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

Juin 28, 2018 à 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

Juin 29, 2018 à 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

Juin 29, 2018 à 09:37 #26922

Vous devez être connecté pour répondre à ce sujet.

Log in now