Perpendicular distance between point and line segment

[TheCelavi]

This library can calculate perpendicular distance between point and great circle passing trough two points.

It can calculate distance between two points.

What about a line segment? Perpendicular distance may not exists between point and line segment on great circle -> how to check that?

That can be useful when calculating minimum distance between point and line.

Thanks.

[TheCelavi]

Hello - does anyone knows answer to this question?

[mjaschen]

Hi, do you have an example?

[TheCelavi]

@mjaschen Is this good enough? https://docs.google.com/presentation/d/1qaP29PFlCZ5YqVSDJlj47QQgx3QbJXlRRn5OEFHICIo/edit?usp=sharing

In general - I am trying to calculate distance between two geo areas - and determining if perpendicular distance exists or not is crucial for that.

[mjaschen]

Thanks for clarification!

I wonder, if the following would be enough to calculate the minimum distance:

• try to calculate the perpendicular distance; if it exists: we've found the minimum distance and are done
• if the perpendicular distance cannot be determined, calculate the distance between the point and each of the two points of the line and return the smaller value

Edit: never mind, that won't work, a perpendicular distance can be calculated in any case (because the great circle is used instead of the line segment -- exactly as described by you), so the second item will never be executed.

[mjaschen]

I'm doing some research and will drop interesting links and ideas here:

• http://stackoverflow.com/questions/7803004/distance-from-point-to-line-on-earth#7804061
• http://www.movable-type.co.uk/scripts/latlong.html#cross-track

Some thoughts:

A simple iteration should lead us to the solution relatively fast:

Given are a point P and a line L consisting of two points P₁ and P₂.

Wanted is the shortes distance between P and the line between P₁ and P₂.

1. Calculate the middle of L: P₃
2. Calculate distance between P and P₁: D₁
3. Calculate distance between P and P₂: D₂
4. Calculate distance between P and P₃: D₃
5. If D₁ is equal to D₂ within a margin ε then D₃ must be the minimum distance between P and L. We're done in this case.
6. If D₁ is smaller than D₂, repeat the calculation with a new line between D₁ and D₃, else repeat the calculation with a new line between D₂ and D₃.

[TheCelavi]

"Never mind, that won't work, a perpendicular distance can be calculated in any case" -> correct.

"A simple iteration should lead us to the solution relatively fast" -> Idea is solid, however, I don't think that iterative approach is a good approach, and should be left as last resort -> if we can not came up with better solution.

Perpendicular distance is actually a intersection of two great circles, right? How about to find that intersection and check if it is on line segment? (slide 3: https://docs.google.com/presentation/d/1qaP29PFlCZ5YqVSDJlj47QQgx3QbJXlRRn5OEFHICIo/edit#slide=id.g213395627b_0_0)

EDIT: Bad idea, I think that it is hard to find out that, see next comment, I think angles are our friends...

[TheCelavi]

BTW - you can edit presentation, if you need to play around with dots and triangles....

When we are at triangles, note that when perpendicular distance exits, angle C - A - B is less or equal then 90 degrees, while when it does not exists, angle C - A - B is greater than 90 degrees. Is that helpful? If we have coordinates of triangle on great circle, can we calculate angle of triangle sides?

See slide 3.

[TheCelavi]

Follow up on idea in regards to angles of triangles: https://sites.math.washington.edu/~king/coursedir/m445w04/notes/vector/coord.html

"Angle between two circles: This angle is the dihedral angle between the planes of the circles and thus can be computed as the angle between normal vectors to the planes. Caution: The angle may be the exterior angle and thus the supplement of the disired angle."

So, we are looking for diangle: http://www.math.csi.cuny.edu/abhijit/623/spherical-triangle.pdf

http://planetmath.org/areaofasphericaltriangle

[TheCelavi]

@mjaschen Ok, seams that there is a simple solution to this problem: https://en.wikipedia.org/wiki/Spherical_trigonometry#Derivation_of_the_cosine_rule

According to given theory, based on coordinates (lat/long) of given points A,B,C of triangle on sphere, we can calculate angles between tow great circles by using formula given in image: https://wikimedia.org/api/rest_v1/media/math/render/svg/3e90f310761cde9b5eebfcfe615594edf89b8f78 and applying arccos function.

If this theory on slide 3 is correct: https://docs.google.com/presentation/d/1qaP29PFlCZ5YqVSDJlj47QQgx3QbJXlRRn5OEFHICIo/edit#slide=id.g213395627b_0_0 then it will be very easy to determine if perpendicular distance exists between a point and line segment on great circle -> we just have to calculate two angles and do a simple check.

Do you agree with proposed idea?

[TheCelavi]

@mjaschen Sorry, I am harassing you but I don't have sufficient knowledge in geometry and I do not know anyone other who has it to ask :)

[TheCelavi]

@mjaschen Hi, I am sorry to bother you, you obviously dont have time to deal with this. Is there any other maintainer with who I can talk about this?

I am willing to work on this and to submit a PR but I need some help and guidance... thanks.

[mjaschen]

Hi,

sorry for letting you wait - I'm a little busy these days.

I'm currently working on a proof-of-concept for you proposal. If it works we can merge it immediately :-)

Marcus

[TheCelavi]

Hi, whats up? Is there any update on this?

[felixveysseyre]

@TheCelavi, did you find a solution to your issue ?

[TheCelavi]

I stopped working on it, I got theory, @mjaschen said that he is going to code it, and I was not under pressure to finish this functionality for one of my side projects...

[felixveysseyre]

@mjaschen Is there any news concerning the implementation of this feature ?

[mjaschen]

@felixveysseyre Unfortunately not :-(

Much of other stuff (private + business) keeps me from investing some time into this issue at the moment.

[acidjazz]

@mjaschen one working existing similar function is distanceToLine here

[mjaschen]

Hi there,

we've finally implemented a solution for this!

Please check the documentation for an example on how to use this.