Geometry: distance to line

[mjcoon]

My question is related to a Basic4PPC project but is really about geometry.

I am extending GPS4PPC to have much of the functionality of my ancient (and deteriorating) Garmin GPS-II+. Including having a "route" of several "legs" to navigate in succession. The screen-shot shows an example, taken from a holiday to Croatia in 2005. (The data can be exchanged via GPX or KML files.)

The Garmin manual says that the leg being navigated is chosen as the nearest one from the full set in the route. This should result in navigating them in the right order but not having to sail exactly to each waypoint that marks the join of leg to leg.

So the geometry puzzle is how to measure the distance to a line. Not to the infinite line defined by two points but the finite line between those points. Anyone know, or how to find, the algorithm?

TIA, Mike.

 

[klaus]

Here you are:

[FONT=Courier New][SIZE=2][FONT=Courier New][SIZE=2]a=yb-ya[/SIZE][/FONT]
[SIZE=2][FONT=Courier New]b=xa-xb[/FONT][/SIZE]
[SIZE=2][FONT=Courier New]c=-a*xa-b*ya[/FONT][/SIZE]
[SIZE=2][FONT=Courier New]d=[/FONT][/SIZE][/SIZE][/FONT][FONT=Courier New][SIZE=2][FONT=Courier New][SIZE=2](a*x+b*y+c)/[/SIZE][/FONT][/SIZE][/FONT][FONT=Courier New][SIZE=2][COLOR=#0000ff][FONT=Courier New][SIZE=2][COLOR=#0000ff][FONT=Courier New][SIZE=2][COLOR=#0000ff]Sqrt[/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][FONT=Courier New][SIZE=2][FONT=Courier New][SIZE=2](a*a+b*b)[/SIZE][/FONT][/SIZE][/FONT]

xa,ya coordinates of point a on the line
xb,yb coordinates of point b on the line
x,y coordinates of the point
a,b,c intermediate variables
d distance from point to line.

The sign of the distance determines on which side of the line the point lays. Looking from point 'a' to point 'b' all points with a positive distance lay on the left side of the line and all points with a negative distance lay on the right side.

Attached a small test program.

Best regards.

 

[mjcoon]

Thanks very much, Klaus, my money was on getting a good answer from you!

But I think you fell into the trap of extending the line infinitely, as a bit of experimentation with your test program confirms. That would give wrong answers in my usage, because a route leg a long way away might happen to extend near the current position.

But I did find an answer to a related (but slightly more complex) question here. I think that will allow me to extend your code and try out an algorithm that includes measuring the distance from the nearer endpoint if the normal from the query point to the line is outside its limits.

Cheers, Mike.

 

[klaus]

Hi Mike,
Sorry for having fallen into the trap.
Fortunately I came out of it.

Attached you find what you asked for.
There is a problem with the transparent drawing, I havent found out yet why, but the equations are OK

Best regards.

 

[mjcoon]

Attached you find what you asked for.

Thank you very much Klaus; useful and rather beautiful too!

I shall incorporate it soon...

Cheers, Mike.

 

[klaus]

Hi Mike,
Attached the program without the transparent drawing problem.
Less beautiful, but more explanatory.

Best regards.

 

[mjcoon]

Less beautiful, but more explanatory.

Thanks again; explanations are crucial!

I note that you check for the simplification of horizontal line.

Since choosing y/x as the arbitrary definition of slope gives zero for horizontal it will give infinity for vertical, so that simple case will also have to be tested for.

Fortunately the lines are fixed and the point moves around, so much of the calculation can be done just once for each route.

Similarly I merely need to know the shortest distance amongst the various legs, so I won't need to do the square root at all.

Best wishes, Mike.

 

[klaus]

Hi Mike.

Since choosing y/x as the arbitrary definition of slope gives zero for horizontal it will give infinity for vertical, so that simple case will also have to be tested for.

Shure, shouldn't have missed that one.
Attached the 'improved' version.

Best regards.

 

[mjcoon]

Thanks again, Klaus. Not only did that behave nicely but it also served as a very useful test-bed for my version with the pre-computed values.

Now I have it incorporated I can connect my old Garmin GPS, set it in "simulator" mode sailing through Croatian waters at 200 knots (!), and watch the actual waypoints we chose in 2005 clicking past in turn!

Cheers, Mike.