[OSM-dev] Nearest way for a location

[andrzej zaborowski]

On 2 July 2010 08:52, Stephan Plepelits <skunk at xover.htu.tuwien.ac.at> wrote:
> 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.

An easier way to find out whether G is on the left or right side of AB
is to take the sign of z coordinate of BA x AG, it ends up being
something like BA_x * AG_y > BA_y * AG_x => we're on the left side.
Then you can check wheter your "t" is in [ 0, 1 ], by making sure that
| AG | and | BG | < | u + AB |.

There was also some really short formula for point to line distance,
but note that all of this assumes your coordinates are in mercator
already (or some approximation, there's a really quick approximation
you can use where you just multiply all latitudes by cosine of your
approximate latitude)

Cheers