Shortest distance from a point to a line

[neros]

... on a sphere. Ok, so this isn't really a homework question (I haven't done homework in years), but rather is a problem I've been trying to figure out for the last few hours for a programming issue I have run into. So if this is the wrong forum, feel free to move it (and I apologize).

Basically, picture a sphere of radius r. Along the surface of the sphere, there is a line segment AB (a "great circle" in navigation terms) which goes from (r, A_theta, A_phi) to (r, B_theta, B_phi) (in spherical coordinates).

Next, there is a point on the surface of the sphere, C (r, C_theta, C_phi). I am trying to determine the shortest distance from C to the line segment, traveling along the surface of the sphere. If this was a line segment in rectangular coordinates, I would solve for a point P, along the line AB, where CP dot AB = 0, and determine of the point is inside of the segment AB, or if it is off one of the two end points.

That being said, I have no idea how to do this for the surface of a sphere. I have thought about trying to "unwrap" the space, but this would leave me with a curve to find the distance to, and because spherical coordinates are not orthogonal, one can't use a dot product. Any ideas would be greatly appreciated.

 

[AlephZero]

Any great circle on a sphere lies in a plane passing through the centre of the sphere.

The shortest distance along the sphere between C and P is also part of a great circle. (Because a great circle is the shortest distance between two points on the sphere, by definition.)

Think about the angle between the planes containing the two great circles.

 

[belliott4488]

Did that work for you, neros?

AlephZero is quite right - if you draw your problem, including the radial lines to your three points and the planes that contain them, you can work out the geometry and get your answer. Let us know if you're still unsure about it.

 

[barty]

I, too, have the same question. Could you please elaborate a bit? I have a need to determine if any part of a great circle arc lies within the bounds of a circle (small circle?) drawn on a sphere with radius R.

Thanks.

 

[belliott4488]

I, too, have the same question. Could you please elaborate a bit? I have a need to determine if any part of a great circle arc lies within the bounds of a circle (small circle?) drawn on a sphere with radius R.

Thanks.

That sounds like a different question. Neros was asking about the intersection of two great circles, which involves the intersection of the two planes containing them, each of which must contain the center of the sphere. Your question seems to involve a plane that does not necessarily contain the center of the sphere, i.e. the plane of the "small circle" you refer to.

So, how much do you know about the two circles in question? If you can determine where their respective planes intersect, that will answer your question.

 

[barty]

Thanks for the quick response belliott4488.

I am looking for the simplest way to determine if a "spherical polygon", with points A, B, C, D, overlaps a "small circle" (not great) with center point C and radius R.

I was thinking this could be done by finding the shortest distance between the circles center point C and each of the great circle arcs made by the polygon: A-B, B-C, C-D, D-A. A simple test of 'Distance <= Radius' would then indicate if any of the sides of the polygon do intersect with the circle.

Note: All coordinates are geographic and converted to radians, as is the circles radius.

Does that even make sense? Maybe there is a better way. My trig skills are very rusty...maybe it is possible this could be solved via linear algebra?

 

[belliott4488]

Yes, that makes sense, and I now see the connection with the OP's question.

Here's what you need to think about:

You're looking for a general way to find the distance (meaning arc of a great circle) between a point and a line (meaning another arc of a great circle). Well, just as the shortest distance from a point to a line on a plane lies on a perpendicular to the line, the shortest arc in this case will be in a plane perpendicular to the plane of the given arc. Make sure that this makes sense to you; drawing it is even better, if you can.

Now, what's the distance? Well, you really want the angle subtended at the center by the arc (assuming you know the radius of the sphere). The given arc defines a plane, and you want the angle between this plane and the radial line to your point. It might not be obvious how to calculate this, but consider this instead: this angle is simply the complement of the angle between that radial line and the line perpendicular to the plane of the arc, drawn through the center of the sphere. Get that angle, and you're all set.

