CGAL::Nef_polyhedron_2<T>

Definition

An instance of data type Nef_polyhedron_2<T> is a subset of the plane that is the result of forming complements and intersections starting from a finite set H of halfspaces. Nef_polyhedron_2 is closed under all binary set operations intersection, union, difference, complement and under the topological operations boundary, closure, and interior.

The template parameter T is specified via an extended kernel concept. T must be a model of the concept ExtendedKernelTraits_2.

#include <CGAL/Nef_polyhedron_2.h>

Types

Creation

Operations

Constructive Operations

Nef_polyhedron_2<T>	N.complement ()	returns the complement of N in the plane.
Nef_polyhedron_2<T>	N.interior ()	returns the interior of N.
Nef_polyhedron_2<T>	N.closure ()	returns the closure of N.
Nef_polyhedron_2<T>	N.boundary ()	returns the boundary of N.
Nef_polyhedron_2<T>	N.regularization ()	returns the regularized polyhedron (closure of interior).
Nef_polyhedron_2<T>	N.intersection ( N1)	returns N $$ N1.
Nef_polyhedron_2<T>	N.join ( N1)	returns N $$ N1. Note that ``union'' is a keyword of C++ and cannot be used for this operation.
Nef_polyhedron_2<T>	N.difference ( N1)	returns N $$- N1.
Nef_polyhedron_2<T>	N.symmetric_difference ( N1)	returns the symmectric difference N - T $$ T - N.

Additionally there are operators *,+,-,^,! which implement the binary operations intersection, join, difference, symmetric difference, and the unary operation complement, respectively. There are also the corresponding modification operations *=,+=,-=,^=.

There are also comparison operations like <,<=,>,>=,==,!= which implement the relations subset, subset or equal, superset, superset or equal, equality, inequality, respectively.

Exploration - Point location - Ray shooting

Types

Operations

Input and Output

Implementation

Nef polyhedra are implemented on top of a halfedge data structure and use linear space in the number of vertices, edges and facets. Operations like empty take constant time. The operations clear, complement, interior, closure, boundary, regularization, input and output take linear time. All binary set operations and comparison operations take time $$O(n log$$n) where $$n is the size of the output plus the size of the input.

The point location and ray shooting operations are implemented in two flavors. The NAIVE operations run in linear query time without any preprocessing, the DEFAULT operations (equals LMWT) run in sub-linear query time, but preprocessing is triggered with the first operation. Preprocessing takes time $$O(N²), the sub-linear point location time is either logarithmic when LEDA's persistent dictionaries are present or if not then the point location time is worst-case linear, but experiments show often sublinear runtimes. Ray shooting equals point location plus a walk in the constrained triangulation overlayed on the plane map representation. The cost of the walk is proportional to the number of triangles passed in direction d until an obstacle is met. In a minimum weight triangulation of the obstacles (the plane map representing the polyhedron) the theory provides a $$O(sqrt(n)) bound for the number of steps. Our locally minimum weight triangulation approximates the minimum weight triangulation only heuristically (the calculation of the minimum weight triangulation is conjectured to be NP hard). Thus we have no runtime guarantee but a strong experimental motivation for its approximation.

Example

Nef polyhedra are parameterized by a so-called extended geometric kernel. There are three kernels, one based on a homogeneous representation of extended points called Extended_homogeneous<RT> where RT is a ring type providing additionally a gcd operation, one based on a Cartesian representation of extended points called Extended_cartesian<NT> where NT is a field type, and finally Filtered_extended_homogeneous<RT> (an optimized version of the first). The following example uses the filtered homogeneous kernel to construct the intersection of two halfspaces.

File: examples/Nef_2/simple_intersection.cpp

#include <CGAL/Gmpz.h>
#include <CGAL/Filtered_extended_homogeneous.h>
#include <CGAL/Nef_polyhedron_2.h>

typedef CGAL::Gmpz RT;
typedef CGAL::Filtered_extended_homogeneous<RT> Extended_kernel;
typedef CGAL::Nef_polyhedron_2<Extended_kernel> Nef_polyhedron;
typedef Nef_polyhedron::Line  Line;

int main()
{
  Nef_polyhedron N1(Line(1,0,0));
  Nef_polyhedron N2(Line(0,1,0), Nef_polyhedron::EXCLUDED);
  Nef_polyhedron N3 = N1 * N2; // line (*)
  return 0;
}

After line (*) N3 is the intersection of N1 and N2. The member types of Nef_polyhedron_2< Extended_homogeneous<NT> > map to corresponding types of the standard CGAL geometry kernel (type equality in pseudo-code notation):

CGAL::Nef_polyhedron_2< CGAL::Extended_cartesian<FT> >::Point
  == CGAL::Cartesian<FT>::Point_2

CGAL::Nef_polyhedron_2< CGAL::Extended_homogeneous<RT> >::Point
   == CGAL::Homogeneous<RT>::Point_2

CGAL::Nef_polyhedron_2< CGAL::Filtered_extended_homogeneous<RT> >::Point
   == CGAL::Homogeneous<RT>::Point_2