• Choose a category
• All
• Classic-Fiction

By Root 1510 0

case we reset pc to pi. If pi and pc are collinear, we set pc to pi only if pi is further from p0 than pc. Thus, once we have traversed all of the points in the list, pc is the point that is clockwise to all others with respect to p0. At this point, we reset p0 to pc and repeat the process until p0 is the point at which we started. Once we reach this point, all points in the convex hull have been inserted into polygon at the top of the outer loop.

The runtime complexity of cvxhull is O (nh), where n is the total number of points, and h is the number of points in the convex hull. The loop in which the lowest point is determined runs in O (n) time because we must traverse all points to determine which is the lowest. The nested loops together are O (nh) because for each point inserted into the convex hull, we must traverse all other points to determine which is next to insert. Since locating the lowest point and constructing the convex hull are carried out sequentially, the runtime complexity of cvxhull is O (nh).

Example 17.3. Implementation for Computing Convex Hulls

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

* *

* ------------------------------- cvxhull.c ------------------------------ *

* *

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

#include

#include

#include "geometry.h"

#include "list.h"

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

* *

* -------------------------------- cvxhull ------------------------------- *

* *

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

int cvxhull(const List *P, List *polygon) {

ListElmt *element;

Point *min,

*low,

*p0,

*pi,

*pc;

double z,

length1,

length2;

int count;

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

* *

* Find the lowest point in the list of points. *

* *

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

min = list_data(list_head(P));

for (element = list_head(P); element != NULL; element = list_next(element)) {

p0 = list_data(element);

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

* *

* Keep track of the lowest point thus far. *

* *

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

if (p0->y < min->y) {

min = p0;

low = list_data(element);

}

else {

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

* *

* If a tie occurs, use the lowest and leftmost point. *

* *

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

if (p0->y == min->y && p0->x < min->x) {

min = p0;

low = list_data(element);

}

}

}

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

* *

* Initialize the list for the convex hull. *

* *

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

list_init(polygon, NULL);

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

* *

* Perform Jarvis's march to compute the convex hull. *

* *

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

p0 = low;

do {

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

* *

* Insert the new p0 into the convex hull. *

* *

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

if (list_ins_next(polygon, list_tail(polygon), p0) != 0) {

list_destroy(polygon);

return -1;

}

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

* *

* Find the point pc that is clockwise from all others. *

* *

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

count = 0;

for (element = list_head(P); element != NULL; element =

list_next(element)) {

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

* *

* Skip p0 in the list of points. *

* *

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