## [REBOL] Interleaving of strings question Re:(4)

### From: joel:neely:fedex at: 25-Sep-2000 10:18

[grantwparks--yahoo--com]wrote:> Yow! I guess it's a lot safer to play in the > theoretical space ;) I was wondering tho' if you > imagine a 3-dimensional space, does changing the power > to 3 from 2 work for Pythagoras? >Yes, if your 3-space is Euclidean.> I recently talked to some GIS guys who pointed out the > inherent errors in GPS because the tectonic plates > move up to 51 cm / year, or something. They got a big > kick out of that, but somehow I missed the punchline. >ROTFL! You should respond, "Yeah, but they more than compensated for that when they turned of SA!"> I did think, though, that this was a definitively more > accurate method than the original discussion (don't > know if you saw it) that was going to interleave the > long digits into the latitude... >Well, I saw it, but didn't understand what problem was being solved (and still don't). Is the task is to: 1) take a given target location and return the point in the database that is geographically nearest; 2) take a given target location and return a list of all points from the database that are "near enough"; 3) sort a collection of points and present a human- readable display based on nearest-to-farthest; or 4) something else? In addition, I'm unclear as to whether: 1) the target is an arbitrary point or is constrained to be one of the points in the database; 2) how many points are in the database; 3) what resolution is required; and 4) the dispersion of the points in the database: 4a) how wide an area is covered, and 4b) how "clumpy" the distribution is. All of these would influence my choice of strategy. For example, if the task is (1) or (2), and the points are fairly uniformly distributed over a large range of lat/lon values, I'd consider a two-level strategy of partitioning the data into coarse-grained lat/lon cells (one-time, front-end work), then searching only the cell that should contain the target point (or nearby cells as needed for near enough or "empty cell" constraints). For example -- assuming two-degree cells for the sake of illustration -- to locate the point 37.4968N x 89.9935W, look first in the cell containing 36-37N x 88-89W. As needed, expand the search into the neighboring cells: ...... ...... ...... ...... ...... ...... ...... ...... ...... ...... ...... 38-39N 36-37N 34-35N ...... ...... 90-91W 90-91W 90-91W ...... ...... 38-39N 36-37N 34-35N ...... ...... 88-89W 88-89W 88-89W ...... ...... 38-39N 36-37N 34-35N ...... ...... 86-87W 86-87W 86-87W ...... ...... ...... ...... ...... ...... ...... ...... ...... ...... ...... This strategy lets you "zoom in" quickly to the area of relevance, then do the more complex calculations only for a small subset of the space. Another strategy would be to pre-compute the true distance-from-origin for each point (storing that value with each point), then use that as a figure of merit for limiting the search space. Points near the target will obviously have a similar distance-from-origin to the target's value. Of course, the converse is not true (90Nx0W is the same distance from 0Nx0W as 0Wx90N), but the point of this trick is just to reduce the nunber of points that must be individually evaluated. Working with real data on real computers with real memory and performance limits can DEFINITELY get hairy! Have fun! -jn-