Correction.
The routine LS_pair in the previous 'dist_utilities.mac' attachment
was incorrect. I had changed from a 2-dim to an n-dim routine
carelessly. The current version at least has that corrected.
Thanks for any comments.
-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 |
---------------------------------------------------------------------------
-------------- 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,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)")$