0

Suppose I have an ordered array containing points (lat, lon) describing a path, and I also have a point (lat, lon) describing my current location.

How can I project the point onto the path (and place the point in the appropriate place in the array)?

What I tried is just simply by searching for the nearest two points and assume it's in the middle of them. It's a good guess, but sometimes fails.

What would be a good way of doing this?

Derek 朕會功夫
  • 92,235
  • 44
  • 185
  • 247
  • possible duplicate of [Find a point in a polyline which is closest to a latlng](http://stackoverflow.com/questions/16429562/find-a-point-in-a-polyline-which-is-closest-to-a-latlng) – r3mainer Jun 18 '15 at 21:23

2 Answers2

1

I see it like this:

line segment overview

  • p0,p1 are path line segment endpoints
  • p is your position
  • q' closest point on line in 3D cartessian
  • q is q' corrected by spherical projection

So:

  1. convert points to 3D cartessian coordinates

  2. compute perpendicular distance from point and line

    • q'=p0+(dot(p-p0,p1-p0)*(p1-p0)/(|p-p0|*|p1-p0|))
    • perpendicular_distance = |p-q'|

  3. find segment with smallest perpendicular_distance

    and use only it for the rest of bullets

  4. compute q

    If you use sphere instead of ellipsoid then you already know the radius if not then either compute the radius algebraically or use average:

    r=0.5*(|p0-(0,0,0)|+|p1-(0,0,0)|)

    assuming (0,0,0) is Earth's center. You can also be more precise if you weight by position:

    w=|q'-p0|/|p1-p0|
r=(1-w)*|p0-(0,0,0)|+w*|p1-(0,0,0)|

    now just correct the position of q'

    q=q'*r/|q'|

    set vector q' as q with size r if it is not obvious enough. Also |p0-(0,0,0)|=|p0| obviously but I wanted to be sure you get how I got it ...

  5. convert q from Cartesian to spherical coordinates

[Notes]

  • |a| is size of vector a done like: |a|=sqrt(ax*ax+ay*ay+az*az)

  • dot(a,b) is dot product of vectors a,b done like: dot(a,b)=(a.b)=ax*bx+ay*by+az*bz

    if your path is not too complex shaped then you can use binary search to find the closest segment. For distance comparison you do not need the sqrt ...

Spektre
  • 49,595
  • 11
  • 110
  • 380
0

Find the path segment which is closest to the current position.

Distance from point to a line

gen-y-s
  • 871
  • 6
  • 12
  • Thanks, but lat, lon are not Euclidean geometry and I'm trying to project it onto the path segment. – Derek 朕會功夫 Jun 18 '15 at 21:00
  • If the line passes through two points P1=(x1,y1) and P2=(x2,y2) then the distance of (x0,y0) from the line is abs((y2-y1)*x0-(x2-x1)*y0+x2*y1-y2*x1)/sqrt((y2-y1)*(y2-y1)+(x2-x1)*(x2-x1)) – gen-y-s Jun 18 '15 at 21:19
  • Latitude and longitude (spherical coordinates on a 3D sphere surface) are not the same as the 2D Euclidean coordinates. – Derek 朕會功夫 Jun 18 '15 at 21:25
  • It should be close enough, and much better than searching for the nearest two (adjacent?) points, like you tried. – gen-y-s Jun 18 '15 at 21:36
  • @Derek朕會功夫 Check out [this demo](http://wtp2.appspot.com/cSnapToRouteDemo.html) (linked from the accepted answer of he question I mentioned above). The point snapping is done by the function `getClosestPointOnLines()` in [this javascript file](http://wtp2.appspot.com/cSnapToRoute.js). The calculations are all done in 2D. – r3mainer Jun 18 '15 at 21:40