Closest Point to a Path

Closest point to a path

You can do this with nn2 from the RANN package. On my system, this computes the nearest center to each of your path points in under 2 seconds.

library(RANN)
system.time(closest <- nn2(centers[, 1:2], path, 1))

#   user  system elapsed 
#   1.41    0.14    1.55 

sapply(closest, head)

#      nn.idx   nn.dists
# [1,] 247451 0.20334929
# [2,] 250454 0.12326323
# [3,] 250454 0.28540127
# [4,] 253457 0.05178687
# [5,] 253457 0.13324137
# [6,] 253457 0.09009626

Here's another example with 2.5 million candidate points that all fall within the extent of the path points (in your example, the centers have a much larger x and y range than do the path points). It's a little slower in this case.

set.seed(1)
centers2 <- cbind(runif(2.5e6, min(x), max(x)), runif(2.5e6, min(y), max(y)))
system.time(closest2 <- nn2(centers2, path, 1))

#   user  system elapsed 
#   2.96    0.11    3.07 

sapply(closest2, head)

#       nn.idx    nn.dists
# [1,]  730127 0.025803703
# [2,]  375514 0.025999069
# [3,] 2443707 0.047259283
# [4,]   62780 0.022747930
# [5,] 1431847 0.002482623
# [6,] 2199405 0.028815865

This can be compared to the output using sp::spDistsN1 (which is much slower for this problem):

library(sp)
apply(head(path), 1, function(x) which.min(spDistsN1(centers, x)))

#       1       2       3       4       5       6 
#  730127  375514 2443707   62780 1431847 2199405 

Adding the point id to the path data.frame and reducing to unique values is trivial:

path$closest.id <- closest$nn.idx
output <- unique(path$closest.id)

Get point on a path or polyline which is closest to a disconnected point

Here is the algorithm that I've implemented as a solution. There's nothing 'non-obvious' in here if you've spent more than ten minutes thinking about it.

I'll reference the distance algorithm which you can find here: https://stackoverflow.com/a/1501725/146077

1. Collect the Polyline as a set of ordered lines
2. Traverse this set, testing the distance from the target point to each line
3. Once the closest line has been identified run the below to identify the closest point on the line.

The answer linked above uses a projection to test if the point is closest to either end of the interval than any other point. I've modified the function from that answer to return the point's position on that projection. Beware that this answer might not make any sense if you haven't read the linked answer!

private Point GetClosestPointOnLine(Point start, Point end, Point p)
{
    var length = (start - end).LengthSquared;

    if (length == 0.0)
        return start; 

    // Consider the line extending the segment, parameterized as v + t (w - v).
    // We find projection of point p onto the line. 
    // It falls where t = [(p-v) . (w-v)] / |w-v|^2
    var t = (p - start) * (end - start) / length;

    if (t < 0.0)
        return start; // Beyond the 'v' end of the segment
    else if (t > 1.0)
        return end;   // Beyond the 'w' end of the segment

    // Projection falls on the segment
    var projection = start + t * (end - start);  
    return projection;
}

Shortest distance between point and path

Are you wanting to calculate this in order to say something like "if the point-to-path distance is zero, then remove the point"? If so, then there is probably an easier way to remove redundant nodes. Take the points three at a time (call them A, B, and C). Calculate the angle between A and B, as well as the angle between B and C. If the two angles are the same, then point B lies in the path between A and C and is redundant. You can use the 'atan2' function (or your language's equivalent) to do the angle calculations.

Algorithm to find the nearest point to a path using Latitude and Longitude

Since no one seems to solve (or maybe understand XD) my problem i'll write down what i've just accomplished on my own.

Basically i used the same solution i posted on the question, but in this answer i'll explain some problem i've found while implementing in the hope that someone one day will find this usefull.

So, the algorithm is this:

• Decompose the path array in smaller arrays. Each of this array has a total distance that i try to keep less than 4 kilometers. If two subsequent points are distant more than 4 kilometers they will be in an array alone. To compute the distance between 2 LatLng point i've used Location.distanceBetween Library.

• For each new path compute the bounds of the concerned area. To compute bounds, expressed as SouthOvest bound and NorthEast bound, i just need to check all the points in the array and save the lowest and the bigest for Latitude and Longitude. To include the points near to the path but out of the bounds i just subtract 500m to SouthOvest Latitude and Longitude and add 500m to NorthEast Latitude and Longitude, more info on how to do this here.

• Make database query for all the points in the area of each path. Since i choose to run all the "little path" on different thread i had some trouble using SQLite, nothing too difficult, you just need to understand how getReadableDatabase work, more info here.

• Compute the distance between all the resulting points and the
  segments in the relative area. Nothing difficult, need to compute distance point-segment for each point and for each segment of the small path. More info onw how to do this with LatLng point here

• Pick the smaller one. When the threads stops the main thread get all the results deleting any copy (Just to solve the possibility of intersected areas as mentioned in the question).

Find closest point on path forwards

You could keep a array consisting of the sorted (start to the end of the path) CLLocation points (hypothetical 100) and evaluate only those poins to find the nearest one that will be visited. To find a visited point you keep the starting position and mesure the distance from the start to the current location of the user(d1). If d1 > distance from start to the next point in the sorted array and the current location is nearby (10 - 100 m) the next point in sorted array then remove the point else user did not visit / passed by that location so you keep it in the sorted array.

Efficient way to find point on a svg stroke closest to the current mouse point?

Interesting, but too involving problem to be solved here.
You will probably need to do some calculations on your own. You might find method getPointAtLength to be useful. If you are comfortable of using some library like D3, you can find some helping functions there as well. I think very good approach to solve this is to segment your path and use Voronoi tessellation. You can find the code and demo here:

https://bl.ocks.org/mbostock/8027835

Closest point on a path to a point, or: Dear target, sorry I missed you

Keep track of the previous distance, and check for the first moment the distance starts to increase.

if ((currentDistance==0) || (currentDistance > previousDistance)) Explode()

It is only this simple because you path geometry is trivial (i.e. a straight line), but it works just fine.

This has the added advantage of working when the target is faster than you describe as well, so long as both tracks are straight (or at least gently curving).

Limitation, you step size needs to be small compared to the "size" of the explosion, or this won't work right. In that case, you would need to precompute the next distance...

---

Related Topics