MathGroup Archive 2003

[Date Index] [Thread Index] [Author Index]

Search the Archive

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!


  • Prev by Date: Re: Finding the closest number from a list
  • Next by Date: Re: Finding the closest number from a list
  • Previous by thread: Re: Finding the closest number from a list
  • Next by thread: Re: Finding the closest number from a list