Skip site navigation (1)
Skip section navigation (2)
## Re: find close (duplicate) points + create index

### In response to

### pgsql-novice by date

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

- Re: find close (duplicate) points + create index at 2004-03-10 09:22:47 from Elinor Medezinski

Next: From:Bob JarmanDate:2004-03-15 00:58:55Subject: CMSPrevious: From: Bruno Wolff IIIDate: 2004-03-14 00:13:33Subject: Re: find close (duplicate) points + create index