CGAL users discussion list

Le Mer 27 décembre 2006 15:53, Monique Teillaud a écrit :
> If you project your points on the horizontal plane (provided they don't
> lie in a vertical plane) and compute the 2d convex hull of the projected
> points with cgal, it gives you the sequence you are looking for.

Hi,
If you don't want to care about the points lying in a vertical plane or
not, any affine transformation will be ok:

let A, B and C be three non collinear points among your vertices, and map
them to f(A) = (0, 0), f(B) = (0, 1) and f(C) = (1, 0) respectively. Any
other vertex X, with barycentric coordinates (a, b, c) with respect to ABC
(i.e. a+b+c = 1, aA+bB+cC = X) should then be mapped to f(X) = (b, c).

b and c may be computed in the following way:
(epsilon, b, c)^t = ((B-A)x(C-A) | B-A | C-A)^(-1) (X-A)
-- 
Camille