Mastering Algorithms With C - Kyle Loudon [220]
Figure 17.6. Locating the point (5, 30, 45) in a spherical coordinate system
Converting Between Coordinate Systems
When speaking about an arc on a spherical surface, it is often convenient to have its endpoints specified in spherical coordinates. Therefore, the algorithm presented here assumes this representation to begin with. However, to compute an arc's length, we will need its endpoints in rectilinear coordinates. Consequently, the first step is to convert the points p 1 = (ρ , θ 1, φ 1) and p 2 = (ρ , θ 2, φ 2) to the rectilinear equivalents p 1 = (x 1, y 1, z 1) and p 2 = (x 2, y 2, z 2). To do this, we start with the following equations. Of course, the locations of the points do not change, only their representations.
Another relationship between ρ and the rectilinear coordinates x, y, and z is:
This formula calculates the distance from a point to the origin in three dimensions.
Computing the Length of an Arc
Now we are ready to compute the length of the arc between p 1 and p 2 on the sphere. First, we picture two imaginary lines extending from the center of the sphere to each of the points (see Figure 17.7a) and calculate α , the angle between them. To do this, we use the formula:
where cos -1 is the inverse cosine of the argument in parentheses. Think of an inverse cosine this way: the cosine of what angle gives us the value of the argument in parentheses? The expression in the numerator of the argument comes from treating the imaginary line segments from the center of the sphere to p 1 and p 2 as vectors U and V (see the related topics at the end of the chapter) and computing the dot product U ⋅ V.
Figure 17.7. The length of an arc as viewed (a) on a sphere and (b) in the plane containing the lines from the center of the sphere to each point
The lines that form α lie in a plane that slices across the sphere. The importance of α is that where the sphere and this plane intersect, a circle is projected onto the plane with the same radius as the sphere (see Figure 17.7b). Since the arc between points p 1 and p 2 lies along a section of this circle, α helps to determine how much of the circle's perimeter the arc covers. This is determined from the percentage α/2π, since there are 2π radians in a circle. Using this and the circumference of the circle, 2πρ, we see that the length s of the arc between p 1 and p 2 is (α/2π)(2πρ), which simplifies to the equation that follows. This is the equation that is used in the implementation presented later:
Interface for Arc Length on Spherical Surfaces
Name
arclen
Synopsis
void arclen(SPoint p1, SPoint p2, double *length)
Return Value
None.
Description
Computes the length of an arc between points p1 and p2 on a spherical surface. Each point is a structure of type Spoint, a point in spherical coordinates. Specify the radius of the sphere as the rho member of each SPoint structure. Specify the theta and phi members of each SPoint structure in radians. The length of the arc is returned in length.
Complexity
O (1)
Implementation and Analysis of Arc Length on Spherical Surfaces
To compute the length of an arc on a spherical surface, we first must have a way to define the arc's endpoints. For this, arclen accepts the two points p1 and p2. Each endpoint is an SPoint structure. This structure consists of three members, rho, theta, and phi, which are the spherical coordinates for a point expressed in radian measure.
The arclen operation (see Example 17.4) begins by converting spherical coordinates into rectilinear coordinates using the equations presented earlier. Recall that this allows us to calculate the angle between the lines extending from the center of the sphere to either point on its surface.