Re: find close (duplicate) points + create index

On Wed, 10 Mar 2004, Elinor Medezinski wrote:

> > I'd look at making an rtree index on
> > the unit box around each point, and then using an "overlaps" test as
> > an indexable coarse filter before the exact distance check.
>
> I didn't understand this either.

Lets say a 2D point comes from GPS, and has coordinates (from some
particular zone) of (483121.534, 5124378.745). The units are
meters, and so these coordinates are both specified to the nearest
millimeter (which is too many significant figures for a GPS
measurement without special equipment).

We can construct a small box around this point, by chopping off
the fractional meters, and either adding or subtracting 1. We
will also assume that any boxes we make, have sides parallel to
our axis. So, the Upper Left point is (483120,5124379) and the
Lower Right point is (483122,5124377).

This isn't a unit box, it's a 4 unit box. But, it requires less
care in constructing it (in my mind) than making the unit box.
But you can work with unit boxes too. To check that are box
(point) of interest overlaps another box, you check to see that
the minimum X of this box is greater than the minimum X of the
other box and less than the maximum X of the other box. Likewise
for the Y coordinates. You are considering small boxes around
points, and all the boxes are squares. The more general problem,
allows for N-sided polygons, where it is possible for the bounding
boxes to overlap, but for the one box to not be inside the other
box.

If the bounding boxes don't overlap, there is no sense calculating
a distance (in some cases) as the points/boxes are too far apart.

Gord