Mastering Algorithms With C - Kyle Loudon [219]
if ((pi = list_data(element)) == p0)
continue;
/***********************************************************************
* *
* Count how many points have been explored. *
* *
***********************************************************************/
count++;
/***********************************************************************
* *
* Assume the first point to explore is clockwise from all others *
* until proven otherwise. *
* *
***********************************************************************/
if (count == 1) {
pc = list_data(element);
continue;
}
/***********************************************************************
* *
* Determine whether pi is clockwise from pc. *
* *
***********************************************************************/
if ((z = ((pi->x - p0->x) * (pc->y - p0->y)) - ((pi->y - p0->y) * (pc->x
- p0->x))) > 0) {
/********************************************************************
* *
* The point pi is clockwise from pc. *
* *
********************************************************************/
pc = pi;
}
else if (z == 0) {
/********************************************************************
* *
* If pi and pc are collinear, select the point furthest from p0. *
* *
********************************************************************/
length1 = sqrt(pow(pi->x - p0->x, 2.0) + pow(pi->y - p0->y, 2.0));
length2 = sqrt(pow(pc->x - p0->x, 2.0) + pow(pc->y - p0->y, 2.0));
if (length1 > length2) {
/*****************************************************************
* *
* The point pi is further from p0 than pc. *
* *
*****************************************************************/
pc = pi;
}
}
}
/**************************************************************************
* *
* Prepare to find the next point for the convex hull. *
* *
**************************************************************************/
p0 = pc;
/**************************************************************************
* *
* Continue until reaching the lowest point again. *
* *
**************************************************************************/
} while (p0 != low);
return 0
;
}
Description of Arc Length on Spherical Surfaces
Many problems require computing the distance between two points. When we are interested in the distance between points along a straight line, we apply the well-known distance formula derived from the Pythagorean theorem. However, if we are interested in the distance between points along a curved surface, the problem becomes more difficult. Fortunately, computing the minimum distance, or arc length, between two points on a spherical surface is a special case that is relatively simple. To begin, let's look at two different coordinate systems, rectilinear coordinates and spherical coordinates.
Rectilinear and Spherical Coordinates
The rectilinear coordinate system is the coordinate system that is most familiar to us. In rectilinear coordinates, a point's location is specified using three values, x, y, z, which are its positions along the x-axis, y-axis, and z-axis. Referring to Figure 17.5, the z-axis is positive going upward. Standing at the arrow looking forward, the x-axis is positive to the right, and the y-axis is positive straight ahead. From this vantage point, the positive directions for x and y look the same as in two dimensions. Thus, to locate (3, 4, 5), for example, we move three units to the right along the x-axis, four units ahead parallel to the y-axis, and five units up parallel to the z-axis (see Figure 17.5).
Figure 17.5. Locating the point (3, 4, 5) in a rectilinear coordinate system
In spherical coordinates, a point's location is specified in terms of a distance ρ (rho) and two angles, θ (theta) and φ (phi): ρ is the distance along an imaginary line from the origin to the point (a radius), θ is the angle the point forms from the positive x-axis toward the positive y-axis, and φ is the angle the point forms from the positive z-axis heading toward the