Finding the Center of Two Points in Latitude/Longitude Form

Date: 08/11/2006 at 07:02:46
From: Sam
Subject: Center Of Two Latitude Points

Hi,

How can I calculate the center (expressed as a latitude value) of two 
latitude points?  I want to find the center of a rectangle expressed 
in longitude and latitude.  The rectangle is defined by the upper left 
and bottom right corners (both represented as lat/lon locations).  
Basically I need to find the midpoint or center between these two 
points.

The reason I want to find the center is so that I can divide the area
into four smaller sub-areas.  Each new sub-area can be defined using
one of the original corners and the center (if we are going to define
it using two locations).  I know the four sub-areas won't be equal
because of the convergence of latitude lines, but that's ok.

I want to be able to divide the Earth up like this in order to perform
efficient proximity searches.  Being able to place a location within
an area of the Earth means only other locations within that area and
certain surrounding areas need to have Haversine applied to find their
distance and is therefore much less computationally heavy. 

The ability to start off with large areas and then divide them into
smaller areas is needed so that a larger area can be queried when a
surrounding location is sparsely populated.  The areas are divided and
re-populated whenever one becomes occupied with a certain amount of
locations. 

I plan to start by dividing the Earth into four equal areas.  This
time they will be equal as it's simple to do this with a sphere and
latitude/longitude, but I'm not sure where to go from there.  Any help
would be greatly appreciated.  Thanks a lot.

Date: 08/11/2006 at 13:33:40
From: Doctor Rick
Subject: Re: Center Of Two Latitude Points

Hi Sam,

Here are two exchanges in the Dr. Math Archive concerning the related 
concept of a "spherical rectangle".  These pages won't answer your 
question, but will give you some background information:

  Spherical "Rectangles"
    http://mathforum.org/library/drmath/view/60748.html 

  Area of a Latitude-Longitude Rectangle
    http://mathforum.org/library/drmath/view/63767.html 

You are interested in "latitude-longitude rectangles"; they don't have
to be squares (equal sides).  I don't think you need a lot of 
precision, but dividing the LLrectangle into four LLrectangles of 
equal area will fit your need well.

Going to the last page I referred you to, I get the formula

  A = (pi/180)R^2 |sin(lat1)-sin(lat2)| |lon1-lon2|

where R is the radius of the earth (which won't matter to us since 
we're working with ratios), lat1 and lat2 are the latitudes of the 
top and bottom of the LLrectangle, and lon1 and lon2 are the 
longitudes of the sides.

The longitude of the vertical dividing line is easy ... well, almost.
We can just take the average of lon1 and lon2, *unless* the 
LLrectangle spans longitude 180 (assuming you're working with 
longitudes from -180 to +180).  We can recognize that case because the
difference |lon2-lon1| will be greater than 180 degrees.  The
algorithm for the dividing longitude is

  lon = (lon1+lon2)/2
  if |lon2-lon1| > 180 then
    if lon > 0
      then lon = lon - 180
      else lon = lon + 180

or equivalent.  If you have set things up so that no LLrectangle will 
cross over longitude 180, you only need the first line.

To find the latitude of the horizontal dividing line, we look for 
lat such that the area from lat1 to lat equals the area from lat to 
lat2:

  (pi/180)R^2 |sin(lat1)-sin(lat)| |lon1-lon2| =
  (pi/180)R^2 |sin(lat)-sin(lat2)| |lon1-lon2|

which can be simplified to

  |sin(lat1)-sin(lat)| = |sin(lat)-sin(lat2)|

If we can assume that lat1 and lat2 are in the same hemisphere (both 
positive or both negative), then lat will obviously have the same 
sign, and we can simplify to

  sin(lat1)-sin(lat) = sin(lat)-sin(lat2)
  sin(lat1) + sin(lat2) = 2sin(lat)
  lat = arcsin((sin(lat1) + sin(lat2))/2)

My instinct is to divide the earth into eight octants to start with; 
this will result in regions that are more "square" in some sense. 
First divide the earth into positive and negative longitudes (thus 
simplifying the lon calculation), then start applying the divide-
into-four-regions algorithm to divide each hemisphere. (The latitude 
division formula will work in this case even though lat1 and lat2 
have different signs.)

- Doctor Rick, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 08/12/2006 at 11:58:35
From: Sam
Subject: Thank you (Center Of Two Latitude Points)

Thank you so much for the help with this problem.  As you suggested I
did plan to make the original divisions at longitude 180.  I will also
make eight original divisions as you suggested.  Thanks again for
your help, I was amazed at the speed of your response and the effort
you put in.

-Sam