Nearest Neighbor in PostGIS [closed]

Question

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)

Answer 1

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, 
FROM public.road r
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,
FROM public.road r
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
            FROM public.road r
            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;