• Choose a category
• All
• Classic-Fiction

The runtime complexity of arclen is O (1) because all of the steps in computing the length of an arc on a spherical surface run in a constant amount of time.

Example 17.4. Implementation for Computing Arc Length on Spherical Surfaces

/*****************************************************************************

* *

* ------------------------------- arclen.c ------------------------------- *

* *

*****************************************************************************/

#include

#include "geometry.h"

/*****************************************************************************

* *

* -------------------------------- arclen -------------------------------- *

* *

*****************************************************************************/

void arclen(SPoint p1, SPoint p2, double *length) {

Point p1_rct,

p2_rct;

double alpha,

dot;

/*****************************************************************************

* *

* Convert the spherical coordinates to rectilinear coordinates. *

* *

*****************************************************************************/

p1_rct.x = p1.rho * sin(p1.phi) * cos(p1.theta);

p1_rct.y = p1.rho * sin(p1.phi) * sin(p1.theta);

p1_rct.z = p1.rho * cos(p1.phi);

p2_rct.x = p2.rho * sin(p2.phi) * cos(p2.theta);

p2_rct.y = p2.rho * sin(p2.phi) * sin(p2.theta);

p2_rct.z = p2.rho * cos(p2.phi);

/*****************************************************************************

* *

* Get the angle between the line segments from the origin to each point. *

* *

*****************************************************************************/

dot = (p1_rct.x * p2_rct.x) + (p1_rct.y * p2_rct.y) + (p1_rct.z * p2_rct.z);

alpha = acos(dot / pow(p1.rho, 2.0));

/*****************************************************************************

* *

* Compute the length of the arc along the spherical surface. *

* *

*****************************************************************************/

*length = alpha * p1.rho;

return;

}

Arc Length Example: Approximating Distances on Earth

One application of computing arc lengths on spherical surfaces is approximating distances between points on Earth. Sometimes these are called great-circle distances . Of course, the earth is not a perfect sphere but an ellipsoid slightly squatter from north to south than east to west. That is, if we were to orbit the earth along the prime meridian, we would find the distance traveled to be less than that of orbiting the earth along the equator. Still, treating the earth as a sphere usually gives reasonable approximations.

To compute the distance between two points on Earth, we first need a way to locate each point. In geography, points are usually located in terms of latitude and longitude . Latitudes sweep from at the equator to 90 degrees at either pole. For points north of the equator, the letter "N" is appended to the latitude, and for points south, an "S" is appended. Often, degrees north of the equator are thought of as positive and degrees south of the equator as negative. Longitudes sweep from at the prime meridian to 180 degrees in either direction. For points to the west of the prime meridian, the letter "W" is appended to the longitude, and for points to the east, an "E" is appended. Often, degrees west of the prime meridian are thought of as positive and degrees east of the prime meridian as negative. For example, Paris is approximately 49.010 degrees to the north of the equator and 2.548 degrees to the east of the prime meridian. Therefore, its position is 49.010N, 2.548E, or 49.010, -2.548 (see Figure 17.8a).

To approximate the distance between two points on Earth given their latitude and longitude, we first translate each point into spherical coordinates and convert all angles from degrees to radians. Then, we simply compute the length of the arc between the points. Recall that a point in spherical coordinates is given by the triple