Thread: nearest match
I'm doing some work with part diagrams and server-side image maps. I want to store single point coordinates (x,y) for reference numbers in a table looking like: reference_number text, x int, y int My question is: How can I find the *nearest* match of some clicked on coordinates without specifying some arbitrary distance from the stored point? The more I think about this the more I am realizing it is probally not that hard, I just can't seem to grasp the answer right now. Thanks, Ryan
Ryan wrote: > I'm doing some work with part diagrams and server-side image maps. > I want to store single point coordinates (x,y) for reference numbers in a > table looking like: > > reference_number text, > x int, > y int > > My question is: How can I find the *nearest* match of some clicked on > coordinates without specifying some arbitrary distance from the stored > point? > > The more I think about this the more I am realizing it is probally not > that hard, I just can't seem to grasp the answer right now. Can you say it in math logic? How to find, that some points are nearer then other without counting distance? For image maps consider using geometric types like polygon. You need only one row for one area when using them. Regards, Tomasz Myrta
I have no idea if this is a *good* way to do this. I do notice that PostgreSQL has a pile of geometric functions which (to my mind at least) would almost certainly be a better match than making this up yourself. This is especially true since one of the geometric functions <-> gives you distance without having to remember the Pythagorean theorem. First of all let's solve the problem using the table that you supplied. First I created the table and filled it with values. create table foo (reference_number text, x int, y int); insert into foo (reference_number, x, y) values ('001', 0, 0); insert into foo (reference_number, x, y) values ('002', 100, 100); insert into foo (reference_number, x, y) values ('003', 0, 100); insert into foo (reference_number, x, y) values ('004', 100, 0); Then I used a little geometry to calculate the distance from each point to the point (10, 10). test=# select reference_number, sqrt(pow(abs(x - 10), 2) + pow(abs(y - 10), 2)) as distance from foo order by distance;reference_number | distance ------------------+------------------001 | 14.142135623731003 | 90.5538513813742004 | 90.5538513813742002 | 127.279220613579 Pretty neat, huh? Now by adding a limit statement we can get the closest point. Please note, if several points are equally close PostgreSQL will simply pick one. test=# select reference_number, sqrt(pow(abs(x - 10), 2) + pow(abs(y - 10), 2)) as distance from foo order by distance limit 1;reference_number | distance ------------------+-----------------001 | 14.142135623731 (1 row) Well, that was fun. Now here's a similar example using the built in geometric types. First I create the table: create table bar (reference_number text, location point); insert into table bar (reference_number, location) values ('001', '(0,0)'); insert into table bar (reference_number, location) values ('002', '(100, 100)'); insert into table bar (reference_number, location) values ('003', '(0, 100)'); insert into table bar (reference_number, location) values ('004', '(100, 0)'); Now I query the table. Notice how much easier the <-> operator is to use than the other query. It's probably faster too because some smart hacker wrote the operator in C. test=# select reference_number, location, point '(10, 10)' <-> location as distance from bar;reference_number | location | distance ------------------+-----------+------------------001 | (0,0) | 14.142135623731002 | (100,100)| 127.279220613579003 | (0,100) | 90.5538513813742004 | (100,0) | 90.5538513813742 (4 rows) Adding the limit clause to narrow our search gets us: test=# select reference_number, location, point '(10, 10)' <-> location as distance from bar limit 1;reference_number | location| distance ------------------+----------+-----------------001 | (0,0) | 14.142135623731 (1 row) I hope this is helpful, Jason "Ryan" <pgsql-sql@seahat.com> writes: > I'm doing some work with part diagrams and server-side image maps. > I want to store single point coordinates (x,y) for reference numbers in a > table looking like: > > reference_number text, > x int, > y int > > My question is: How can I find the *nearest* match of some clicked on > coordinates without specifying some arbitrary distance from the stored > point? > > The more I think about this the more I am realizing it is probally not > that hard, I just can't seem to grasp the answer right now. > > Thanks, > Ryan > > > > ---------------------------(end of broadcast)--------------------------- > TIP 6: Have you searched our list archives? > > http://archives.postgresql.org
> Ryan wrote: >> I'm doing some work with part diagrams and server-side image maps. I >> want to store single point coordinates (x,y) for reference numbers in >> a table looking like: >> >> reference_number text, >> x int, >> y int >> >> My question is: How can I find the *nearest* match of some clicked >> on coordinates without specifying some arbitrary distance from the >> stored point? > > How about something like this? > > select reference_number, '(50,50)'::point <-> point(x,y) as distance > from my_table order by distance limit 1; > > With a reasonably small table, it should perform fairly well. Hot damn! thats exactly what I needed. I imagine I would only be comparing the distance of 50 points at any given time (about the max number of reference numbers on any given image) so its mighty quick. (184 points takes 1.80 msec to check) I didn't even know about those geometric operators (I find new stuff every day I swear). Are they SQL standard or postgres specific? Ryan
> Ryan wrote: >> I'm doing some work with part diagrams and server-side image maps. I >> want to store single point coordinates (x,y) for reference numbers in >> a table looking like: >> >> reference_number text, >> x int, >> y int >> >> My question is: How can I find the *nearest* match of some clicked on >> coordinates without specifying some arbitrary distance from the stored >> point? > > How about something like this? > > select reference_number, '(50,50)'::point <-> point(x,y) as distance > from my_table order by distance limit 1; > > With a reasonably small table, it should perform fairly well. Hot damn! thats exactly what I needed. I imagine I would only be comparing the distance of 50 points at any given time (about the max number of reference numbers on any given image) so its mighty quick. (184 points takes 1.80 msec to check) I didn't even know about those geometric operators (I find new stuff every day I swear). Are they SQL standard or postgres specific? Ryan
--On Thursday, March 13, 2003 11:22:21 -0600 Ryan Orth <ryan@seahat.com> wrote: >> Ryan wrote: > Hot damn! thats exactly what I needed. I imagine I would only be > comparing the distance of 50 points at any given time (about the max > number of reference numbers on any given image) so its mighty quick. > (184 points takes 1.80 msec to check) > > I didn't even know about those geometric operators (I find new stuff every > day I swear). Are they SQL standard or postgres specific? postgres specific. There are a WHOLE bunch of geometric operators and functions in PG. LER -- Larry Rosenman http://www.lerctr.org/~ler Phone: +1 972-414-9812 E-Mail: ler@lerctr.org US Mail: 1905 Steamboat Springs Drive, Garland, TX 75044-6749