CGAL users discussion list

[Camille Wormser <>]

Nora Ayanian wrote:
> I would like to use the dD Convex Hulls and Delaunay Triangulations 
> package to compute triangulations (intersections, etc.) of 6+ 
> dimensional polytopes, 

Dear Nora,
What kind of operations do you need on these polytopes? In case you need 
to use the Convex_hull_d package, I attach a previous message sent on 
this list which briefly presents how to use it.

> starting from H-representation.

If you want to compute the V-representation from the H-representation, 
you will have to do the conversion "manually". In order to compute the 
V-representation of the intersection C of some halfspaces, you could:

1) first compute the d-convex hull of the (polar) dual points 
representing the hyperplanes (you will need to know at least one point 
inside C that will be used as a center for the polar duality)
2) then deducing the vertices of the convex hull C from the faces of D: 
if (h_0...h_5) is a (simplicial) face of D, then h_0\cap...\cap h_5 is a 
vertex of C.
3) if two faces of D share an edge, the corresponding vertices of C are 
adjacent.

Hope this helps,
--
Camille Wormser

--- Begin Message ---

• From: Camille Wormser <>
• To:
• Subject: Re: [cgal-discuss] 6 Dimensional Space
• Date: Fri, 27 Oct 2006 12:16:44 +0200
• List-archive: <https://lists-sop.inria.fr/wws/arc/cgal-discuss>
• List-id: <cgal-discuss.lists-sop.inria.fr>

wrote:

Can anyone please provide me with a simple example to calculate the convex
hull of a set of points in 6D, USING CGAL ?

Something like this should work :
--------------------------------------------------------------------
#include <list>
#include <Convex_hull_d.h>
#include <CGAL/Cartesian_d.h>

typedef CGAL::Cartesian_d<double> Kd;
typedef CGAL::Convex_hull_d<Kd> CHull_d;
typedef CHull_d::Point_d Point_d;
typedef std::list<Point_d> List_ptd;

CHull_d* init_insertion(List_ptd points) {
CHull_d::Vertex_handle vh6;
List_ptd::iterator a, b;

a = points->begin();
b = points->end();
ch6 = new CHull_d(6);

while(a != b) {
vh6 = ch6->insert(*a);
++a;
}
}
--------------------------------------------------------------------
A Point_d can be created by calling for example
Point_d(6, c.begin(), c.end());
where c is a list of 6 doubles.

Then, if you want to retrieve the points on the convex hull, you have access to iterators
ch6->Hull_point_const_iterator hull_points_begin()
ch6->Hull_point_const_iterator hull_points_end()

You also have the facets iterators
ch6->Facet_iterator facets_begin()
ch6->Facet_iterator facets_end()

and ch6->vertex_of_facet(facet,j) for j = 0..5 gives you the vertices.
ch6->vertex_of_facet(facet,j)->point() gives you the point.
ch6->vertex_of_facet(facet,j)->point().cartesian_begin() gives you an iterator on the coordinates.

You may however soon encounter robustness issues, and then need an exact number type (note that this Convex_hull_d computes and stores some hyperplanes, and is not completely predicate-based...).
--
Camille



--- End Message ---