Good discussion. I must admit that I am using the easy solution to just run thru all the nodes in the object. I hadn't given it much thought whether there actually would be a better solution.
But I don't think that you can use the ExtractNodes() function as there might be a risk of skipping the point that actually was closest to the point. This might at least be the risk if you use the MBR to see whether any of the nodes are close to the point. You might risk that the point is just 1 mm north, south east or west of the MBR, and that the nodes in the rest of the original object are further away. This means that there might have been a node only 1 mm from the point, but you ignored these ecause the point wasn't within the MBR. In stead you search in the remaining nodes and find a node 5 meters away. But there might be away of optimizing the search - just a bit. 1. If the point you are searching with is located on top of a node, the distance is 0. And in this case there is no reason to continue looping thru the nodes of the object. 2. You could also use the same approach but specifying that a distance below x meters would be seen as okay, and then stop the looping when the distance is less than this distance. Not that good a solution... 3. And finally you could also use the point to create some kind of a cutter (eg a buffer, quare region or what ever) and then split the object you are searching. In this way you could find the distance to the closest node. What is left is to find the segment no and node no. In this case you could use me second suggestion and using the found distance is the "zero-distance". I'm not sure whether the creating of a buffer/region is actually faster than looping thru the nodes. If not you might only use this method if there were more than 100/10000/100000 nodes in the object Just a few ideas, Peter Horsb�ll M�ller GIS Developer Geographical Information & IT COWI A/S Odensevej 95 DK-5260 Odense S. Denmark Tel +45 6311 4900 Direct +45 6311 4908 Mob +45 5156 1045 Fax +45 6311 4949 E-mail [EMAIL PROTECTED] http://www.cowi.dk/gis -----Original Message----- From: Bill Thoen [mailto:[EMAIL PROTECTED] Sent: Thursday, November 11, 2004 3:09 AM To: MapInfo-L Subject: RE: MI-L Fast node search on an object Milo van der Linden writes: > But I can't see this exercise being a problem with a single point in a > not to big region so I think your problem revolves from performance > problems on large regions or a large set of points. Right. It's only a problem on the largest objects. It's just that I sense a "code smell" that tells me that looping through all nodes is inefficient, and I wondered if there's a more elegant solution. > What you might consider is first doing radius select to decrease the > number of nodes tested. For instance, do a radius search with a > diameter of 1 mile, if the count of the objects returned is larger > then zero, do your calculation, otherwise increase the radius with > certain steps. (Think big, start small) This is a matter of fine > tuning for your specific situation. For objects that are near the > center of a big region this will always be a problem. This won't help because the nodes in MapInfo objects cannot be accessed directly with MapInfo's higher spatial functions. You still have to examine every point and determine if it's in the buffer or not. And if you're going to have to do that, the fastest algorithm is still just the "brute force" method of comparing every point to the given X,Y coordinate. There's only one other hope that I can think of. There is the ExtractNodes() function, which is a fast way to extract a sub-polyline object from a polyline or region object. Can we use this? If there are n nodes in an object, and you use ExtractNodes() to pull nodes 1 to n/2 and find that the Minimum Bounding Rectangle (MBR) of the returned object is not in your area of interest, then you can immediately eliminate nodes 1 to n/2 from your search. That is a faster way to eliminate nodes (if you're lucky) than the brute force method. But of course, this won't always yield cool results, because the sequence of nodes has nothing to do with their spatial distribution, but is it worth exploring ExtractNodes()? Is there anyone interested in applying the lever of their mind to this problem who isn't afraid that the effort might also flip their brains out between their ears? - 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: 13991 --------------------------------------------------------------------- List hosting provided by Directions Magazine | www.directionsmag.com | To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED] Message number: 13995
