Main Page | Modules | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

regina::NDoubleDescriptor Class Reference
[Vertex Enumeration]

Implements a modified double descriptor method for polytope vertex enumeration. More...

#include <ndoubledescriptor.h>

Inheritance diagram for regina::NDoubleDescriptor:

regina::NVertexEnumerator List of all members.

Public Member Functions

 NDoubleDescriptor ()
 Creates a new vertex enumeration engine.
template<class OutputIterator, class RayIterator, class FaceIterator>
void enumerateVertices (OutputIterator results, RayIterator oldRaysFirst, RayIterator oldRaysLast, FaceIterator facesFirst, FaceIterator facesLast, const NMatrixInt &subspace, const NCompConstraintSet *constraints, NProgressNumber *progress=0) const
 Determines the extremal rays of the intersection of the given cone with the given linear subspace.

Detailed Description

Implements a modified double descriptor method for polytope vertex enumeration.

Python:
Not present.


Constructor & Destructor Documentation

regina::NDoubleDescriptor::NDoubleDescriptor  )  [inline]
 

Creates a new vertex enumeration engine.


Member Function Documentation

template<class OutputIterator, class RayIterator, class FaceIterator>
void regina::NDoubleDescriptor::enumerateVertices OutputIterator  results,
RayIterator  oldRaysFirst,
RayIterator  oldRaysLast,
FaceIterator  facesFirst,
FaceIterator  facesLast,
const NMatrixInt subspace,
const NCompConstraintSet constraints,
NProgressNumber progress = 0
const [virtual]
 

Determines the extremal rays of the intersection of the given cone with the given linear subspace.

The resulting rays will be newly allocated and written to the given output iterator. Their deallocation is the responsibility of whoever called this routine.

The given cone is represented by a list of its extremal rays and a list of hyperplanes that determine its faces. Specifically the list of face hyperplanes must be a set of hyperplanes passing through the origin for which the actual faces of the cone are determined by intersecting this set of hyperplanes with some subspace of the entire vector space. Note that this list of hyperplanes might well be the faces themselves.

The new linear subspace to intersect is represented by a matrix in which each row represents a hyperplane through the origin; the subspace is the intersection of all these hyperplanes. Each hyperplane is represented by the vector of a ray perpendicular to it.

The resulting list of extremal rays is guaranteed not to contain any duplicates or redundancies. They are guaranteed to be of the same subclass of NRay as the initial extremal rays.

Parameter constraints may contain a set of compatibility constraints representing necessary and sufficient conditions for a convex combination of two valid rays to be also valid, where the definition of valid depends upon the specific application at hand. If a set of constraints is passed, only valid extremal rays (as defined by these constraints) will be found. In this case the given cone may be a union of many smaller cones, since validity need not be preserved under addition. These smaller cones may intersect, and an extremal ray may belong to more than one such cone. In such cases, the ray should not be duplicated.

A numeric progress watcher may be passed for progress reporting. If so, this routine will poll for cancellation requests accordingly.

Precondition:
The cone described by [oldRaysFirst, oldRaysLast) and [facesFirst, facesLast) is convex and satisfies the structural requirements given above.

The list [oldRaysFirst, oldRaysLast) of extremal rays does not contain any duplicates or redundancies.

If constraints is non-zero, then the given list [oldRaysFirst, oldRaysLast) must contain only valid rays, where validity is defined by the given set of compatibility constraints.

Todo:
Optimise: Intersect the hyperplanes in a good order.

Parameters:
results the output iterator to which the resulting extremal rays will be written; this must accept objects of type NRay* (or alternatively pointers to the same subclass of NRay as is used for the initial list of rays).
oldRaysFirst the beginning of the list [oldRaysFirst, oldRaysLast) of extremal rays defining the cone to intersect with the given subspace; this must be a forward iterator over objects of type const NRay* (or some subclass thereof).
oldRaysLast the end of the list [oldRaysFirst, oldRaysLast) of extremal rays defining the cone to intersect with the given subspace; this must be a forward iterator over objects of type const NRay* (or some subclass thereof).
facesFirst the beginning of the list [facesFirst, facesLast) of hyperplanes that determine the faces of the given cone, as described above; each hyperplane is represented by the vector of a ray perpendicular to it. Note that this list is allowed to contain duplicates or redundancies. This must be a forward iterator over objects of type NVector<NLargeInteger>*.
facesLast the end of the list [facesFirst, facesLast) of hyperplanes that determine the faces of the given cone. This must be a forward iterator over objects of type NVector<NLargeInteger>*.
subspace a matrix whose rows are hyperplanes whose intersection defines the subspace to intersect with the given cone.
constraints a set of compatibility constraints that define validity if we are only to find "valid" extremal rays, or 0 if no additional constraints should be imposed.
progress a numeric progress watcher through which progress will be reported, or 0 if no progress reporting is required. If a progress watcher is passed, its expected total will be increased immediately by some number of steps and the completed total will be increased gradually by this same number. Note that NProgress::setFinished() will not be called, since whoever called this routine may need to do further processing.

Implements regina::NVertexEnumerator.


The documentation for this class was generated from the following file:
Copyright © 1999-2004, Ben Burton
This software is released under the GNU General Public License.
For further information, or to submit a bug or other problem, please contact Ben Burton (bab@debian.org).