Mastering Algorithms With C - Kyle Loudon [223]
return -1;
/*****************************************************************************
* *
* Convert each latitude and longitude to spherical coordinates in radians *
* using the earth's radius for rho. *
* *
*****************************************************************************/
p1.rho = EARTH_RADIUS;
p1.theta = -1.0 * DEGTORAD(lon1);
p1.phi = (DEGTORAD(-1.0 * lat1)) + DEGTORAD(90.0);
p2.rho = EARTH_RADIUS;
p2.theta = -1.0 * DEGTORAD(lon2);
p2.phi = (DEGTORAD(-1.0 * lat2)) + DEGTORAD(90.0);
/*****************************************************************************
* *
* Compute the distance between the points. *
* *
*****************************************************************************/
arclen(p1, p2, d);
return 0;
}
Questions and Answers
Q: One application of geometric algorithms mentioned at the start of this chapter was determining whether the track of an object transgresses a restricted region. If we assume that the track we follow begins outside of the restricted region, a simple approach to this problem is to determine whether any line segment in the track intersects with any line segment defining the restricted region. What is the running time of this approach if we use the lint operation presented in this chapter?
A: The runtime complexity of this approach is O (nm), where n is the number of line segments in the track and m is the number of line segments defining the restricted region. This is because for each of the n line segments in the track, we call lint once for each of the m line segments in the restricted region. Since lint runs in a constant amount of time, the runtime complexity of the solution overall is O (nm).
Q: Determining the orientation of two points with respect to a third is an important part of the algorithms presented for determining whether line segments intersect and computing convex hulls. Formally, given points p 1 , p 2, and p 3, we determine the orientation of p 3 relative to p 2 with respect to p 1 by treating the line segments from p 1 to p 2 and p 1 to p 3 as vectors U and V. We then use the sign of the z-component of the cross product U × V as a gauge of orientation. What is the orientation of the points if we compute the cross product V × U? In other words, given a specific orientation of p 3 relative to p 2, what is the orientation of p 2 relative to p 3?
A: The answer to this question is a matter of perspective. Imagine two people facing forward in a room with a door behind them. Unless the two individuals line up perfectly with the door (one in front of the other), person A will see person B to his left, whereas person B will see person A to his right, and vice versa. The neat thing about cross products is that they reflect this perspective mathematically. When we compute the orientation of p 3 relative to p 2 with respect to p 1, we get an indication of where p 3 is from the perspective of p 2. For example, p 3 may be clockwise from p 2. When we compute the orientation of p 2 relative to p 3, we get an indication of where p 2 is from the perspective of p 3. These perspectives are always equal but opposite to one another (except in the boundary case when p 2 and p 3 form a straight line with p 1). That is, U × V is always equal to but of opposite sign as V × U (if p 2 and p 3 form a straight line with p 1, U × V and V × U are both 0, and the line segments from p 1 to p 2 and p 1 to p 3 are collinear). The formula given earlier in the chapter for z 1 when testing for intersecting line segments comes from U × V. To compute V × U, we exchange the positions of x 2 and x 3 and of y 2 and y 3 in the formula. This yields an equivalent result but with the sign reversed. Therefore, if p 3 is clockwise from p 2, for example, this tells us that p 2 is counterclockwise from p 3, as we would expect.
Q: To test whether two line segments from points p 1 to p 2 and p 3 to p 4 intersect, we first examine whether the bounding boxes of the line segments intersect and then compare the orientation of p 3 relative