core/vgl/algo/vgl_convex_hull_2d.txx File Reference

two-dimensional convex hull read points from stdin, one point per line, as two numbers separated by whitespace on stdout, points on convex hull in order around hull, given by their numbers in input order the results should be "robust", and not return a wildly wrong hull, despite using floating point works in O(n log n); I think a bit faster than Graham scan; somewhat like Procedure 8.2 in Edelsbrunner's "Algorithms in Combinatorial Geometry", and very close to: A.M. More...

#include "vgl_convex_hull_2d.h"
#include <vcl_cstdlib.h>

Go to the source code of this file.

Defines
#define	vgl_convex_hull_2d_txx_
#define	CMPM(c, A, B)
#define	VGL_CONVEX_HULL_2D_INSTANTIATE(T)

---

Detailed Description

two-dimensional convex hull read points from stdin, one point per line, as two numbers separated by whitespace on stdout, points on convex hull in order around hull, given by their numbers in input order the results should be "robust", and not return a wildly wrong hull, despite using floating point works in O(n log n); I think a bit faster than Graham scan; somewhat like Procedure 8.2 in Edelsbrunner's "Algorithms in Combinatorial Geometry", and very close to: A.M.

Andrew, "Another Efficient Algorithm for Convex Hulls in Two Dimensions", Info. Proc. Letters 9, 216-219 (1979) (See also http://geometryalgorithms.com/Archive/algorithm_0110/algorithm_0110.htm)

Ken Clarkson wrote this. Copyright (c) 1996 by AT&T.. Permission to use, copy, modify, and distribute this software for any purpose without fee is hereby granted, provided that this entire notice is included in all copies of any software which is or includes a copy or modification of this software and in all copies of the supporting documentation for such software. THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED WARRANTY. IN PARTICULAR, NEITHER THE AUTHORS NOR AT&T MAKE ANY REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE.

Definition in file vgl_convex_hull_2d.txx.

---

Define Documentation

#define CMPM	(		c,
			A,
			B
	)

Value:

v = (*(double*const*)A)[c] - (*(double*const*)B)[c];\
  if (v>0) return 1;\
  if (v<0) return -1

Definition at line 53 of file vgl_convex_hull_2d.txx.

#define VGL_CONVEX_HULL_2D_INSTANTIATE

(

T

)

Value:

/* template vcl_ostream& operator<<(vcl_ostream& s, vgl_convex_hull_2d<T >const& h); */ \
/* template vcl_istream& operator>>(vcl_istream& s, vgl_convex_hull_2d<T >& h); */ \
template class vgl_convex_hull_2d<T >

Definition at line 148 of file vgl_convex_hull_2d.txx.

#define vgl_convex_hull_2d_txx_

Definition at line 2 of file vgl_convex_hull_2d.txx.