Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

I have three points in geographic coordinates (latitude, longitude, altitude). One of the points represents an observer, above the Earth. The other two points define a bounding box. I'd like a somewhat efficient way to determine the minimum and maximum straight-line distance between the observer and the edges of the bounding box. I'm concerned with performance over accuracy, so I'm okay with using the spherical model of the Earth for speed gains. Please see the image for a stunning rendition of the aforementioned scenario.

pic

share|improve this question
    
How big is the bounding box (meters, km, 1000's km)? –  TreyA Mar 12 '12 at 12:20
    
It can be 1000's km. The max bounding box is lat(+-90) and lon(+-90) (since an observer can't see past the horizon). The only way I've been able to do this so far is to convert everything to ECEF and use straight line distances. I'm sure this introduces some error, but it seems okay. I'm more concerned with finding a faster way to do it, but I'm not so sure it's possible to do much faster. –  Pris Mar 12 '12 at 14:19

2 Answers 2

up vote 1 down vote accepted

Hi I am not sure how to use GIS for this. But since you said you need speed, you can do some math yourself. You have a point P in space and you have coordinates of that point. You can assume a sphere centered at earth's center. You get P(x1,y1) in space.

Now, in the BB, which is not a box in fact since you got to see the curvature. So a surface which is bound by (Θ1,Θ2) and (φ1,φ2). The point on this surface is Q(x,y) which is actually (rcosΘcosφ ,rcosΘsinφ), r being the average radius of your patch.

Now, d = sqrt( (x1-x)^2 + (y1-y)^2 ) is your optimization objective function.

with the above stated conditions, find maxima and minima of d. You can infact use MATLAB do solve for the min and max values of d.

Have fun. N

share|improve this answer
    
This seems like the cheapest way to do it if I want to maintain the spheroid model. Thanks. –  Pris Mar 12 '12 at 15:27

The "bounding box" can have several interpretations. The two most natural are (a) the sides are meridians and the top and bottom are circles of constant latitude and (b) the sides are still meridians, but now the top and bottom are geodesics (which therefore do not necessarily have constant latitude). Fortunately, the solution method is the same in both interpretations, because in all cases the sides are portions of circles. This reduces the problem to optimizing the distance between a fixed point x and an arc of a circle (in three dimensions). Do this for each of the four sides and retain the best results.

A simple way to represent the arc of a circle is to choose coordinates for x in which the circle's center is at the origin, the circle is determined by two vectors e and f of equal length (say, r) and at right angles to each other, and the arc is given by all points of the form cos(q) * e + sin(q) * f for angles q ranging from q0 through q1. Critical points for the optima occur either at the endpoints of the arc or where the tangent vector is perpendicular to the direction vector. The latter tells us the inner product of x - (cos(q) * e + sin(q) * f) with (-sin(q) * e + cos(q) * f) is zero. This easily reduces to the equation

tan(q) = -xe / xf

where xe is the inner product of x with e and xf is the inner product of x with f. There will usually be two solutions (differing by 180 degrees). Use ATan (or its equivalent) to find them. Any of these solutions that lies in the interval [q0, q1] is a critical point.

In this fashion you collect (in most cases) up to two critical points per side plus the four vertices of the bounding box: that gives between 4 and 12 distance calculations to make in order to find the largest and smallest distance. These are 3D (Pythagorean) distances: compute them using the Pythagorean formula, but don't bother to take square roots when comparing; just take square roots for the largest and smallest distances.

Figure

Portions of the four circles determined by the sides of this bounding box are shown in gray. The arcs of latitude are in red and the arcs of the meridians are in blue.

There is a notable exception to this nice situation: x might lie on, or extremely close to, the axis of the circle. In this case, every point along the circle (and therefore every point along the arc) has the same distance to x. Make sure to check for this situation. It's easy to detect: both xf and xe are zero (or extremely small compared to x itself).

It remains, then, to describe how to find e, f, q0, and q1. That's easy:

  1. For a meridian at longitude lambda, the circle's center is already at (0,0,0), so don't change the coordinates of x (which presumably is referenced to a geocentric system). Take e = (R*cos(lambda), R*sin(lambda), 0) and f = (0,0,R) where R is the earth's radius (in a spherical model). Here, q0 will be the minimum latitude among the bounding box coordinates and q1 will be the maximum latitude.

  2. For a circle of latitude phi, take the center to be (0, 0, R*sin(phi)). Subtract these coordinates from x. In these new coordinates, we can let e = (R*cos(phi), 0, 0) and f = (0, R*cos(phi), 0). Now q0 is the westernmost longitude and q1 is the easternmost longitude in the bounding box.

  3. Equations for e, f, q0, and q1 are more complicated for arbitrary geodesics (case (b) in the first paragraph). Because it is not apparent these are needed, I won't derive them here.

In summary,

  • Only simple calculations are needed to establish the 3D coordinate representation of x, e, f and to find q0 and q1. (This is all done four times, once for each side of the bounding box.)

  • Four arctangent calculations will determine between 0 and 8 critical points. At this time, you can inspect xe and xf (four times) to check whether any of the sides of the bounding box are equidistant from x. (You will have to decide how such a situation is to be handled).

  • Squared pythagorean distances (sums of squares) have to be determined between x and the four corners of the bounding box plus these other critical points. Take the square roots of the min and max of these distances.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.