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.
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: sk...@xover.mud.at > Blog: plepe.at > Jabber: sk...@fsinf.at|
| > Twitter: twitter.com/plepe > Wave: plepel...@googlewave.com |
`---------------------------------------------------------------------'
_______________________________________________
dev mailing list
dev@openstreetmap.org
http://lists.openstreetmap.org/listinfo/dev
