# Nearest Neighbor in PostGIS [closed]

I would like to write a php script that takes a coordinate as input and finds the nearest vertex of the road_network.

Is this possible with ST_ClosestPoint?

Or do I need nearest neighbor method?

And how could I implement the query since I don't know the geometry of the point I'm looking for?

I enter a random point (blue point in the picture) and the result of the 2nd to last query is the red point. The yellow line on the network is a part of my road network which is split by pgr_nodeNetwork. What I'd like the result of the query to be is either the upper or the lower vertex of the yellow line (actually the closest to the blue point)

• ST_DWithin will be faster postgis.net/docs/ST_DWithin.html
– Mapperz
Commented Feb 10, 2017 at 15:45
• I think that this returns true if the two geometries you define are within the distance you ask. Can it be applied like "find the nearest point in 100 meters" ? Commented Feb 10, 2017 at 16:20
• select * from theuser where ST_DWithin(point , ST_GeomFromText('POINT(120.9982 24.788)',4326) , 0.1/111.325 ); will find any (if any) within the point/lat/lng (100m)
– Mapperz
Commented Feb 10, 2017 at 16:28
• I think you want to combine it with ST_Dump, as explained here with respect to two lines. Commented Feb 10, 2017 at 17:53
• Which version of PostgreSQL are you using and PostGIS? If you are using 9.5+ and 2.2+, then <-> (nearest neighbor operator is your best bet) Commented Feb 11, 2017 at 0:54

It seems to me you have three main options:

1. Use ST_DWithin to identify a vertex within a certain distance of the coordinates. The advantage to this is that it makes use of spatial indexes on the geometry column and will be much faster. The disadvantage is that it may not return the nearest road vertex if there isn't a nearby road, or may return multiple vertexes. The multiple vertexes could be handled by checking distance within just those vertexes, with a subquery in the SQL. This approach would be good if you know the nearest vertex will never be more than X distance.

2. Use the methods I outlined earlier (below) to find the nearest vertex in your roads table. I think this gives you more precisely what you are asking for, but the ST_Distance function does not make use of the spatial index so the resulting query may not be performant if you have a lot of roads and vertexes.

3. Use the ST_DumpPoint function to populate a new table with the vertexes. Place a spatial index on the points, and then query against this table using the <-> bounding box operator in the ORDER BY and limiting to one. This makes use of bounding boxes in spatial indexing, and because the bounding box is on a point rather than a line it is more exact (a bounding box on a long, curving road may fully encompass your point). If you need information on the road itself, you can include a road_id in the new vertex table and join to it. The disadvantages to this approach are the one-time creation of the vertexes (more than one time if your roads change frequently), and the time to create the table. If you care which road is being located, you may also need to make accommodations for roads that have common vertexes (intersections).

Earlier real-time query strategy posted earlier:

Depending on what you are trying to identify, one of the following PostGIS SQL queries should work. I've provided options to select the nearest road to the selected point, the nearest point on the road (not necessarily a vertex, or the nearest vertex on the road.

• Replace x,y with point coordinates in all examples below.
• Replace 'road' with name of line layer.
• The line layer and point need to have the SRID (I've assumed 4326).

To find the nearest line:

``````SELECT  r.gid,
r.geom,
ORDER BY ST_Distance(r.geom,
ST_SetSRID(ST_MakePoint(x, y), 4326)) ASC
LIMIT 1;
``````

To find the nearest point on a line (not necessarily a vertex). This may perform slowly with a lot of lines - see vertex example below.

``````SELECT  ST_ClosestPoint(r.geom, ST_SetSRID(ST_MakePoint(x, y), 4326)) as closest_pt,
ORDER BY ST_Distance(r.geom, ST_SetSRID(ST_MakePoint(x, y), 4326)) ASC
LIMIT 1;
``````

To find the nearest vertex in a lines layer (simpler, but less efficient?)

``````SELECT d.geom
FROM
(SELECT (ST_DumpPoints(r.geom)).geom as geom FROM public.road r) AS d
ORDER BY ST_Distance(d.geom, ST_SetSRID(ST_MakePoint(x,y), 4326)) ASC
LIMIT 1;
``````

The following method of finding the nearest vertex could be faster because it only dumps vertices of the nearest line, rather than all lines in the layer. This allows the line to be selected with a spatial index prior to the dump. Note that x, y needs to be entered twice.

``````SELECT  d.geom
FROM (SELECT
(ST_DumpPoints(
(SELECT r.geom AS geom
FROM public.road r  --PERHAPS PLACE ST_DWithin SUBQUERY HERE
ORDER BY
ST_Distance(r.geom, --AVOIDS POTENTIAL BOUNDING BOX ISSUE WITH <->
ST_SetSRID(ST_MakePoint(x, y), 4326))
ASC
LIMIT 1
))).geom AS geom FROM public.road r
) AS d
ORDER BY ST_Distance(d.geom, ST_SetSRID(ST_MakePoint(x, y), 4326)) ASC
LIMIT 1;
``````

EDIT Based on @LR1234567's comment above, the ST_Distance doesn't use the index the way I expected. I believe the SQL below will do better, but may introduce some approximations the way bounding boxes are used, as described here.

``````SELECT  d.geom,            --remove comma if not doing optionals below
ST_AsText(d.geom), --optional
ST_X(d.geom),      --optional
ST_Y(d.geom)       --optional
FROM (SELECT
(ST_DumpPoints(
(SELECT r.geom as geom
ORDER BY
r.geom <-> ST_SetSRID(ST_MakePoint(x, y), 4326)
ASC
LIMIT 1
))).geom as geom FROM public.road r
) AS d
ORDER BY ST_Distance(d.geom, ST_SetSRID(ST_MakePoint(x, y), 4326)) ASC
LIMIT 1;
``````
• As you mentioned, St_distance does not make use of indexes, though st_dwithin does. Commented Feb 11, 2017 at 4:57
• WOW...!!!! I am astonished by the answers of this community. Thanks a lot you guys. So far the last snippet works perfectly for here. Taking for granted that this is running in localhost it took 43msec to execute the query. I need to revise PostGIS functions a bit though some of this looks really new. Thank you..!!! Commented Feb 11, 2017 at 15:24
• @Stefanos Out of curiosity, how long does it take to run the second to last code block? Commented Feb 11, 2017 at 15:54
• OK wait, we have an update here. I created Spatial Indexes on the road network like: CREATE INDEX ON roads USING GIST(geom). Then VACUUM ANALYZE. Now the last snippet runs in 36ms and the second in 41msec. Normal ? (Which spatial index comes by default? R-Tree or GIST? ) Commented Feb 11, 2017 at 16:04
• It sounds kind of normal to me, but is dependent on data set, etc. A brief search seems to indicate GIST is default for spatial indexes in PostGIS with an R-tree overtop of the GIST. It looks like PostgreSQL geometry (without PostGIS) could use SP-GIST? It's not something I know very well presently. The vacuum likely helped, too. Commented Feb 11, 2017 at 19:43