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
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
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
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
screenshot.pdf (79.3 KB)
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
Dear Jialin,
sorry for the blank patch.
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
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
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
Hi Jialin,
that’s surely interesting: keep up your good work, and also keep us informed about its progress, if you wish.
Best,
Francesco