Mailing List Archive: 49091 messages

## [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-
```