Mastering Algorithms With C - Kyle Loudon [224]
A: Recall that when the orientation of either p 3 or p 4 is 0, it means that the line segment from either p 1 to p 3 or p 1 to p 4 is collinear with the line segment from p 1 to p 2. If the bounding boxes of the two line segments intersect as well, this tells us that at least some parts of the segments overlay each other (see Figure 17.9a). Therefore, the line segments intersect. On the other hand, it is possible to have two line segments that are collinear without intersecting. This occurs when the segments would overlay each other if either were long enough, but neither has the length necessary to do so (see Figure 17.9b).
Figure 17.9. Collinear line segments whose bounding boxes (a) intersect and (b) do not intersect
Q: In this chapter we learned that the smallest polygon surrounding a set of points is called a convex hull. This name implies that the polygon is always convex. Why is this?
A: Recall that a polygon is convex if any line segment connecting two points inside the polygon lies completely inside the polygon itself; otherwise, the polygon is concave. To understand why a convex hull is always convex, consider a concave polygon that surrounds a set of points. For any sequence of three points p 1, p 2, and p 3 defining a concave region, if we replace the edges from p 1 to p 2 and p 2 to p 3 with a single edge from p 1 to p 3, we can reduce the size of the polygon while keeping p 2 enclosed. We know that the size of the polygon will be reduced because it is always shorter to go from one point to another than through a third point first. We know that p 2 will still be enclosed by the resulting polygon because the angle from p 2 to p 3 is less than the angle from p 1 to p 2. Therefore, since a convex polygon will always be shorter than any concave one that encloses the same points, a convex hull must be convex (see Figure 17.10).
Figure 17.10. Showing that the smallest polygon enclosing a set of points is always convex
Q: Suppose in the approximation for distances on Earth presented in this chapter we would like to improve the method used in the function geodist. Specifically, we would like to do something to take into account the change in the Earth's radius at different latitudes and longitudes. How can we do this?
A: One way to make this improvement is to use the fact that both points passed into geodist have their own value for the spherical coordinate ρ. When we treat the Earth as a perfect sphere, we set the rho member of each point to the same value since we are considering the distance from the Earth's center to the surface to be the same everywhere. However, a better approach would be to set rho for each point to the actual distance from the center of the Earth to the point and then compute an average of the two rho members for the radius of the arc. Although this does not perfect the distance computation, it does generally improve it.
Related Topics
Vectors
Mathematical quantities having both magnitude and direction. A vector consists of several components , one for each axis of the coordinate system. If we draw a vector as a line segment starting at the origin, a vector's components are values that describe how far we must move along each axis to reach the point at which the vector ends. Some operations with vectors include addition, subtraction, dot products, cross products, and magnitudes.
Testing whether any two line segments intersect
A generalization of the test provided earlier in this chapter for determining whether two line segments intersect. However, rather than simply applying this test over and over again to test whether any line segments in a set intersect, it is best to use a dedicated approach. Using a dedicated approach, the problem can be solved in O (n lg n) time, where n is the number of line segments.
Graham's scan