[OSM-dev] Nearest way for a location
balrogg at gmail.com
Sun Jul 4 01:27:38 BST 2010
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" 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.
> 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
More information about the dev