[OSM-dev] Nearest way for a location

[Stephan Plepelits]

On Mon, Jun 28, 2010 at 12:06:04PM -0400, Matthias Julius wrote:
> Stephan Plepelits <skunk at xover.htu.tuwien.ac.at> writes:
> 
> > On Sun, Jun 27, 2010 at 07:11:53PM -0500, Nolan Darilek wrote:
> >> 3. In dusting off my disused (and never that good to begin with :) math
> >> skills from over a decade in my past, I'm thinking that a vector-based
> >> solution might work. I am already calculating a node's neighbors if it
> >> is on one or more ways, so I think that if I create vectors between the
> >> nearest node and each of its neighbors, then determine which segment has
> >> the least distance to the user's current location, then I've figured out
> >> the user's new way with minimal complexity. Before I go off and
> >> implement this (or rather, before I figure out which vector operations
> >> apply here and *then* implement this :) can anyone tell me why this may
> >> be a bad idea?
> > I think this is a very good idea :) Check out the "Hesse normal form"[5] how
> > to calculate the distance of a point to a line.
> The nearest road does not need to have a node near your location.
Yes, that's why I told you to calculate the distance to the line.
Your position is the point, and the line is the road segment.

Example:

  Your coordinates (G): (2, 3)
  Your road segment (AB): (1, 1) -> (4, 5)

  Therefore you get:
  Function for all points on AB: (1, 1) + t*(3, 4)   (for 0<=t<=1)
  Normal vector to AB (n): (-4, 3)
  Unified normal vector to AB (n0): (-4/5, 3/5) = (-0.8, 0.6)


You can use the hesse normal form to calculate the distance (which is the
easier solution):

  Hesse normal form: n0 * (X - A)       (for X is any point on AB)
  Our Hesse normal form of that line: (-0.8, 0.6) * (X - (1, 1)) = 0

  Distance form: | AG * n0 |     ( * being a scalar product )
  Our distance: | (1, 2) * (-0.8, 0.6) | = | -0.8 + 1.2 |

-> distance: 0.4

Voila. Problem: We don't know, if we are on the right part of the road (the
line is assumed to be infinite). Therefore we need another approach:

  We have to lines:
  AB (1, 1) + t*(3, 4)         (for 0<=t<=1)
  GX (2, 3) + u*(-0.8, 0.6)    (for any u, |u| is our distance)
  X is the point where GX crosses AB, say the nearest point to G on AB.

  If we intersect these vectors we will get the point X:
  (1, 1) + t*(3, 4) = (2, 3) + u*(-0.8, 0.6)

  We get two equations:
  1 + t*3 = 2 + u*-0.8
  1 + t*4 = 3 + u* 0.6

  Now we can solve this system of equations and get
  t= 0.44
  u=-0.4

-> t is between 0 and 1, so G is near AB
-> X is (2.32, 2.76)
-> distance is 0.4

greetings,
        Stephan
-- 
Seid unbequem, seid Sand, nicht Öl im Getriebe der Welt! - Günther Eich
,---------------------------------------------------------------------.
| Stephan Plepelits,                                                  |
| Technische Universität Wien   -    Studien Informatik & Raumplanung |
| Projects:                                                           |
| > openstreetbrowser.org > couchsurfing.org > tubasis.at > bl.mud.at |
| Contact:                                                            |
| > Mail: skunk at xover.mud.at > Blog: plepe.at > Jabber: skunk at fsinf.at|
| > Twitter: twitter.com/plepe > Wave: plepelits at googlewave.com       |
`---------------------------------------------------------------------'