## Re: find close (duplicate) points + create index

From: pgsql-novice(at)postgresql(dot)org Re: find close (duplicate) points + create index 2004-03-14 17:27:46 Pine.A41.3.95.1040314095347.17028A-100000@freenet.edmonton.ab.ca (view raw, whole thread or download thread mbox) 2004-03-04 10:42:23 from Elinor Medezinski  2004-03-10 04:16:24 from Bruno Wolff III  2004-03-10 05:27:27 from Tom Lane   2004-03-10 09:22:47 from Elinor Medezinski    2004-03-10 14:58:22 from Tom Lane     2004-03-10 15:14:15 from "Costin Manda"      2004-03-10 15:27:38 from "Costin Manda"    2004-03-14 00:13:33 from Bruno Wolff III    2004-03-14 17:27:46 from   2004-03-10 12:27:43 from   2005-02-13 15:41:18 from Elinor    2005-02-16 20:08:48 from Tom Lane pgsql-novice
```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

```

### pgsql-novice by date

 Next: From: Bob Jarman Date: 2004-03-15 00:58:55 Subject: CMS Previous: From: Bruno Wolff III Date: 2004-03-14 00:13:33 Subject: Re: find close (duplicate) points + create index

Privacy Policy | About PostgreSQL
Copyright © 1996-2017 The PostgreSQL Global Development Group