Yesterday I asked for a fast way to search an object in MapBasic to return the segment and node id for the nearest node in the object to a particular point. I wanted something faster than the brute force method of simply checking the distance to every node in the object. I also needed this method to work for one-shot search on objects, so pre-indexing the object's nodes wouldn't be worth the trouble since it would be slower than the brute force method.
The short answer is that I figured out a way to do it that improves on the brute force speed by factors of 2 to 12 times, and infinite times in some cases (I get execution times of 0 seconds sometimes), depending on the chip you're using and the available memory. You can download the source and 7.5 MBX for this demo app at ftp://ftp.gisnet.com/pub/NodeSearch.zip. Peter Horsb�ll M�ller had a good suggestion for the brute force method. While searching the nodes, if you find a distance of 0, or a distance less than some minimum distance, you can just go with it and not search the rest of the nodes. A good idea, but it only works in exceptional situations. Several people suggested that I use a DLL to do the calculation, since DLL code executes MUCH faster than MapBasic code. The fatal flaw here is that I would have to load the DLL with all the points before I could take advantage of the DLL's performance. But if I have to visit every node anyway, it seems that the Distance() function might just be faster anyway. The mitab dll was mentioned with performance advantages of about 600 times. See http://mitab.maptools.org/mitab-1.2.4-win32.zip or http://mitab.maptools.org if you're interested in that. More than one person suggested that the brute force method was "mathematically fastest" and that in MapBasic I couldn't do better. Wrong. As I suspected, using functions like Overlap() and ExtractNodes() I was able to push the envelope a bit. The big clue came from some code sent to me by Tony (who goes by the handle "Photogrammetry GIU".) In it he used a technique of a linearly expanding box from the search point until it intersected the object. He suggested that a spatial binary search might be better. It is. In the demo app that I've put on my FTP site, I use a binary spatial search (using circles with varying radii instead of a box) and I use Overlap() until I can clip off a polyline of nodes from the object that contains less than 5 nodes. Then I use the brute force method on that to find the location of the nearest node. If all I needed was the location, then I could stop right there. But I need the segment and node id; not just its location. So the next trick is to pass the starting and ending nodes of the object to a recursive function that tests to see if the node location is in the MBR of the node groups. If it is, then these nodes are also split into a first half and a second half, and then the function calls itself with each group testing to see if the point is in these new MBRs, etc. Some of these node groups do not have the searched-for node in their MBR, so you can immediately eliminate them. The other groups are continually split until you get down to the one node that's the one. Recursive algorithms are hard to explain, and even harder to bend your mind around them, but they are very handy in "divide and conquer" situations. You can download the code and fiddle with it yourself if you're interested. As to performance, on a 1.2 GHz Athlon with 512 MB RAM, I search nearest nodes on the state of Texas (I tested this with Texas because it's got lots of nodes) and find brute force search times of about 3-4 seconds. The "speedy" method takes zero seconds. On my PIII laptop, I see similar brute force speeds, but after a few searchs, the brute force method slows to 11-12 seconds (I don't know why performace drops suddenly on my memory-tight laptop after about 6 searches.) However, the speedy method still takes only zero secods. I think it will be hard to beat zero execution time. If you can do that, then you've got a time machine that could be used to predict the future. Thanks for the help, folks! - Bill Thoen --------------------------------------------------------------------- List hosting provided by Directions Magazine | www.directionsmag.com | To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED] Message number: 14005
