CGAL 6.1 - 2D Boolean Operations on Nef Polygons

Loading...
Searching...
No Matches
List of all members | Classes
CGAL::Nef_polyhedron_2< T > Class Template Reference
Reference Manual

`#include <CGAL/Nef_polyhedron_2.h>`

## Definition

template<typename T>
class CGAL::Nef_polyhedron_2< T >

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`.

Exploration - Point location - Ray shooting

As Nef polyhedra are the result of forming complements and intersections starting from a set `H` of halfspaces that are defined by oriented lines in the plane, they can be represented by an attributed plane map \( M = (V,E,F)\). For topological queries within `M` the following types and operations allow exploration access to this structure.

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^2)\), 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 overlaid 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 Nef_2/nef_2_intersection.cpp

#include <CGAL/Exact_integer.h>
#include <CGAL/Filtered_extended_homogeneous.h>
#include <CGAL/Nef_polyhedron_2.h>
typedef CGAL::Exact_integer 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;
}
Exact_integer.h
CGAL::Filtered_extended_homogeneous
The class Filtered_extended_homogeneous serves as a traits class for the class Nef_polyhedron_2<T>.
Definition: Filtered_extended_homogeneous.h:20
CGAL::Nef_polyhedron_2
An instance of data type Nef_polyhedron_2<T> is a subset of the plane that is the result of forming c...
Definition: Nef_polyhedron_2.h:92
CGAL::Nef_polyhedron_2::Line
unspecified_type Line
the oriented lines modeling halfplanes.
Definition: Nef_polyhedron_2.h:101
unspecified_type

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
CGAL::Nef_polyhedron_2::Point
unspecified_type Point
the affine points of the plane.
Definition: Nef_polyhedron_2.h:106
CGAL::Cartesian
CGAL::Homogeneous

The same holds for the types `Line` and `Direction` in the local scope of `Nef_polyhedron_2<...>`.

Examples
  Nef_2/nef_2_construction.cpp, Nef_2/nef_2_exploration.cpp, Nef_2/nef_2_intersection.cpp, and Nef_2/nef_2_polylines.cpp.

## Classes
class | Explorer
| a decorator to examine the underlying plane map. More...
class | Topological_explorer
| An instance `D` of the data type `Topological_explorer` is a decorator for interfacing the topological structure of a plane map `P` (read-only). More...

## Types
enum | Boundary { EXCLUDED , INCLUDED }
| construction selection. More...
enum | Content { EMPTY , COMPLETE }
| construction selection More...
enum | Location_mode { DEFAULT , NAIVE , LMWT }
| selectionflag for the point location mode. More...
typedef unspecified_type | Line
| the oriented lines modeling halfplanes.
typedef unspecified_type | Point
| the affine points of the plane.
typedef unspecified_type | Direction
| directions in our plane.
typedef unspecified_type | Polygons_tag
| tag for calling polygon constructor.
typedef unspecified_type | Polylines_tag
| tag for calling polyline constructor.
typedef unspecified_type | Object_handle
| a generic handle to an object of the underlying plane map.

## Creation
| Nef_polyhedron_2 (Content plane=EMPTY)
| creates an instance `N` of type `Nef_polyhedron_2<T>` and initializes it to the empty set if `plane == EMPTY` and to the whole plane if `plane == COMPLETE`.
| Nef_polyhedron_2 (Line l, Boundary line=INCLUDED)
| creates a Nef polyhedron `N` containing the halfplane left of `l` including `l` if `line==INCLUDED`, excluding `l` if `line==EXCLUDED`.
template<class Forward_iterator >
| Nef_polyhedron_2 (Forward_iterator it, Forward_iterator end, Boundary b=INCLUDED)
| creates a Nef polyhedron `N` from the simple polygon `P` spanned by the list of points in the iterator range `[it,end)` and including its boundary if `b = INCLUDED` excluding the boundary otherwise.
template<class Forward_iterator >
| Nef_polyhedron_2 (Forward_iterator it, Forward_iterator end, Polygons_tag)
| The iterator range [it, end) defines a set point ranges, each of which defines the boundary of simple polygon.
template<class Forward_iterator >
| Nef_polyhedron_2 (Forward_iterator it, Forward_iterator end, Polylines_tag)
| The iterator range [it, end) defines a set point ranges, each of which defines a polyline.

## Operations
void | clear (Content plane=EMPTY)
| makes `N` the empty set if `plane == EMPTY` and the full plane if `plane == COMPLETE`.
bool | is_empty ()
| returns true if `N` is empty, false otherwise.
bool | is_plane ()
| returns true if `N` is the whole plane, false otherwise.
bool | contains (Object_handle h)
| returns true iff the object `h` is contained in the set represented by `N`.
bool | contained_in_boundary (Object_handle h)
| returns true iff the object `h` is contained in the \( 1\)-skeleton of `N`.
Object_handle | locate (const Point &p, Location_mode m=DEFAULT)
| returns a generic handle `h` to an object (face, halfedge, vertex) of the underlying plane map that contains the point `p` in its relative interior.
Object_handle | ray_shoot (const Point &p, const Direction &d, Location_mode m=DEFAULT)
| returns a handle `h` with `N.contains(h)`, that can be converted to a `Vertex_/Halfedge_/Face_const_handle` as described above.
Object_handle | ray_shoot_to_boundary (const Point &p, const Direction &d, Location_mode m=DEFAULT)
| returns a handle `h`, that can be converted to a `Vertex_/Halfedge_const_handle` as described above.
Explorer | explorer ()
| returns a decorator object that allows read-only access of the underlying plane map.

## Constructive Operations
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.
Nef_polyhedron_2< T > | complement ()
| returns the complement of `N` in the plane.
Nef_polyhedron_2< T > | interior ()
| returns the interior of `N`.
Nef_polyhedron_2< T > | closure ()
| returns the closure of `N`.
Nef_polyhedron_2< T > | boundary ()
| returns the boundary of `N`.
Nef_polyhedron_2< T > | regularization ()
| returns the regularized polyhedron (closure of interior).
Nef_polyhedron_2< T > | intersection (const Nef_polyhedron_2< T > &N1)
| returns `N` \( \cap\) `N1`.
Nef_polyhedron_2< T > | join (const Nef_polyhedron_2< T > &N1)
| returns `N` \( \cup\) `N1`.
Nef_polyhedron_2< T > | difference (const Nef_polyhedron_2< T > &N1)
| returns `N` \( -\) `N1`.
Nef_polyhedron_2< T > | symmetric_difference (const Nef_polyhedron_2< T > &N1)
| returns the symmetric difference `N - T` \( \cup\) `T - N`.

## Member Typedef Documentation

## ◆ Object_handle

template<typename T >

typedef unspecified_type CGAL::Nef_polyhedron_2< T >::Object_handle

a generic handle to an object of the underlying plane map.

The kind of object `(vertex, halfedge, face)` can be determined and the object can be assigned to a corresponding handle by the three functions:

`bool assign(Vertex_const_handle& h, Object_handle)`

`bool assign(Halfedge_const_handle& h, Object_handle)`

`bool assign(Face_const_handle& h, Object_handle)`

where each function returns `true` iff the assignment to `h` was done.

## Member Enumeration Documentation

## ◆ Boundary

template<typename T >

enum CGAL::Nef_polyhedron_2::Boundary

construction selection.

Enumerator
EXCLUDED |
INCLUDED |

## ◆ Content

template<typename T >

enum CGAL::Nef_polyhedron_2::Content

construction selection

Enumerator
EMPTY |
COMPLETE |

## ◆ Location_mode

template<typename T >

enum CGAL::Nef_polyhedron_2::Location_mode

selectionflag for the point location mode.

LMWT stands for Locally Minimum Weight Triangulation, a locally optimized constrained triangulation where the weight corresponds to the length of the edges of the triangulation.

Enumerator
DEFAULT |
NAIVE |
LMWT |

## Constructor & Destructor Documentation

## ◆ Nef_polyhedron_2()

template<typename T >
template<class Forward_iterator >

CGAL::Nef_polyhedron_2< T >::Nef_polyhedron_2 | ( | Forward_iterator | it,
|  | Forward_iterator | end,
|  | Boundary | b = `INCLUDED`
| ) |  |

creates a Nef polyhedron `N` from the simple polygon `P` spanned by the list of points in the iterator range `[it,end)` and including its boundary if `b = INCLUDED` excluding the boundary otherwise.

`Forward_iterator` has to be an iterator with value type `Point`. This construction expects that `P` is simple. The degenerate cases where `P` contains no point, one point or spans just one segment (two points) are correctly handled. In all degenerate cases there's only one unbounded face adjacent to the degenerate polygon. If `b == INCLUDED` then `N` is just the boundary. If `b == EXCLUDED` then `N` is the whole plane without the boundary.

## Member Function Documentation

## ◆ explorer()

template<typename T >

Explorer CGAL::Nef_polyhedron_2< T >::explorer | ( |  | ) |

returns a decorator object that allows read-only access of the underlying plane map.

See the manual page `Explorer` for its usage.

Examples
  Nef_2/nef_2_exploration.cpp.

## ◆ join()

template<typename T >

Nef_polyhedron_2< T > CGAL::Nef_polyhedron_2< T >::join | ( | const Nef_polyhedron_2< T > & | N1 | ) |

returns `N` \( \cup\) `N1`.

Note that "union" is a keyword of C++ and cannot be used for this operation.

## ◆ locate()

template<typename T >

Object_handle CGAL::Nef_polyhedron_2< T >::locate | ( | const Point & | p,
|  | Location_mode | m = `DEFAULT`
| ) |  |

returns a generic handle `h` to an object (face, halfedge, vertex) of the underlying plane map that contains the point `p` in its relative interior.

The point `p` is contained in the set represented by `N` if `N.contains(h)` is true. The location mode flag `m` allows one to choose between different point location strategies.

## ◆ ray_shoot()

template<typename T >

Object_handle CGAL::Nef_polyhedron_2< T >::ray_shoot | ( | const Point & | p,
|  | const Direction & | d,
|  | Location_mode | m = `DEFAULT`
| ) |  |

returns a handle `h` with `N.contains(h)`, that can be converted to a `Vertex_/Halfedge_/Face_const_handle` as described above.

The object returned is intersected by the ray starting in `p` with direction `d` and has minimal distance to `p`. The operation returns an empty `Object_handle` if the ray shoot along `d` does not hit any object `h` of `N` with `N.contains(h)`. The location mode flag `m` allows one to choose between different point location strategies.

## ◆ ray_shoot_to_boundary()

template<typename T >

Object_handle CGAL::Nef_polyhedron_2< T >::ray_shoot_to_boundary | ( | const Point & | p,
|  | const Direction & | d,
|  | Location_mode | m = `DEFAULT`
| ) |  |

returns a handle `h`, that can be converted to a `Vertex_/Halfedge_const_handle` as described above.

The object returned is part of the \( 1\)-skeleton of `N`, intersected by the ray starting in `p` with direction `d` and has minimal distance to `p`. The operation returns an empty `Object_handle` if the ray shoot along `d` does not hit any \( 1\)-skeleton object `h` of `N`. The location mode flag `m` allows one to choose between different point location strategies.