On 2 July 2010 08:52, Stephan Plepelits <sk...@xover.htu.tuwien.ac.at> wrote: > On Mon, Jun 28, 2010 at 12:06:04PM -0400, Matthias Julius wrote: >> Stephan Plepelits <sk...@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 _______________________________________________ dev mailing list dev@openstreetmap.org http://lists.openstreetmap.org/listinfo/dev
