CGAL::Polyhedron_3<Traits>

Definition

A polyhedral surface Polyhedron_3<Traits> consists of vertices V, edges E, facets F and an incidence relation on them. Each edge is represented by two halfedges with opposite orientations.

Vertices represent points in 3d-space. Edges are straight line segments between two endpoints. Facets are planar polygons without holes defined by the circular sequence of halfedges along their boundary. The polyhedral surface itself can have holes. The halfedges along the boundary of a hole are called border halfedges and have no incident facet. An edge is a border edge if one of its halfedges is a border halfedge. A surface is closed if it contains no border halfedges. A closed surface is a boundary representation for polyhedra in three dimensions. The convention is that the halfedges are oriented counterclockwise around facets as seen from the outside of the polyhedron. An implication is that the halfedges are oriented clockwise around the vertices. The notion of the solid side of a facet as defined by the halfedge orientation extends to polyhedral surfaces with border edges although they do not define a closed object. If normal vectors are considered for the facets, normals point outwards (following the right hand rule).

The strict definition can be found in [Ket99]. One implication of this definition is that the polyhedral surface is always an orientable and oriented 2-manifold with border edges, i.e., the neighborhood of each point on the polyhedral surface is either homeomorphic to a disc or to a half disc, except for vertices where many holes and surfaces with boundary can join. Another implication is that the smallest representable surface is a triangle (for polyhedral surfaces with border edges) or a tetrahedron (for polyhedra). Boundary representations of orientable 2-manifolds are closed under Euler operations. They are extended with operations that create or close holes in the surface.

Other intersections besides the incidence relation are not allowed, although they are not automatically handled, since self intersections are not easy to check efficiently. Polyhedron_3<Traits> does only maintain the combinatorial integrity of the polyhedral surface (using Euler operations) and does not consider the coordinates of the points or any geometric information.

The class Polyhedron_3<Traits> can represent polyhedral surfaces as well as polyhedra. The interface is designed in such a way that it is easy to ignore border edges and work only with polyhedra.

The sequence of edges can be ordered in the data structure on request such that the sequence starts with the non-border edges and ends with the border edges. Border edges are then itself ordered such that the halfedge which is incident to the facet comes first and the halfedge incident to the hole comes thereafter. This normalization step counts simultaneously the number of border edges. This number is zero if and only if the surface is a closed polyhedron. Note that this class does not maintain this counter nor the halfedge order during further modifications. There is no automatic caching done for auxiliary information.

#include <CGAL/Polyhedron_3.h>

Parameters

The full template declaration of Polyhedron_3<Traits> states four template parameters:

The first parameter requires a model of the PolyhedronTraits_3 concept as argument, for example CGAL::Polyhedron_traits_3. The second parameter expects a model of the PolyhedronItems_3 concept. By default, the class CGAL::Polyhedron_items_3 is preselected. The third parameter is a class template. A model of the HalfedgeDS concept is expected. By default, the class CGAL::HalfedgeDS_default is preselected, which is a list based implementation of the halfedge data structure. The fourth parameter Alloc requires a standard allocator for STL container classes. The rebind mechanism from Alloc will be used to create appropriate allocators internally. A default is provided with the macro CGAL_ALLOCATOR(int) from the <CGAL/memory.h> header file.

Types

The following handles, iterators, and circulators have appropriate non-mutable counterparts, i.e., const_handle, const_iterator, and const_circulator. The mutable types are assignable to their non-mutable counterparts. Both circulators are assignable to the Halfedge_iterator. The iterators are assignable to the respective handle types. Wherever the handles appear in function parameter lists, the corresponding iterators can be used as well. For convenience, the Edge_iterator enumerates every other halfedge. It is based on the CGAL::N_step_adaptor class. For convenience, the Point_iterator enumerates all points in the polyhedral surface in the same order as the Vertex_iterator, but with the value type Point. It is based on the CGAL::Iterator_project adaptor. Similarly, a Plane_iterator is provided.

Creation

Access Member Functions

Combinatorial Predicates

Euler Operators (Combinatorial Modifications)

The following Euler operations modify consistently the combinatorial structure of the polyhedral surface. The geometry remains unchanged.

Euler Operators Modifying Genus

Modifying Facets and Holes

Erasing

Operations with Border Halfedges

Miscellaneous

See Also

CGAL::Polyhedron_3<Traits>::Vertex
CGAL::Polyhedron_3<Traits>::Halfedge
CGAL::Polyhedron_3<Traits>::Facet
PolyhedronTraits_3
CGAL::Polyhedron_traits_3<Kernel>
PolyhedronItems_3
CGAL::Polyhedron_items_3
HalfedgeDS
CGAL::HalfedgeDS_default
CGAL::Polyhedron_incremental_builder_3<HDS>
CGAL::Modifier_base.

Example

This example program instantiates a polyhedron using the default traits class and creates a tetrahedron.

File: examples/Polyhedron/polyhedron_prog_simple.cpp

#include <CGAL/Simple_cartesian.h>
#include <CGAL/Polyhedron_3.h>

typedef CGAL::Simple_cartesian<double>     Kernel;
typedef CGAL::Polyhedron_3<Kernel>         Polyhedron;
typedef Polyhedron::Halfedge_handle        Halfedge_handle;

int main() {
    Polyhedron P;
    Halfedge_handle h = P.make_tetrahedron();
    if ( P.is_tetrahedron(h))
        return 0;
    return 1;
}