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!