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?
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.
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...
--- [EMAIL PROTECTED] wrote:
> Hi, Grant!
>
> 1) A couple of minor tweaks to coord-sort yields
> (*WARNING*
> *UNTESTED CODE FOLLOWS* *TEST BEFORE USING*)
>
> coord-sort: func [a b /local val dim sum] [
> dim: length? a
> sum: 0
> foreach val a [sum: sum + power val dim]
> foreach val b [sum: sum - power val dim]
> sum > 0
> ]
>
> 2) Your generalization over dimensionality appeals
> to me as a
> mathematician, but as a "software engineer" I am
> compelled
> to point out that if you're dealing with a
> performance bottle-
> neck, the following is faster:
>
> coord-sort-2d: func [a b /local val dim sum] [
> dim: length? a
> sum: 0
> foreach val a [sum: sum + (val * val)]
> foreach val b [sum: sum - (val * val)]
> sum > 0
> ]
>
> 3) Putting my mathematics hat back on, I am
> compelled to
> point out that if these are really lat/lon
> coordinates,
> then both the taxicab metric (absolute deltas) and
> squared
> Euclidean metric (sum squared deltas) can give wrong
> answers
> to the general case of "which points are nearest to
> a specific
> target point".
>
> Near the poles, lattitude deltas make MUCH more
> difference
> than comparable longitude deltas. For small deltas,
> a GREAT
> improvement in accuracy results from weighting
> longitude
> delta by cos avg lat in the sum. Some additional
> fiddling
> may be required due to the singularites at the
> poles, but
> pole crossings involve large longitude deltas
> anyway...
>
> 4) Putting my s/w eng'ing hat back on, I should add
> that the
> performance of the whole search issue (assuming
> you might
> need to search for a "nearest point" as in the
> previous
> comment) is dominated by the number of points in the
> entire
> search space. If the space is large, with
> substantial
> dispersion of points, consider using the following
> speedup trick:
>
> The maximum error of the taxicab metric vs. the
> Euclidean
> metric is the square root of two (e.g., the
> point at (1,1)
> has a taxicab metric of 2, instead of the
> Euclidean metric
> of 1.141... -- it's too large by a factor of
> sqrt 2. Ergo...
>
> Make a prepass across the search space using the
> taxicab
> metric, retaining only those points whose
> distance from the
> target is at most 1.414... times the least
> distance-
> from-target found thusfar. Then make a second
> pass across
> only the set collected in the prepass, using the
> correct-
> but-more-expensive real metric.
>
> Hope some of this is helpful!
>
> -jn-
>
> [EMAIL PROTECTED] wrote:
> >
> > Since we want them sorted, we're talking about
> their
> > relative distance from an origin ( 0,0,... ). So
> it
> > became (x1 to the nth + y1 to the nth) < (x2 to
> the
> > nth + y2 to the nth)...
> >
> > If one of you great REBOLs would show how to do
> this
> > using all the niceties of series! traversal I
> would
> > appreciate it; I know my version is a pretty sad
> > procedural version:
> >
> > coord-sort: func [ a b /local sum1 sum2 ] [
> > sum1: 0
> > sum2: 0
> >
> > dimension: length? a
> >
> > while [ not tail? a ] [
> > sum1: add sum1 power first a dimension
> > a: next a
> > ]
> > while [ not tail? b ] [
> > sum2: add sum2 power first b dimension
> > b: next b
> > ]
> > sum1 < sum2
> > ]
> >
>
__________________________________________________
Do You Yahoo!?
Send instant messages & get email alerts with Yahoo! Messenger.
http://im.yahoo.com/
