Extract nearest point index from a linestring to a given point?

Question

Let's consider a linestring as a list of points, I named it trail. I need to detect which point is close enough to this trail. I have another linestring called interest points, which I need to return the closest index point from trail linestring. I want to mention that these interest points are not included in trail linestring, so I will somehow evaluate the index point in this trail by giving that interest point. The resulted interest point will get the value existing in the trail list.

[EDIT]:

I will convert this problem using plain numbers. I find that is easy.

Input list [0.5, 1, 1.5, 2, 2.5, 3, 3.5, 4, 4.5, 5]. Input number: 3.30

I can easly see that conditon: list[n] < number < list[n+1] Then I can check the costs:

cost1 = number - list[n] cost2 = list[n+1] - number.

Then I can get the index of N if (cost1 < cost2) return N else return N+1.

[IMPORTANT]:

Point objects are not comparable as numbers, this drive me to a blind spot.

Answer 1

If you only need to do this once, or speed is not really important, and your trace doesn't tend to loop back on itself so that detecting the closest two points could differ from detecting the line segment between them, then it's pretty easy.

First, you need a distance squared formula for points (this takes the place of the difference of plain numbers):

 def dSq(x0: Double, y0: Double, x1: Double, y1: Double) =
   (x1 - x0)*(x1 - x0) + (y1 - y0)*(y1 - y0)

Note that you have no real advantage for using plain distance over distance squared, except that you have to calculate an extra square root. (But feel free to def d(...) = sqrt(dSq(...)) and use that instead.)

Now you find the distances from your trace to your target point:

 val ds = trace.map(p => dSq(target.x, target.y, p.x, p.y))

And you find the distances between pairs of points:

 val pairDs = ds.sliding(2).map(xx => xx(0) + xx(1))

And you find the index of the smallest of these:

 val smallest = pairDs.min
 val index = pairDs.indexWhere(_ == smallest)

Then in your original list, the two points are index and index+1.

Alternatively, you could find the closest single point and then decide whether you want the next or previous one by comparing the distances to those. (Again, note that all of these are inexact--to really do it right you have to compute the point of closest approach of the point to the line segment between two points, which is a longer formula.)

If you have to do this a lot, then you'll want to have a faster way to ignore big distances that aren't relevant. One common way is to place a grid over your trace, and then make subtraces inside each grid element. Then, when given a point of interest, you first look up its grid location, then do the same searching trick just inside the grid. (You may need to search the 8 adjacent neighbors also depending on how you clip the points inside the grid.)