Re: Finding the closest number from a list
- To: mathgroup at smc.vnet.net
- Subject: [mg39544] Re: Finding the closest number from a list
- From: jrome at mail.com (Jacob Rome)
- Date: Sat, 22 Feb 2003 03:38:09 -0500 (EST)
- References: <b32ab1$b3o$1@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
Wow, I got so many helpful responses from so many people that I'm
blown away! I ended using an approach similar in spirit to the merged
list approach. Here's what I did.
I have two list of nodes on the x-y plane, nXY and oXY. What I want to
do is to determine the point from oXY closest to a point nXY[[i]]. I
will use that guess to help determine which Delaunay triangle (based
upon the oXY set of points) the new point (nXY[[i]]) is located in.
I have created two matrices of sorted values, nSort and oSort. I know
the length of the lists are nNodes (~10,000) and oNodes (~15,000),
respectively. The matrices have two columns, the 1st column has the
magnitude of the node (point on the x-y plane), the 2nd column is the
node number (the row number from the initial matrix).
My problem really has three steps, the way I've constructed it:
1) Find the nodes from oXY which have a magnitude closest to the node
nXY[[i]];
2) From these surrounding nodes, determine which one, oXY[[j]], is
closest to nXY[[i]]; (the point of step 1 is to greatly reduce the
number of nodes to be searched)
3) Find which Delaunay triangle (of oXY) the point nXY[[i]] belongs
to, searching only those triangles which have vertices at oXY[[j]];
(This takes care of 95%+ of my nodes. For the remaining nodes, I've
expanded the search to include more surrounding triangles.)
Therefore, for step 1, I don't need to know the node with the closest
magnitude, I just need to find one of the closest. For step 2, I do
not need to find the absolute nearest node, since that will neither
guarentee that step 3 is a success nor will not finding it ensure that
step 3 fails.
With all that in mind, here's the code I wrote (depth specifies how
many of the nearest nodes to search). The actual sorting takes about
0.36 seconds on a PIII/1000, although Length[oXY]=15000, not 30000 as
previously thought.
nearestNode[depth_, nNodes_, oNodes_, nSort_List, oSort_List,
nXY_List,
oXY_List] :=
Module[{nearest, offset, nearRow, mag, limLow, limUp, cMag,
minMag, cNode,
sortClose, k, testNode},
nearest = Table[0, {jj, nNodes}]; (*
this array will store the nearest node candidate *)
offset = Table[0, {jj, nNodes}];
nearRow = 1;
Do[{
mag = nSort[[k, 1]];
While[mag > oSort[[nearRow, 1]], nearRow++];
limLow = Max[1, nearRow - depth]; (*
limits of the nearest point search *)
limUp = Min[oNodes, nearRow + depth];
minMag = 10000;
Do[{ (*Closest point search *)
cMag = vectMag[
nXY[[nSort[[k, 2]]]] - oXY[[oSort[[testNode, 2]]]]];
minMag = Min[minMag, cMag];
If[cMag == minMag, {cNode = oSort[[testNode, 2]],
sortClose = testNode;}];
}, {testNode, limLow, limUp}];
offset[[k]] = nearRow - sortClose;
nearest[[nSort[[k, 2]]]] = cNode;
}, {k, nNodes}]; Return[{nearest, offset}];];
Again, thanks for everyone's help. I got some really good ideas from
your responses!