NAME

trim_2D_hull - Removes redundant points from a 2D hull.

SYNOPSIS

#include "h/h_misc.h"

Example compile flags (system dependent):
  -DLINUX_X86_64 -DLINUX_X86_64_OPTERON  -DGNU_COMPILER 
   -I/home/kobus/include
   -L/home/kobus/misc/load/linux_x86_64_opteron -L/usr/lib/x86_64-linux-gnu
  -lKJB                               -lfftw3  -lgsl -lgslcblas -ljpeg  -lSVM -lstdc++                    -lpthread -lSLATEC -lg2c    -lacml -lacml_mv -lblas -lg2c      -lncursesw 


Hull *trim_2D_hull
(
	const Hull *hp,
	double tolerance
);

DESCRIPTION

This routine creates a new hull, similar to the argument hull, but with redundant points removed. A point is considered redundant if removing the point does not change the hull too much. Slightly more specifically, it is considered redundant if it is almost colinear with two other vertices. The gory details are as follows.

    Let D be the distance between two vertices P1, P2.
    Consider some other vertex, V.
    Let the perpendicular distance from V to the segment P1--P2 be d.
    Then, the point is redundant if d/D < tolerance.

When a redundant point is found, then it is removed, and then the remaining points are considered as a group (without the removed ones). It would be faster to condider each point to be removed in the context of the complete set of vertices, but this could lead to all points being deleted. However, no effort is currently made to remove the "most" redundant point first. This may be a reasonable improvement to the routine.

RETURNS

A pointer to a new hull on success and NULL on failure.

DISCLAIMER

This software is not adequatedly tested. It is recomended that results are checked independantly where appropriate.

AUTHOR

Kobus Barnard

DOCUMENTER