So, how do you get the line perpendicular to the plane? Well, that depends on the form you have for the location of the arc (or its endpoints, in the case of your polygon). If you can convert those points to Cartesian coordinates, however (such as the E,F,G coordinates often used for Earth-fixed reference system, since you're dealing with geographic locations), then yes, it does come down to some linear algebra.

Remember that the cross-product of two vectors gives you a vector perpendicular to the plane containing them, and the dot product can be used to get the angle between them. If you can write down vectors for all three of your points, i.e. the single point and the endpoints of the arc, then you should be all set.

HTH,
Bruce

 

[barty]

Thanks, Bruce!

I think I have it, but I am getting strange results for certain points. It appears as though the arc created by points A & B of a polygon side continue infinitely.

Here are my steps:

Vectors A & B define two points making-up a side (great circle arc) of a polygon. Vector P is the center point of the circle.

1. Calculate the cross product of vectors A & B to get a perpendicular plane
2. Normalize the vector created in step #1: Normal _AB
3. Normalize vector P: Normal_P
4. Calculate the dot product of the normal vectors Normal_AB and Normal_P to get the angle, in radians, between the two vectors
5. Multiply the dot product by the radius of the Earth. This is the difference.

When I say that the arc appears to continue infinitely I mean it does not appear to be bound by its endpoints. The distances being returned from points P (center of the circle) far east or west (geographically) of the line in question are consistent with the line continuing infinitely around the sphere. Would this behavior be expected?

I have been checking the results against the maps on Google Earth and they appear to be quite accurate. So, I can't be too far off. I'm just stuck with this "infinite" great circle arc

Thanks, again,

Barty

 

[belliott4488]

1. Calculate the cross product of vectors A & B to get a perpendicular plane

You mean "to get a perpendicular vector", right? i.e. perpendicular to the plane of A and B.

2. Normalize the vector created in step #1: Normal _AB
3. Normalize vector P: Normal_P
4. Calculate the dot product of the normal vectors Normal_AB and Normal_P to get the angle, in radians, between the two vectors

This is right, but remember that this is not the angle that you need to get your distance - that angle is the complement of (90 deg. minus) this angle.

5. Multiply the dot product by the radius of the Earth. This is the difference.

This could be a problem if it's literally what you're doing. The dot product of the normalized vectors gives you not the angle, but the cosine of the angle. You need to use arccos(dot product), i.e. inverse of the cosine, to get the angle.

When I say that the arc appears to continue infinitely I mean it does not appear to be bound by its endpoints. The distances being returned from points P (center of the circle) far east or west (geographically) of the line in question are consistent with the line continuing infinitely around the sphere. Would this behavior be expected?

I have been checking the results against the maps on Google Earth and they appear to be quite accurate. So, I can't be too far off. I'm just stuck with this "infinite" great circle arc

Sorry, I'm not following what's going on when you the arc "continues infinitely". I thought you just had three points, A, B and P (so far - I know there are other sides to the polygon, but they haven't entered this calculation yet, right?). Where is there a new arc being constructed?

One place you could run into trouble is if any of these points are more than 180 degrees apart. In that case some of the angles in question will be on the "wrong" side. You can handle this if you are just very careful with the signs of your cross and dot products. For example, A X B points in the opposite direction if A and B are more than 180 apart than if they are less than 180 apart. You'll also get in trouble right at 180 degrees (diametrically opposite points), where the direction of the cross product is not defined.

I don't know if your problems are related to any of that, however.

 

[blaze985]

Hi,

I have same problem: Want to found if point on a surface of sphere is inside a bounding polygon...for a simplicity we can say is a rectangle...

And englesh is not my native language, so reading all your post make me understend how bad is my math english...

I calculate this for a circle on the sphere(if a point is insade the circle) basiclly I calculate all posible point given from minLat and min Lng to maxLat and maxLng
this is my programming code:
distance = radius of circle
latPoint1, lngPoint1 (center of the circle)

MIN_LAT = Math.toRadians(-90d); // -PI/2
MAX_LAT = Math.toRadians(90d); // PI/2
MIN_LON = Math.toRadians(-180d); // -PI*2
MAX_LON = Math.toRadians(180d); // PI*2

// angular distance in radians on a great circle
double radDist = distance / EARTH_RADIUS;

double minLat = Math.toRadians(latPoint1) - radDist;
double maxLat = Math.toRadians(latPoint1) + radDist;

double minLon, maxLon;
if (minLat > MIN_LAT && maxLat < MAX_LAT) {
double deltaLon = Math.asin(Math.sin(radDist) /
Math.cos(Math.toRadians(latPoint1)));
minLon = Math.toRadians(lngPoint1) - deltaLon;
if (minLon < MIN_LON) minLon += 2d * Math.PI;
maxLon = Math.toRadians(lngPoint1) + deltaLon;
if (maxLon > MAX_LON) maxLon -= 2d * Math.PI;
} else {
// a pole is within the distance
minLat = Math.max(minLat, MIN_LAT);
maxLat = Math.min(maxLat, MAX_LAT);
minLon = MIN_LON;
maxLon = MAX_LON;
}

its take in care for the specific position of 180degrees..and so on...

but still have problems to calculate for other shape...:S

Any help, maybe someone already solve it...?!:)