The routines are simple and just do simple searching, etc. I have not
tried to optimize them. On my system, they work reasonably
for my purposes.
For instance, the routine 'min_dist(list_1, list_2)' will find the
minumum distance between two lists of 100 vectors of dimension 100 in
about 6 or 7 reported seconds with 'showtime: true'.
I am attaching the file 'dist_utilities.mac' which contains the
utilities.
I put in a test program 'te(n,m,dim)' which tests the routines on
randomly generated vectors in the unit cube of dimension 'dim'.
Any comments or suggestions are welcome.
TIA,
-sen
---------------------------------------------------------------------------
| Sheldon E. Newhouse | e-mail: sen1 at math.msu.edu |
| Mathematics Department | |
| Michigan State University | telephone: 517-355-9684 |
| E. Lansing, MI 48824-1027 USA | FAX: 517-432-1562 |
---------------------------------------------------------------------------
On Mon, 9 Apr 2007, Stavros Macrakis wrote:
> Looks interesting. I haven't heard of such routines in Maxima.
>
> What algorithms are you using? Do they work for arbitrary dimensions?
> I'm assuming you're representing points in rectilinear coordinates
> (as n-lists)?
>
> You might want to post the code for comments....
>
> -s
>
-------------- next part --------------
/************************************************************************
Copyright (C) 2007 Sheldon E. Newhouse <newhouse at math.msu.edu>
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston,
MA 02111-1307 USA
*************** 04/10/2007 **************************************/
ratprint: false;
showtime:true;
/*
xy(n) makes an n-vector of random numbers in [0,1];
xx(n,m) makes a list of of n points in R^m with elements
given by xy(m);
te(n,m,dim) finds the minimum distance from the point sets
given by xx(n,dim) and xx(m,dim)
Let's call the output of xx(n,m) a 'list of n random m-vectors'
Then, te(500,100,10) finds the minimum distance between
a list of 500 random 10-vectors and
a list of 100 random 10-vectors
The function
min_line(list1, list2, NumPoints) creates the line setment with
NumPoints points of minimal length between the elements of list1 and
list2. 'max_line' is similar.
Try e.g.,
min_line(xx(10,10),xx(10,10),10)
*/
xy(n):=makelist(random(1.0),i,1,n);
xx(n,m):=makelist(xy(m),i,1,n);
te(n,m,dim):=min_dist(xx(n,dim),xx(m,dim));
/* below are the tools for min_dist and related tools */
alias(prt, print)$
index_list(list):= makelist([list[i],i],i,1,length(list))$
index_list_usg: prt(" index_list(list) gives the list of pairs
[list[i],i] ")$
/*
LS_pair(p,q,NumPoints):=makelist([i*q[1]/NumPoints+(1-i/NumPoints)*p[1],i*q[2]/NumPoints+(1-i/NumPoints)*p[2]],i,1,NumPoints);
*/
LS_pair(p,q,NumPoints):=makelist([i*q/NumPoints+(1-i/NumPoints)*p,i*q[2]/NumPoints+(1-i/NumPoints)*p],i,1,NumPoints);
LS_pair_usg: print(" LS_pair(p,q,NumPoints) gives the line segment
joining the two points p and q with NumPoints points ")$
Max(a,b):= block( if (a > b) then return(a) else return(b))$
Min(a,b):= block( if (a < b) then return(a) else return(b))$
xvar(y):= [x,-y,y];
yvar(x):= [y,-x,x];
zvar(x):= [z,-x,x];
List_Max(list):= block([z], z: list[1],for i:1 thru length(list) do (z: Max(list[i],z)), return(z));
List_Min(list):= block([z], z: list[1],for i:1 thru length(list) do (z: Min(list[i],z)), return(z));
alias(Lmax, List_Max);
alias(Lmin, List_Min);
Norm(list):= float(sqrt(inprod(list,list)));
List_Max_2(list):= block([z], z: [[1],list[1]],
for i:1 thru length(list) do
if not(list[i] < z[2]) then
if list[i] > z[2] then z: [[i],list[i]]
else if i # 1 then z: [endcons(i,z[1]), list[i]],
return(z))$
List_Max_2_usg: prt("List_Max_2(list) returns a list of length
two. The second term is max(list), and the first term is a list of the
indices where this max appears. LMax_2 is an alias.");
List_Min_2(list):= block([z], z: [[1],list[1]],
for i:1 thru length(list) do
if not(list[i] > z[2]) then
if list[i] < z[2] then z: [[i],list[i]]
else if i # 1 then z: [endcons(i,z[1]), list[i]],
return(z))$
List_Min_2_usg: prt("List_Min_2(list) returns a list of length
two. The second term is min(list), and the first term is a list of the
indices where this min appears. LMin_2 is an alias. ");
alias(LMax_2, List_Max_2);
alias(LMin_2, List_Min_2);
/* for the distance from a point to a list */
point_list_distance(p,list):=block([t_list: list, N_list, min_dist],
N_list: makelist(Norm(p-t_list[i]),i,1,length(t_list)),
min_dist: LMin_2(N_list),
return(min_dist)
)$
point_list_distance_usg: prt(" point_list_distance(p,list) gives the
minimum distance from the point 'p' to the elements of the list
'list'. It gives the positions where the minimum occurs as well as the
actual distance. An alias is pmin_list or pmin_dist")$
alias(pmin_list,point_list_distance)$
alias(pmin_dist,point_list_distance)$
point_list_max_distance(p,list):=block([t_list: list, N_list,max_dist],
N_list: makelist(Norm(p-t_list[i]),i,1,length(t_list)),
max_dist: LMax_2(N_list),
return(max_dist)
)$
alias(pmax_list,point_list_max_distance)$
alias(pmax_dist,point_list_max_distance)$
point_list_max_distance_usg: prt(" point_list_max_distance(p,list) gives the
maximum distance from the point 'p' to the elements of the list
'list'. It gives the positions where the maximum occurs as well as the
actual distance. An alias is pmax_list or pmax_dist.")$
List_Min_3(list):= block([z], z: [[1],list[1]],
for i:1 thru length(list) do
if not(list[i] > z[2]) then
if list[i] < z[2] then z: [[i],list[i]]
else if i # 1 then z: [endcons(i,z[1]), list[i]],
return(z))$
/* added 4-7-2007 */
pmin_line(p,list):= LS_pair(p,list[pmin_list(p,list)[1][1]],500)$
pmax_line(p,list):= LS_pair(p,list[pmax_list(p,list)[1][1]],500)$
pmin_line_usg: prt("pmin_line(p,line) gives the minimum distance from
the point 'p' to the line 'line' ");
pmax_line_usg: prt("pmax_line(p,line) gives the maximum distance from
the point 'p' to the line 'line' ");
/* Next, we get the minimum and maximum distances between two lists,
list_1, and list_2 */
/* Test lists, uncomment below when testing */
xx: [[3,2], [4,5], [6,1]];
xy: [[2,4],[1,3],[2,4]];
p: [1.5];
min_dist(list_1, list_2):=
block(
[list_1t: list_1, list_2t: list_2, A, list_3t, slist_3t,list_3t_ind,
slist_3t_ind, list_4t, numer: true],
/* first we make a new list, list_3t whose length equals that of
list_1 and whose i-th entry is pmin_list(list_1t[i], list_2t)*/
list_3t: makelist( pmin_list(list_1t[i],list_2t),i,1,length(list_1t)),
/* Next, we index it */
list_3t_ind: index_list(list_3t),
/* next, we sort the indexed list and return
the first element */
/* slist_3t: sort(list_3t), */
/* we also sort list_3t_ind, and add it to the returned stuff */
slist_3t_ind: sort(list_3t_ind),
return(first(slist_3t_ind))
)$
min_dist_usg: prt(" min_dist(list_1, list_2) returns the minimum
distance from points in list_1 to those in list_2. It returns a pair [[list,a],b],
in which 'list' is the set of indices in list_2 where the minimum distance
occurs, 'a' is the minumum distance, and b is an index in list_1
where the minimum occurs. Note, it does NOT return the list of the all
the possible indices for b");
min_line(list_1,list_2,NumPoints):=
LS_pair(list_1[part(min_dist(list_1,list_2),2)],list_2[part(min_dist(list_1,list_2),1,1,1)],NumPoints)$
min_line_usg: prt("min_line(list_1,list_2,NumPoints) gives a line of
minimun distance from list_1 to list_2 with NumPoints points)")$
max_dist(list_1, list_2):=
block(
[list_1t: list_1, list_2t: list_2, A, list_3t, slist_3t,list_3t_ind,
slist_3t_ind, list_4t, numer: true],
/* first we make a new list, list_3t whose length equals that of
list_1 and whose i-th entry is pmax_list(list_1t[i], list_2t)*/
list_3t: makelist( pmax_list(list_1t[i],list_2t),i,1,length(list_1t)),
/* Next, we index it */
list_3t_ind: index_list(list_3t),
/* next, we sort the indexed list and return
the first element */
/* slist_3t: sort(list_3t), */
/* we also sort list_3t_ind, and add it to the returned stuff */
slist_3t_ind: sort(list_3t_ind),
return(last(slist_3t_ind))
)$
max_dist_usg: prt(" min_dist(list_1, list_2) returns the maximum
distance from points in list_1 to those in list_2. It returns a pair [[list,a],b],
in which 'list' is the set of indices in list_2 where the maximum distance
occurs, 'a' is the maxumum distance, and b is an index in list_1
where the maximum occurs. Note, it does NOT return the list of the all
the possible indices for b");
max_line(list_1,list_2,NumPoints):=
LS_pair(list_1[part(max_dist(list_1,list_2),2)],list_2[part(max_dist(list_1,list_2),1,1,1)],NumPoints)$
max_line_usg: prt("min_line(list_1,list_2,NumPoints) gives a line of
maximun distance from list_1 to list_2 with NumPoints points)")$