ttl Namespace Reference

Main interface to TTL. More...

Functions
Delaunay Triangulation

template<class TraitsType , class DartType , class PointType >
bool	insertNode (DartType &dart, PointType &point)
	Inserts a new node in an existing Delaunay triangulation and swaps edges to obtain a new Delaunay triangulation.
template<class TraitsType , class DartType >
void	removeRectangularBoundary (DartType &dart)
	Removes the rectangular boundary of a triangulation as a final step of an incremental Delaunay triangulation.
template<class TraitsType , class DartType >
void	removeNode (DartType &dart)
	Removes the node associated with dart and updates the triangulation to be Delaunay.
template<class TraitsType , class DartType >
void	removeBoundaryNode (DartType &dart)
	Removes the boundary node associated with dart and updates the triangulation to be Delaunay.
template<class TraitsType , class DartType >
void	removeInteriorNode (DartType &dart)
	Removes the interior node associated with dart and updates the triangulation to be Delaunay.
template<class TraitsType , class ForwardIterator , class DartType >
void	insertNodes (ForwardIterator first, ForwardIterator last, DartType &dart)
Topological and Geometric Queries

template<class TraitsType , class PointType , class DartType >
bool	locateFaceSimplest (const PointType &point, DartType &dart)
	Locates the face containing a given point.
template<class TraitsType , class PointType , class DartType >
bool	locateTriangle (const PointType &point, DartType &dart)
	Locates the triangle containing a given point.
template<class TraitsType , class PointType , class DartType >
bool	inTriangleSimplest (const PointType &point, const DartType &dart)
	Checks if point is inside the triangle associated with dart.
template<class TraitsType , class PointType , class DartType >
bool	inTriangle (const PointType &point, const DartType &dart)
	Checks if point is inside the triangle associated with dart.
template<class DartType , class DartListType >
void	getBoundary (const DartType &dart, DartListType &boundary)
	Gets the boundary as sequence of darts, where the edges associated with the darts are boundary edges, given a dart with an associating edge at the boundary of a topology structure.
template<class DartType >
bool	isBoundaryEdge (const DartType &dart)
	Checks if the edge associated with dart is at the boundary of the triangulation.
template<class DartType >
bool	isBoundaryFace (const DartType &dart)
	Checks if the face associated with dart is at the boundary of the triangulation.
template<class DartType >
bool	isBoundaryNode (const DartType &dart)
	Checks if the node associated with dart is at the boundary of the triangulation.
template<class DartType >
int	getDegreeOfNode (const DartType &dart)
	Returns the degree of the node associated with dart.
template<class DartType , class DartListType >
void	get_0_orbit_interior (const DartType &dart, DartListType &orbit)
	Gets the 0-orbit around an interior node.
template<class DartType , class DartListType >
void	get_0_orbit_boundary (const DartType &dart, DartListType &orbit)
	Gets the 0-orbit around a node at the boundary.
template<class DartType >
bool	same_0_orbit (const DartType &d1, const DartType &d2)
	Checks if the two darts belong to the same 0-orbit, i.e., if they share a node.
template<class DartType >
bool	same_1_orbit (const DartType &d1, const DartType &d2)
	Checks if the two darts belong to the same 1-orbit, i.e., if they share an edge.
template<class DartType >
bool	same_2_orbit (const DartType &d1, const DartType &d2)
	Checks if the two darts belong to the same 2-orbit, i.e., if they lie in the same triangle.
template<class TraitsType , class DartType >
bool	swappableEdge (const DartType &dart, bool allowDegeneracy)
	Checks if the edge associated with dart is swappable, i.e., if the edge is a diagonal in a strictly convex (or convex) quadrilateral.
template<class DartType >
void	positionAtNextBoundaryEdge (DartType &dart)
	Given a dart, CCW or CW, positioned in a 0-orbit at the boundary of a tessellation.
template<class TraitsType , class DartType >
bool	convexBoundary (const DartType &dart)
	Checks if the boundary of a triangulation is convex.
template<class TopologyElementType , class DartType >
bool	isMemberOfFace (const TopologyElementType &topologyElement, const DartType &dart)
template<class TraitsType , class NodeType , class DartType >
bool	locateFaceWithNode (const NodeType &node, DartType &dart_iter)
template<class DartType >
void	getAdjacentTriangles (const DartType &dart, DartType &t1, DartType &t2, DartType &t3)
template<class DartType >
void	getNeighborNodes (const DartType &dart, list< DartType > &node_list, bool &boundary)
template<class TraitsType , class DartType >
bool	degenerateTriangle (const DartType &dart)
Utilities for Delaunay Triangulation

template<class TraitsType , class DartType , class DartListType >
void	optimizeDelaunay (DartListType &elist)
	Optimizes the edges in the given sequence according to the Delaunay criterion, i.e., such that the edge will fullfill the circumcircle criterion (or equivalently the MaxMin angle criterion) with respect to the quadrilaterals where they are diagonals.
template<class TraitsType , class DartType , class DartListType >
void	optimizeDelaunay (DartListType &elist, const typename DartListType::iterator end)
template<class TraitsType , class DartType >
bool	swapTestDelaunay (const DartType &dart, bool cycling_check)
	Checks if the edge associated with dart should be swapped according to the Delaunay criterion, i.e., the circumcircle criterion (or equivalently the MaxMin angle criterion).
template<class TraitsType , class DartType >
void	recSwapDelaunay (DartType &diagonal)
	Recursively swaps edges in the triangulation according to the Delaunay criterion.
template<class TraitsType , class DartType , class ListType >
void	swapEdgesAwayFromInteriorNode (DartType &dart, ListType &swapped_edges)
	Swaps edges away from the (interior) node associated with dart such that that exactly three edges remain incident with the node.
template<class TraitsType , class DartType , class ListType >
void	swapEdgesAwayFromBoundaryNode (DartType &dart, ListType &swapped_edges)
	Swaps edges away from the (boundary) node associated with dart in such a way that when removing the edges that remain incident with the node, the boundary of the triangulation will be convex.
template<class TraitsType , class DartType , class DartListType >
void	swapEdgeInList (const typename DartListType::iterator &it, DartListType &elist)
	Swap the the edge associated with iterator it and update affected darts in elist accordingly.
Constrained (Delaunay) Triangulation

template<class TraitsType , class DartType >
DartType	insertConstraint (DartType &dstart, DartType &dend, bool optimize_delaunay)
	Inserts a constrained edge between two existing nodes in a triangulation.

Detailed Description

Main interface to TTL.

This namespace contains the basic generic algorithms for the TTL, the Triangulation Template Library.

Examples of functionality are:

Incremental Delaunay triangulation
Constrained triangulation
Insert/remove nodes and constrained edges
Traversal operations
Misc. queries for extracting information for visualisation systems etc.

General requirements and assumptions:

DartType and TraitsType should be implemented in accordance with the description in Application Programming Interface to TTL (API).
A "Requires:" section in the documentation of a function template shows which functionality is required in TraitsType to support that specific function.
Functionalty required in DartType is the same (almost) for all function templates; see Application Programming Interface to TTL (API) and the example referred to.
When a reference to a dart object is passed to a function in TTL, it is assumed that it is oriented counterclockwise (CCW) in a triangle unless it is explicitly mentioned that it can also be clockwise (CW). The same applies for a dart that is passed from a function in TTL to the users TraitsType class (or struct).
When an edge (represented with a dart) is swapped, it is assumed that darts outside the quadrilateral where the edge is a diagonal are not affected by the swap. Thus, TraitsType::swapEdge must be implemented in accordance with this rule.

Glossary:

General terms are explained in Application Programming Interface to TTL (API).
CCW - counterclockwise
CW - clockwise
0_orbit, 1_orbit and 2_orbit: A sequence of darts around a node, around an edge and in a triangle respectively; see ttl::get_0_orbit_interior and ttl::get_0_orbit_boundary
arc - In a triangulation an arc is equivalent with an edge

See also:: ttl_util and Application Programming Interface to TTL (API)

Author:: �yvind Hjelle, oyvindhj@ifi.uio.no

Function Documentation

template<class TraitsType , class DartType >

bool ttl::convexBoundary ( const DartType & dart ) [inline]

Checks if the boundary of a triangulation is convex.

Parameters:

dart

A CCW dart at the boundary of the triangulation

TraitsType::crossProduct2d (const Dart&, const Dart&)

Definition at line 1355 of file ttl.h.

References ttl_util::crossProduct2d(), and getBoundary().

01356 01357 01358 01359 01360 01361 01362 01363 01364     ++bit; 01365 01366 01367 01368 01369 01370 01371 01372 01373 01374       } 01375 01376     } 01377 01378 01379 01380 01381 01382 01383 01384     } 01385 01386 01387 01388 01389 01390   }

class="fragment">01355 { list<DartType> blist; ttl::getBoundary(dart, blist); int no; no = blist.size(); typename list<DartType>::const_iterator bit = blist.begin(); DartType d1 = *bit; DartType d2; bool convex = true; for (; bit != blist.end(); ++bit) { d2 = *bit; double crossProd = TraitsType::crossProduct2d(d1, d2); if (crossProd < 0.0) { //cout << "!!! Boundary is NOT convex: crossProd = " << crossProd << endl; convex = false; return convex; d1 = d2; // Check the last angle d2 = *blist.begin(); double crossProd = TraitsType::crossProduct2d(d1, d2); if (crossProd < 0.0) { //cout << "!!! Boundary is NOT convex: crossProd = " << crossProd << endl; convex = false; //if (convex) // cout << "\n---> Boundary is convex\n" << endl; //cout << endl; return convex;

template<class TraitsType , class DartType >

bool ttl::degenerateTriangle ( const DartType & dart ) [inline]

Definition at line 1249 of file ttl.h.

References ttl_util::crossProduct2d().

01249                                                   {
01250     
01251     // Check if triangle is degenerate
01252     // Assumes CCW dart
01253     
01254     DartType d1 = dart;
01255     DartType d2 = d1;
01256     d2.alpha1();
01257     if (TraitsType::crossProduct2d(d1,d2) == 0)
01258       return true;
01259     
01260     return false;
01261   }

template<class DartType , class DartListType >

void ttl::get_0_orbit_boundary	(	const DartType &	dart,
		DartListType &	orbit
	)			`[inline]`

Gets the 0-orbit around a node at the boundary.

Parameters:

dart

A dart (CCW or CW) positioned at a boundary node and at a boundary edge.

Return values:

orbit

Sequence of darts with one orbit for each arc. All the darts, exept the last one, have the same orientation (CCW or CW) as dart, and dart is the first element in the sequence.

DartListType::push_back (DartType&)

Note:

The last dart in the sequence have opposite orientation compared to the others!

See also:: ttl::get_0_orbit_interior

Definition at line 1158 of file ttl.h.

01158                                                                          {
01159     
01160     DartType dart_prev;
01161     DartType d_iter = dart;
01162     do {
01163       orbit.push_back(d_iter);
01164       d_iter.alpha1();
01165       dart_prev = d_iter;
01166       d_iter.alpha2();
01167     } while (d_iter != dart_prev);
01168     
01169     orbit.push_back(d_iter); // the last one with opposite orientation
01170   }

template<class DartType , class DartListType >

void ttl::get_0_orbit_interior	(	const DartType &	dart,
		DartListType &	orbit
	)			`[inline]`

Gets the 0-orbit around an interior node.

Parameters:

dart

A dart (CCW or CW) positioned at an interior node.

Return values:

orbit

Sequence of darts with one orbit for each arc. All the darts have the same orientation (CCW or CW) as dart, and dart is the first element in the sequence.

DartListType::push_back (DartType&)

See also:: ttl::get_0_orbit_boundary

Definition at line 1124 of file ttl.h.

01124                                                                          {
01125     
01126     DartType d_iter = dart;
01127     orbit.push_back(d_iter);
01128     d_iter.alpha1().alpha2();
01129     
01130     while (d_iter != dart) {
01131       orbit.push_back(d_iter);
01132       d_iter.alpha1().alpha2();
01133     }
01134   }

template<class DartType >

void ttl::getAdjacentTriangles	(	const DartType &	dart,
		DartType &	t1,
		DartType &	t2,
		DartType &	t3
	)			`[inline]`

Definition at line 831 of file ttl.h.

00831                                                                                               {
00832     
00833     DartType dart_iter = dart;
00834     
00835     // add first
00836     if (dart_iter.alpha2() != dart) {
00837       t1 = dart_iter;
00838       dart_iter = dart;
00839     }
00840     
00841     // add second
00842     dart_iter.alpha0();
00843     dart_iter.alpha1();
00844     DartType dart_prev = dart_iter;
00845     if ((dart_iter.alpha2()) != dart_prev) {
00846       t2 = dart_iter;
00847       dart_iter = dart_prev;
00848     }
00849     
00850     // add third
00851     dart_iter.alpha0();
00852     dart_iter.alpha1();
00853     dart_prev = dart_iter;
00854     if ((dart_iter.alpha2()) != dart_prev)
00855       t3 = dart_iter;
00856   }

template<class DartType , class DartListType >

void ttl::getBoundary	(	const DartType &	dart,
		DartListType &	boundary
	)			`[inline]`

Gets the boundary as sequence of darts, where the edges associated with the darts are boundary edges, given a dart with an associating edge at the boundary of a topology structure.

The first dart in the sequence will be the given one, and the others will have the same orientation (CCW or CW) as the first. Assumes that the given dart is at the boundary.

Parameters:

	dart	A dart at the boundary (CCW or CW)
	boundary	A sequence of darts, where the associated edges are the boundary edges

DartListType::push_back (DartType&)

Definition at line 876 of file ttl.h.

References positionAtNextBoundaryEdge().

Referenced by convexBoundary().

00876                                                                    {
00877     // assumes the given dart is at the boundary (by edge)
00878     
00879     DartType dart_iter(dart);
00880     boundary.push_back(dart_iter); // Given dart as first element
00881     dart_iter.alpha0();
00882     positionAtNextBoundaryEdge(dart_iter);
00883     
00884     while (dart_iter != dart) {
00885       boundary.push_back(dart_iter);
00886       dart_iter.alpha0();
00887       positionAtNextBoundaryEdge(dart_iter);
00888     }
00889   }

template<class DartType >

int ttl::getDegreeOfNode ( const DartType & dart ) [inline]

Returns the degree of the node associated with dart.

Definition:: The degree (or valency) of a node V in a triangulation, is defined as the number of edges incident with V, i.e., the number of edges joining V with another node in the triangulation.

Definition at line 999 of file ttl.h.

Referenced by swapEdgesAwayFromInteriorNode().

00999                                               {
01000     
01001     DartType dart_iter(dart);
01002     DartType dart_prev;
01003     
01004     // If input dart is reached again, then interior node
01005     // If alpha2(d)=d, then boundary
01006     
01007     int degree = 0;
01008     bool boundaryVisited = false;
01009     do {
01010       dart_iter.alpha1();
01011       degree++;
01012       dart_prev = dart_iter;
01013       
01014       dart_iter.alpha2();
01015       
01016       if (dart_iter == dart_prev) {
01017         if (!boundaryVisited) {
01018           boundaryVisited = true;
01019           // boundary is reached first time, count in the reversed direction
01020           degree++; // count the start since it is not done above
01021           dart_iter = dart;
01022           dart_iter.alpha2();
01023         }
01024         else
01025           return degree;
01026       }
01027       
01028     } while (dart_iter != dart);
01029     
01030     return degree;
01031   }

template<class DartType >

void ttl::getNeighborNodes	(	const DartType &	dart,
		list< DartType > &	node_list,
		bool &	boundary
	)			`[inline]`

Definition at line 1059 of file ttl.h.

01059                                                                                            {
01060     
01061     DartType dart_iter(dart);
01062     
01063     dart_iter.alpha0(); // position the dart at an opposite node
01064     
01065     DartType dart_prev = dart_iter;
01066     
01067     bool start_at_boundary = false;
01068     dart_iter.alpha2();
01069     if (dart_iter == dart_prev)
01070       start_at_boundary = true;
01071     else
01072       dart_iter = dart_prev; // back again 
01073     
01074     DartType dart_start = dart_iter;
01075     
01076     do {
01077       node_list.push_back(dart_iter);
01078       dart_iter.alpha1();
01079       dart_iter.alpha0();
01080       dart_iter.alpha1();
01081       dart_prev = dart_iter;
01082       dart_iter.alpha2();
01083       if (dart_iter == dart_prev) {
01084         // boundary reached
01085         boundary = true;
01086         if (start_at_boundary == true) {
01087           // add the dart which now is positioned at the opposite boundary
01088           node_list.push_back(dart_iter);
01089           return;
01090         }
01091         else {
01092           // call the function again such that we start at the boundary
01093           // first clear the list and reposition to the initial node
01094           dart_iter.alpha0();
01095           node_list.clear();
01096           getNeighborNodes(dart_iter, node_list, boundary);
01097           return; // after one recursive step
01098         }
01099       }
01100     } while (dart_iter != dart_start);
01101     
01102     boundary = false;
01103   }

template<class TraitsType , class DartType >

DartType ttl::insertConstraint	(	DartType &	dstart,
		DartType &	dend,
		bool	optimize_delaunay
	)			`[inline]`

Inserts a constrained edge between two existing nodes in a triangulation.

If the constraint falls on one or more existing nodes and this is detected by the predicate TraitsType::orient2d, which should return zero in this case, the constraint is split. Otherwise a degenerate triangle will be made along the constraint.

Parameters:

	dstart	A CCW dart with the start node of the constraint as the source node
	dend	A CCW dart with the end node of the constraint as the source node
	optimize_delaunay	If set to `true`, the resulting triangulation will be a constrained Delaunay triangulation. If set to `false`, the resulting triangulation will not necessarily be of constrained Delaunay type.

Return values:

DartType

A dart representing the constrained edge.

TraitsType::orient2d (DartType&, DartType&, PointType&)
TraitsType::swapEdge (DartType&)

ttl::optimizeDelaunay if optimize_delaunay is set to true

Assumes:

The constrained edge must be inside the existing triangulation (and it cannot cross the boundary of the triangulation).

Definition at line 543 of file ttl_constr.h.

References same_0_orbit().

00543                                                                                         {
00544     
00545     // Assumes:
00546     // - It is the users responsibility to avoid crossing constraints
00547     // - The constraint cannot cross the boundary, i.e., the boundary must be
00548     //   convex in the area of crossing edges.
00549     // - dtart and dend are preserved (same node associated.)
00550     
00551 
00552     // Find edges crossing the constraint and put them in elist.
00553     // If findCrossingEdges reaches a Node lying on the constraint, this function 
00554     // calls itself recursively. 
00555 
00556     // RECURSION
00557     list<DartType> elist;
00558     DartType next_start = ttl_constr::findCrossingEdges<TraitsType>(dstart, dend, elist);
00559 
00560     // If there are no crossing edges (elist is empty), we assume that the constraint
00561     // is an existing edge.
00562     // In this case, findCrossingEdges returns the constraint.
00563     // Put the constraint in the list to fit with the procedures below
00564     // (elist can also be empty in the case of invalid input data (the constraint is in
00565     // a non-convex area) but this is the users responsibility.)
00566 
00567     //by Thomas Sevaldrud   if (elist.size() == 0)
00568     //by Thomas Sevaldrud   elist.push_back(next_start);
00569 
00570     // findCrossingEdges stops if it finds a node lying on the constraint.
00571     // A dart with this node as start node is returned
00572     // We call insertConstraint recursivly until the received dart is dend
00573     if (!ttl::same_0_orbit(next_start, dend)) {
00574 
00575 #ifdef DEBUG_TTL_CONSTR_PLOT
00576       cout << "RECURSION due to collinearity along constraint" << endl;
00577 #endif
00578 
00579       insertConstraint<TraitsType,DartType>(next_start, dend, optimize_delaunay);
00580     }
00581     
00582     // Swap edges such that the constraint edge is present in the transformed triangulation.
00583     if (elist.size() > 0) // by Thomas Sevaldrud
00584        ttl_constr::transformToConstraint<TraitsType>(dstart, next_start, elist);
00585     
00586 #ifdef DEBUG_TTL_CONSTR_PLOT
00587     cout << "size of elist = " << elist.size() << endl;
00588     if (elist.size() > 0) {
00589       DartType the_constraint = elist.back();
00590       ofile_constr << the_constraint.x() << " " << the_constraint.y() << " " << 0 << endl;
00591       the_constraint.alpha0();
00592       ofile_constr << the_constraint.x() << " " << the_constraint.y() << " " << 0 << endl << endl;
00593     }
00594 #endif
00595 
00596     // Optimize to constrained Delaunay triangulation if required.
00597     typename list<DartType>::iterator end_opt = elist.end();
00598     if (optimize_delaunay) {
00599 
00600       // Indicate that the constrained edge, which is the last element in the list,
00601       // should not be swapped
00602       --end_opt;
00603       ttl::optimizeDelaunay<TraitsType, DartType>(elist, end_opt);
00604     }
00605 
00606     if(elist.size() == 0) // by Thomas Sevaldrud
00607        return next_start; // by Thomas Sevaldrud
00608      
00609     // Return the constraint, which is still the last element in the list
00610     end_opt = elist.end();
00611     --end_opt;
00612     return *end_opt;
00613   }

template<class TraitsType , class DartType , class PointType >

bool ttl::insertNode	(	DartType &	dart,
		PointType &	point
	)			`[inline]`

Inserts a new node in an existing Delaunay triangulation and swaps edges to obtain a new Delaunay triangulation.

This is the basic function for incremental Delaunay triangulation. When starting from a set of points, an initial Delaunay triangulation can be created as two triangles forming a rectangle that contains all the points. After insertNode has been called repeatedly with all the points, ttl::removeRectangularBoundary can be called to remove triangles at the boundary of the triangulation so that the boundary form the convex hull of the points.

Note that this incremetal scheme will run much faster if the points have been sorted lexicographically on x and y.

Parameters:

	dart	An arbitrary CCW dart in the tringulation. Output: A CCW dart incident to the new node.
	point	A point (node) to be inserted in the triangulation.

Return values:

bool true if point was inserted; false if not.
If point is outside the triangulation, or the input dart is not valid, false is returned.

TraitsType::splitTriangle (DartType&, const PointType&)

Note:

For efficiency reasons dart should be close to the insertion point.

See also:: ttl::removeRectangularBoundary

Definition at line 268 of file ttl.h.

References isBoundaryEdge().

00268                                                       {
00269     
00270     bool found = ttl::locateTriangle<TraitsType>(point, dart);
00271     if (!found) {
00272 #ifdef DEBUG_TTL
00273       cout << "ERROR: Triangulation::insertNode: NO triangle found. /n";
00274 #endif
00275       return false;
00276     }
00277     
00278     // ??? can we hide the dart? this is not possible if one triangle only
00279     TraitsType::splitTriangle(dart, point);
00280     
00281     DartType d1 = dart;
00282     d1.alpha2().alpha1().alpha2().alpha0().alpha1();
00283     
00284     DartType d2 = dart;
00285     d2.alpha1().alpha0().alpha1();
00286     
00287     // Preserve a dart as output incident to the node and CCW
00288     DartType d3 = dart;
00289     d3.alpha2();
00290     dart = d3; // and see below
00291     //DartType dsav = d3;
00292     d3.alpha0().alpha1();
00293     
00294     //if (!TraitsType::fixedEdge(d1) && !ttl::isBoundaryEdge(d1)) {
00295     if (!ttl::isBoundaryEdge(d1)) {
00296       d1.alpha2();
00297       recSwapDelaunay<TraitsType>(d1);
00298     }
00299     
00300     //if (!TraitsType::fixedEdge(d2) && !ttl::isBoundaryEdge(d2)) {
00301     if (!ttl::isBoundaryEdge(d2)) {
00302       d2.alpha2();
00303       recSwapDelaunay<TraitsType>(d2);
00304     }
00305     
00306     // Preserve the incoming dart as output incident to the node and CCW
00307     //d = dsav.alpha2();
00308     dart.alpha2();
00309     //if (!TraitsType::fixedEdge(d3) && !ttl::isBoundaryEdge(d3)) {
00310     if (!ttl::isBoundaryEdge(d3)) {
00311       d3.alpha2();
00312       recSwapDelaunay<TraitsType>(d3);
00313     }
00314     
00315     return true;
00316   }

template<class TraitsType , class ForwardIterator , class DartType >

void ttl::insertNodes	(	ForwardIterator	first,
		ForwardIterator	last,
		DartType &	dart
	)			`[inline]`

Definition at line 322 of file ttl.h.

00322                                                                                   {
00323     
00324     // Assumes that the dereferenced point objects are pointers.
00325     // References to the point objects are then passed to TTL.
00326     
00327     ForwardIterator it;
00328     for (it = first; it != last; ++it) {
00329       bool status = insertNode<TraitsType>(dart, **it);
00330     }
00331   }

template<class TraitsType , class PointType , class DartType >

bool ttl::inTriangle	(	const PointType &	point,
		const DartType &	dart
	)			`[inline]`

Checks if point is inside the triangle associated with dart.

This function deals with degeneracy to some extent, but round-off errors may still lead to wrong result if the triangle is degenerate.

Parameters:

dart

A CCW dart in the triangle

TraitsType::crossProduct2d (DartType&, PointType&)
TraitsType::scalarProduct2d (DartType&, PointType&)

See also:: ttl::inTriangleSimplest

Definition at line 750 of file ttl.h.

References ttl_util::crossProduct2d(), and ttl_util::scalarProduct2d().

00750                                                                   {
00751     
00752     // SHOULD WE INCLUDE A STRATEGY WITH EDGE X e_1 ETC? TO GUARANTEE THAT
00753     // ONLY ON ONE EDGE? BUT THIS DOES NOT SOLVE PROBLEMS WITH
00754     // notInE1 && notInE1.neghbour ?
00755     
00756     
00757     // Returns true if inside (but not necessarily strictly inside)
00758     // Works for degenerate triangles, but not when all edges are degenerate,
00759     // and the point coincides with all nodes;
00760     // then false is always returned.
00761     
00762     typedef typename TraitsType::real_type real_type;
00763     
00764     DartType dart_iter = dart;
00765     
00766     real_type cr1 = TraitsType::crossProduct2d(dart_iter, point);
00767     if (cr1 < 0)
00768       return false;
00769     
00770     dart_iter.alpha0().alpha1();
00771     real_type cr2 = TraitsType::crossProduct2d(dart_iter, point);
00772     
00773     if (cr2 < 0)
00774       return false;
00775     
00776     dart_iter.alpha0().alpha1();
00777     real_type cr3 = TraitsType::crossProduct2d(dart_iter, point);
00778     if (cr3 < 0)
00779       return false;
00780     
00781     // All cross products are >= 0
00782     // Check for degeneracy
00783     
00784     if (cr1 != 0 || cr2 != 0 || cr3 != 0)
00785       return true; // inside non-degenerate face
00786     
00787     // All cross-products are zero, i.e. degenerate triangle, check if inside
00788     // Strategy: d.scalarProduct2d >= 0 && alpha0(d).d.scalarProduct2d >= 0 for one of
00789     // the edges. But if all edges are degenerate and the point is on (all) the nodes,
00790     // then "false is returned".
00791     
00792     DartType dart_tmp = dart_iter;
00793     real_type sc1 = TraitsType::scalarProduct2d(dart_tmp,point);
00794     real_type sc2 = TraitsType::scalarProduct2d(dart_tmp.alpha0(), point);
00795     
00796     if (sc1 >= 0 && sc2 >= 0) {
00797       // test for degenerate edge
00798       if (sc1 != 0 || sc2 != 0)
00799         return true; // interior to this edge or on a node (but see comment above)
00800     }
00801     
00802     dart_tmp = dart_iter.alpha0().alpha1();
00803     sc1 = TraitsType::scalarProduct2d(dart_tmp,point);
00804     sc2 = TraitsType::scalarProduct2d(dart_tmp.alpha0(),point);
00805     if (sc1 >= 0 && sc2 >= 0) {
00806       // test for degenerate edge
00807       if (sc1 != 0 || sc2 != 0)
00808         return true; // interior to this edge or on a node (but see comment above)
00809     }
00810     
00811     dart_tmp = dart_iter.alpha1();
00812     sc1 = TraitsType::scalarProduct2d(dart_tmp,point);
00813     sc2 = TraitsType::scalarProduct2d(dart_tmp.alpha0(),point);
00814     if (sc1 >= 0 && sc2 >= 0) {
00815       // test for degenerate edge
00816       if (sc1 != 0 || sc2 != 0)
00817         return true; // interior to this edge or on a node (but see comment above)
00818     }
00819     
00820     // Not on any of the edges of the degenerate triangle.
00821     // The only possibility for the point to be "inside" is that all edges are degenerate
00822     // and the point coincide with all nodes. So false is returned in this case.
00823     
00824     return false;
00825   }

template<class TraitsType , class PointType , class DartType >

bool ttl::inTriangleSimplest	(	const PointType &	point,
		const DartType &	dart
	)			`[inline]`

Checks if point is inside the triangle associated with dart.

A fast and simple function that does not deal with degeneracy.

Parameters:

dart

A CCW dart in the triangle

TraitsType::orient2d (DartType&, DartType&, PointType&)

See also:: ttl::inTriangle for a more robust function

Definition at line 706 of file ttl.h.

00706                                                                           {
00707     
00708     // Fast and simple: Do not deal with degenerate faces, i.e., if there is
00709     // degeneracy, true will be returned if the point is on the extension of the
00710     // edges of a degenerate triangle
00711     
00712     DartType d_iter = dart;
00713     DartType d0 = d_iter;
00714     d0.alpha0();
00715     if (!TraitsType::orient2d(d_iter, d0, point) >= 0)
00716       return false;
00717     
00718     d_iter.alpha0().alpha1();
00719     d0 = d_iter;
00720     d0.alpha0();
00721     if (!TraitsType::orient2d(d_iter, d0, point) >= 0)
00722       return false;
00723     
00724     d_iter.alpha0().alpha1();
00725     d0 = d_iter;
00726     d0.alpha0();
00727     if (!TraitsType::orient2d(d_iter, d0, point) >= 0)
00728       return false;
00729     
00730     return true;
00731   }

template<class DartType >

bool ttl::isBoundaryEdge ( const DartType & dart ) [inline]

Checks if the edge associated with dart is at the boundary of the triangulation.

Implements:

   DartType dart_iter = dart;
   if (dart_iter.alpha2() == dart)
     return true;
   else
     return false;

Definition at line 922 of file ttl.h.

Referenced by insertNode(), recSwapDelaunay(), removeBoundaryNode(), swapEdgesAwayFromBoundaryNode(), swappableEdge(), and swapTestDelaunay().

00922                                               {
00923     
00924     DartType dart_iter = dart;
00925     if (dart_iter.alpha2() == dart)
00926       return true;
00927     else
00928       return false;
00929   }

template<class DartType >

bool ttl::isBoundaryFace ( const DartType & dart ) [inline]

Checks if the face associated with dart is at the boundary of the triangulation.

Definition at line 937 of file ttl.h.

00937                                               {
00938     
00939     // Strategy: boundary if alpha2(d)=d
00940     
00941     DartType dart_iter(dart);
00942     DartType dart_prev;
00943     
00944     do {
00945       dart_prev = dart_iter;
00946       
00947       if (dart_iter.alpha2() == dart_prev)
00948         return true;
00949       else
00950         dart_iter = dart_prev; // back again
00951       
00952       dart_iter.alpha0();
00953       dart_iter.alpha1();
00954       
00955     } while (dart_iter != dart);
00956     
00957     return false;
00958   }

template<class DartType >

bool ttl::isBoundaryNode ( const DartType & dart ) [inline]

Checks if the node associated with dart is at the boundary of the triangulation.

Definition at line 966 of file ttl.h.

Referenced by ttl_constr::getAtSmallestAngle(), removeNode(), and same_0_orbit().

00966                                               {
00967     
00968     // Strategy: boundary if alpha2(d)=d
00969     
00970     DartType dart_iter(dart);
00971     DartType dart_prev;
00972     
00973     // If input dart is reached again, then internal node
00974     // If alpha2(d)=d, then boundary
00975     
00976     do {
00977       dart_iter.alpha1();
00978       dart_prev = dart_iter;
00979       dart_iter.alpha2();
00980       
00981       if (dart_iter == dart_prev)
00982         return true;
00983       
00984     } while (dart_iter != dart);
00985     
00986     return false;
00987   }

template<class TopologyElementType , class DartType >

bool ttl::isMemberOfFace	(	const TopologyElementType &	topologyElement,
		const DartType &	dart
	)			`[inline]`

Definition at line 517 of file ttl.h.

Referenced by locateFaceWithNode().

00517                                                                                           {
00518     
00519     // Check if the given topology element (node, edge or face) is a member of the face
00520     // Assumes:
00521     // - DartType::isMember(TopologyElementType)
00522     
00523     DartType dart_iter = dart;
00524     do {
00525       if (dart_iter.isMember(topologyElement))
00526         return true;
00527       dart_iter.alpha0().alpha1();
00528     } while (dart_iter != dart);
00529     
00530     return false;
00531   }

template<class TraitsType , class PointType , class DartType >

bool ttl::locateFaceSimplest	(	const PointType &	point,
		DartType &	dart
	)			`[inline]`

Locates the face containing a given point.

It is assumed that the tessellation (e.g. a triangulation) is regular in the sense that there are no holes, the boundary is convex and there are no degenerate faces.

Parameters:

	point	A point to be located
	dart	An arbitrary CCW dart in the triangulation Output: A CCW dart in the located face

Return values:

bool true if a face is found; false if not.

TraitsType::orient2d (DartType&, DartType&, PointType&)

Note:

If false is returned, point may still be inside a face if the tessellation is not regular as explained above.

See also:: ttl::locateTriangle

Definition at line 587 of file ttl.h.

00587                                                                     {
00588     // Not degenerate triangles if point is on the extension of the edges
00589     // But inTriangle may be called in case of true (may update to inFace2)
00590     // Convex boundary
00591     // no holes
00592     // convex faces (works for general convex faces)
00593     // Not specialized for triangles, but ok?
00594     //
00595     // TraitsType::orint2d(PointType) is the half open half-plane defined
00596     // by the dart:
00597     // n1 = dart.node()
00598     // n2 = dart.alpha0().node
00599     // Only the following gives true:
00600     // ((n2->x()-n1->x())*(point.y()-n1->y()) >= (point.x()-n1->x())*(n2->y()-n1->y()))
00601     
00602     DartType dart_start;
00603     dart_start = dart;
00604     DartType dart_prev;
00605     
00606     DartType d0;
00607     for (;;) {
00608       d0 = dart;
00609       d0.alpha0();
00610       if (TraitsType::orient2d(dart, d0, point) >= 0) {
00611         dart.alpha0().alpha1();
00612         if (dart == dart_start)
00613           return true; // left to all edges in face
00614       }
00615       else {
00616         dart_prev = dart;
00617         dart.alpha2();
00618         if (dart == dart_prev)
00619           return false; // iteration to outside boundary
00620         
00621         dart_start = dart;
00622         dart_start.alpha0();
00623         
00624         dart.alpha1(); // avoid twice on same edge and ccw in next
00625       }
00626     }
00627   }

template<class TraitsType , class NodeType , class DartType >

bool ttl::locateFaceWithNode	(	const NodeType &	node,
		DartType &	dart_iter
	)			`[inline]`

Definition at line 537 of file ttl.h.

References isMemberOfFace().

00537                                                                        {
00538     // Locate a face in the topology structure with the given node as a member
00539     // Assumes:
00540     // - TraitsType::orient2d(DartType, DartType, NodeType)
00541     // - DartType::isMember(NodeType)
00542     // - Note that if false is returned, the node might still be in the
00543     //   topology structure. Application programmer
00544     //   should check all if by hypothesis the node is in the topology structure;
00545     //   see doc. on locateTriangle. 
00546     
00547     bool status = locateFaceSimplest<TraitsType>(node, dart_iter);
00548     if (status == false)
00549       return status;
00550     
00551     // True was returned from locateFaceSimplest, but if the located triangle is
00552     // degenerate and the node is on the extension of the edges,
00553     // the node might still be inside. Check if node is a member and return false
00554     // if not. (Still the node might be in the topology structure, see doc. above
00555     // and in locateTriangle(const PointType& point, DartType& dart_iter)
00556     
00557     return isMemberOfFace(node, dart_iter);
00558   }

template<class TraitsType , class PointType , class DartType >

bool ttl::locateTriangle	(	const PointType &	point,
		DartType &	dart
	)			`[inline]`

Locates the triangle containing a given point.

It is assumed that the triangulation is regular in the sense that there are no holes and the boundary is convex. This function deals with degeneracy to some extent, but round-off errors may still lead to a wrong result if triangles are degenerate.

Parameters:

	point	A point to be located
	dart	An arbitrary CCW dart in the triangulation Output: A CCW dart in the located triangle

Return values:

bool true if a triangle is found; false if not.
If point is outside the triangulation, in which case false is returned, then the edge associated with dart will be at the boundary of the triangulation.

Definition at line 654 of file ttl.h.

00654                                                                 {
00655     // The purpose is to have a fast and stable procedure that
00656     //  i) avoids concluding that a point is inside a triangle if it is not inside
00657     // ii) avoids infinite loops
00658     
00659     // Thus, if false is returned, the point might still be inside a triangle in
00660     // the triangulation. But this will probably only occur in the following cases:
00661     //  i) There are holes in the triangulation which causes the procedure to stop.
00662     // ii) The boundary of the triangulation is not convex.
00663     // ii) There might be degenerate triangles interior to the triangulation, or on the
00664     //     the boundary, which in some cases might cause the procedure to stop there due
00665     //     to the logic of the algorithm.
00666     
00667     // It is the application programmer's responsibility to check further if false is
00668     // returned. For example, if by hypothesis the point is inside a triangle
00669     // in the triangulation and and false is returned, then all triangles in the
00670     // triangulation should be checked by the application. This can be done using
00671     // the function:
00672     // bool inTriangle(const PointType& point, const DartType& dart).
00673     
00674     
00675     // Assumes:
00676     // - crossProduct2d, scalarProduct2d etc., see functions called
00677     
00678     bool status = locateFaceSimplest<TraitsType>(point, dart);
00679     if (status == false)
00680       return status;
00681     
00682     // There may be degeneracy, i.e., the point might be outside the triangle
00683     // on the extension of the edges of a degenerate triangle.
00684     
00685     // The next call returns true if inside a non-degenerate or a degenerate triangle,
00686     // but false if the point coincides with the "supernode" in the case where all
00687     // edges are degenerate.
00688     return inTriangle<TraitsType>(point, dart);
00689   }

template<class TraitsType , class DartType , class DartListType >

void ttl::optimizeDelaunay	(	DartListType &	elist,
		const typename DartListType::iterator	end
	)			`[inline]`

Definition at line 1428 of file ttl.h.

01428                                                                                         {
01429     
01430     // CCW darts
01431     // Optimize here means Delaunay, but could be any criterion by
01432     // requiring a "should swap" in the traits class, or give
01433     // a function object?
01434     // Assumes that elist has only one dart for each arc.
01435     // Darts outside the quadrilateral are preserved
01436     
01437     // For some data structures it is possible to preserve
01438     // all darts when swapping. Thus a preserve_darts_when swapping
01439     // ccould be given to indicate this and we would gain performance by avoiding
01440     // find in list.
01441     
01442     // Requires that swap retuns a dart in the "same position when rotated CCW"
01443     // (A vector instead of a list may be better.)
01444     
01445     // First check that elist is not empty
01446     if (elist.empty())
01447         return;
01448 
01449     // Avoid cycling by more extensive circumcircle test
01450     bool cycling_check = true;
01451     bool optimal = false;
01452     typename DartListType::iterator it;
01453 
01454     typename DartListType::iterator end_opt = end;
01455 
01456     // Hmm... The following code is trying to derefence an iterator that may
01457     // be invalid. This may lead to debug error on Windows, so we comment out
01458     // this code. Checking elist.empty() above will prevent some
01459     // problems...
01460     //
01461     // last_opt is passed the end of the "active list"
01462     //typename DartListType::iterator end_opt;
01463     //if (*end != NULL)
01464     //  end_opt = end;
01465     //else
01466     //  end_opt = elist.end();
01467 
01468     while(!optimal) {
01469       optimal = true;
01470       for (it = elist.begin(); it != end_opt; ++it) {
01471         if (ttl::swapTestDelaunay<TraitsType>(*it, cycling_check)) {
01472 
01473           // Preserve darts. Potential darts in the list are:
01474           // - The current dart
01475           // - the four CCW darts on the boundary of the quadrilateral
01476           // (the current arc has only one dart)
01477           
01478           ttl::swapEdgeInList<TraitsType, DartType>(it, elist);
01479           
01480           optimal = false;
01481         } // end if should swap
01482       } // end for
01483     } // end pass
01484   }

template<class TraitsType , class DartType , class DartListType >

void ttl::optimizeDelaunay ( DartListType & elist ) [inline]

Optimizes the edges in the given sequence according to the Delaunay criterion, i.e., such that the edge will fullfill the circumcircle criterion (or equivalently the MaxMin angle criterion) with respect to the quadrilaterals where they are diagonals.

Parameters:

elist

The sequence of edges

TraitsType::swapEdge (DartType& dart)
Note: Must be implemented such that dart is delivered back in a position as seen if it was glued to the edge when swapping (rotating) the edge CCW

ttl::swapTestDelaunay

Definition at line 1421 of file ttl.h.

01421                                                {
01422       optimizeDelaunay<TraitsType, DartType, DartListType>(elist, elist.end());
01423   }

template<class DartType >

void ttl::positionAtNextBoundaryEdge ( DartType & dart ) [inline]

Given a dart, CCW or CW, positioned in a 0-orbit at the boundary of a tessellation.

Position dart at a boundary edge in the same 0-orbit.
If the given dart is CCW, dart is positioned at the left boundary edge and will be CW.
If the given dart is CW, dart is positioned at the right boundary edge and will be CCW.

Note:

The given dart must have a source node at the boundary, otherwise an infinit loop occurs.

Definition at line 1330 of file ttl.h.

Referenced by ttl_constr::getAtSmallestAngle(), getBoundary(), removeBoundaryNode(), removeRectangularBoundary(), same_0_orbit(), and swapEdgesAwayFromBoundaryNode().

01330                                                     {
01331     
01332     DartType dart_prev;
01333     
01334     // If alpha2(d)=d, then boundary
01335     
01336     //old convention: dart.alpha0();
01337     do {
01338       dart.alpha1();
01339       dart_prev = dart;
01340       dart.alpha2();
01341     } while (dart != dart_prev);
01342   }

template<class TraitsType , class DartType >

void ttl::recSwapDelaunay ( DartType & diagonal ) [inline]

Recursively swaps edges in the triangulation according to the Delaunay criterion.

Parameters:

diagonal

A CCW dart representing the edge where the recursion starts from.

TraitsType::swapEdge (DartType&)
Note: Must be implemented such that the darts outside the quadrilateral are not affected by the swap.

Calls itself recursively

Definition at line 1617 of file ttl.h.

References isBoundaryEdge().

01617                                              {
01618 
01619     if (!ttl::swapTestDelaunay<TraitsType>(diagonal))
01620       // ??? ttl::swapTestDelaunay also checks if boundary, so this can be optimized
01621       return;
01622     
01623     // Get the other "edges" of the current triangle; see illustration above.
01624     DartType oppEdge1 = diagonal;    
01625     oppEdge1.alpha1();
01626     bool b1;
01627     if (ttl::isBoundaryEdge(oppEdge1))
01628       b1 = true;
01629     else {
01630       b1 = false;
01631       oppEdge1.alpha2();
01632     }
01633     
01634     
01635     DartType oppEdge2 = diagonal;
01636     oppEdge2.alpha0().alpha1().alpha0();
01637     bool b2;
01638     if (ttl::isBoundaryEdge(oppEdge2))
01639       b2 = true;
01640     else {
01641       b2 = false;
01642       oppEdge2.alpha2();
01643     }
01644     
01645     // Swap the given diagonal
01646     TraitsType::swapEdge(diagonal);
01647     
01648     if (!b1)
01649       recSwapDelaunay<TraitsType>(oppEdge1);
01650     if (!b2)
01651       recSwapDelaunay<TraitsType>(oppEdge2);
01652   }

template<class TraitsType , class DartType >

void ttl::removeBoundaryNode ( DartType & dart ) [inline]

Removes the boundary node associated with dart and updates the triangulation to be Delaunay.

TraitsType::removeBoundaryTriangle (Dart&)

Definition at line 402 of file ttl.h.

References isBoundaryEdge(), and positionAtNextBoundaryEdge().

00402                                             {
00403     
00404     // ... and update Delaunay
00405     // - CCW dart must be given (for remove)
00406     // - No dart is delivered back now (but this is possible if
00407     //   we assume that there is not only one triangle left in the triangulation.
00408         
00409     // Position at boundary edge and CCW
00410     if (!ttl::isBoundaryEdge(dart)) {
00411       dart.alpha1(); // ensures that next function delivers back a CCW dart (if the given dart is CCW)
00412       ttl::positionAtNextBoundaryEdge(dart);
00413     }
00414 
00415     list<DartType> swapped_edges;
00416     ttl::swapEdgesAwayFromBoundaryNode<TraitsType>(dart, swapped_edges);
00417     
00418     // Remove boundary triangles and remove the new boundary from the list
00419     // of swapped edges, see below.
00420     DartType d_iter = dart;
00421     DartType dnext = dart;
00422     bool bend = false;
00423     while (bend == false) {
00424       dnext.alpha1().alpha2();
00425       if (ttl::isBoundaryEdge(dnext))
00426         bend = true; // Stop when boundary
00427       
00428       // Generic: Also remove the new boundary from the list of swapped edges
00429       DartType n_bedge = d_iter;
00430       n_bedge.alpha1().alpha0().alpha1().alpha2(); // new boundary edge
00431       
00432       // ??? can we avoid find if we do this in swap away?
00433       typename list<DartType>::iterator it;
00434       it = find(swapped_edges.begin(), swapped_edges.end(), n_bedge);
00435       
00436       if (it != swapped_edges.end())
00437         swapped_edges.erase(it);
00438       
00439       // Remove the boundary triangle
00440       TraitsType::removeBoundaryTriangle(d_iter);
00441       d_iter = dnext;
00442     }
00443     
00444     // Optimize Delaunay
00445     typedef list<DartType> DartListType;
00446     ttl::optimizeDelaunay<TraitsType, DartType, DartListType>(swapped_edges);
00447   }

template<class TraitsType , class DartType >

void ttl::removeInteriorNode ( DartType & dart ) [inline]

Removes the interior node associated with dart and updates the triangulation to be Delaunay.

TraitsType::reverse_splitTriangle (Dart&)

Note:

The node cannot belong to a fixed (constrained) edge that is not swappable. (An endless loop is likely to occur in this case).

Definition at line 466 of file ttl.h.

00466                                             {
00467     
00468     // ... and update to Delaunay.
00469     // Must allow degeneracy temporarily, see comments in swap edges away
00470     // Assumes:
00471     // - revese_splitTriangle does not affect darts
00472     //   outside the resulting triangle.
00473     
00474     // 1) Swaps edges away from the node until degree=3 (generic)
00475     // 2) Removes the remaining 3 triangles and creates a new to fill the hole
00476     //    unsplitTriangle which is required
00477     // 3) Runs LOP on the platelet to obtain a Delaunay triangulation
00478     // (No dart is delivered as output)
00479     
00480     // Assumes dart is counterclockwise
00481     
00482     list<DartType> swapped_edges;
00483     ttl::swapEdgesAwayFromInteriorNode<TraitsType>(dart, swapped_edges);
00484     
00485     // The reverse operation of split triangle:
00486     // Make one triangle of the three triangles at the node associated with dart
00487     // TraitsType::
00488     TraitsType::reverse_splitTriangle(dart);
00489     
00490     // ???? Not generic yet if we are very strict:
00491     // When calling unsplit triangle, darts at the three opposite sides may
00492     // change!
00493     // Should we hide them longer away??? This is possible since they cannot
00494     // be boundary edges.
00495     // ----> Or should we just require that they are not changed???
00496     
00497     // Make the swapped-away edges Delaunay.
00498     // Note the theoretical result: if there are no edges in the list,
00499     // the triangulation is Delaunay already
00500     
00501     ttl::optimizeDelaunay<TraitsType, DartType>(swapped_edges);
00502   }

template<class TraitsType , class DartType >

void ttl::removeNode ( DartType & dart ) [inline]

Removes the node associated with dart and updates the triangulation to be Delaunay.

ttl::removeBoundaryNode if dart represents a node at the boundary
ttl::removeInteriorNode if dart represents an interior node

Note:

The node cannot belong to a fixed (constrained) edge that is not swappable. (An endless loop is likely to occur in this case).

Definition at line 381 of file ttl.h.

References isBoundaryNode().

00381                                     {
00382     
00383     if (ttl::isBoundaryNode(dart))
00384       ttl::removeBoundaryNode<TraitsType>(dart);
00385     else
00386       ttl::removeInteriorNode<TraitsType>(dart);
00387   }

template<class TraitsType , class DartType >

void ttl::removeRectangularBoundary ( DartType & dart ) [inline]

Removes the rectangular boundary of a triangulation as a final step of an incremental Delaunay triangulation.

The four nodes at the corners will be removed and the resulting triangulation will have a convex boundary and be Delaunay.

Parameters:

dart

A CCW dart at the boundary of the triangulation
Output: A CCW dart at the new boundary

ttl::removeBoundaryNode

Note:

This function requires that the boundary of the triangulation is a rectangle with four nodes (one in each corner).

Definition at line 352 of file ttl.h.

References positionAtNextBoundaryEdge().

00352                                                    {
00353     
00354     DartType d_next = dart;
00355     DartType d_iter;
00356     
00357     for (int i = 0; i < 4; i++) {
00358       d_iter = d_next;
00359       d_next.alpha0();
00360       ttl::positionAtNextBoundaryEdge(d_next);
00361       ttl::removeBoundaryNode<TraitsType>(d_iter);
00362     }
00363     
00364     dart = d_next; // Return a dart at the new boundary
00365   }

template<class DartType >

bool ttl::same_0_orbit	(	const DartType &	d1,
		const DartType &	d2
	)			`[inline]`

Checks if the two darts belong to the same 0-orbit, i.e., if they share a node.

d1 and/or d2 can be CCW or CW.

(This function also examines if the the node associated with d1 is at the boundary, which slows down the function (slightly). If it is known that the node associated with d1 is an interior node and a faster version is needed, the user should implement his/her own version.)

Definition at line 1185 of file ttl.h.

References isBoundaryNode(), and positionAtNextBoundaryEdge().

Referenced by insertConstraint(), and ttl_constr::isTheConstraint().

01185                                                               {
01186     
01187     // Two copies of the same dart
01188     DartType d_iter = d2;
01189     DartType d_end = d2;
01190     
01191     if (ttl::isBoundaryNode(d_iter)) {
01192       // position at both boundary edges
01193       ttl::positionAtNextBoundaryEdge(d_iter);
01194       d_end.alpha1();
01195       ttl::positionAtNextBoundaryEdge(d_end);
01196     }
01197     
01198     for (;;) {
01199       if (d_iter == d1)
01200         return true;
01201       d_iter.alpha1();
01202       if (d_iter == d1)
01203         return true;
01204       d_iter.alpha2();
01205       if (d_iter == d_end)
01206         break;
01207     }
01208     
01209     return false;
01210   }

template<class DartType >

bool ttl::same_1_orbit	(	const DartType &	d1,
		const DartType &	d2
	)			`[inline]`

Checks if the two darts belong to the same 1-orbit, i.e., if they share an edge.

d1 and/or d2 can be CCW or CW.

Definition at line 1219 of file ttl.h.

01219                                                               {
01220     
01221     DartType d_iter = d2;
01222     // (Also works at the boundary)
01223     if (d_iter == d1 || d_iter.alpha0() == d1 || d_iter.alpha2() == d1 || d_iter.alpha0() == d1)
01224       return true;
01225     return false;
01226   }

template<class DartType >

bool ttl::same_2_orbit	(	const DartType &	d1,
		const DartType &	d2
	)			`[inline]`

Checks if the two darts belong to the same 2-orbit, i.e., if they lie in the same triangle.

d1 and/or d2 can be CCW or CW

Definition at line 1235 of file ttl.h.

01235                                                               {
01236     
01237     DartType d_iter = d2;
01238     if (d_iter == d1 || d_iter.alpha0() == d1 ||
01239       d_iter.alpha1() == d1 || d_iter.alpha0() == d1 ||
01240       d_iter.alpha1() == d1 || d_iter.alpha0() == d1)
01241       return true;
01242     return false;
01243   }

template<class TraitsType , class DartType , class DartListType >

void ttl::swapEdgeInList	(	const typename DartListType::iterator &	it,
		DartListType &	elist
	)			`[inline]`

Swap the the edge associated with iterator it and update affected darts in elist accordingly.

The darts affected by the swap are those in the same quadrilateral. Thus, if one want to preserve one or more of these darts on should keep them in elist.

Definition at line 1829 of file ttl.h.

01829                                                                                       {
01830 
01831     typename DartListType::iterator it1, it2, it3, it4;
01832     DartType dart(*it);
01833     
01834     //typename TraitsType::DartType d1 = dart; d1.alpha2().alpha1();
01835     //typename TraitsType::DartType d2 =   d1; d2.alpha0().alpha1();
01836     //typename TraitsType::DartType d3 = dart; d3.alpha0().alpha1();
01837     //typename TraitsType::DartType d4 =   d3; d4.alpha0().alpha1();
01838     DartType d1 = dart; d1.alpha2().alpha1();
01839     DartType d2 =   d1; d2.alpha0().alpha1();
01840     DartType d3 = dart; d3.alpha0().alpha1();
01841     DartType d4 =   d3; d4.alpha0().alpha1();
01842     
01843     // Find pinters to the darts that may change.
01844     // ??? Note, this is not very efficient since we must use find, which is O(N),
01845     // four times.
01846     // - Solution?: replace elist with a vector of pair (dart,number)
01847     //   and avoid find?
01848     // - make a function for swapping generically?
01849     // - sould we use another container type or,
01850     // - erase them and reinsert?
01851     // - or use two lists?
01852     it1 = find(elist.begin(), elist.end(), d1);
01853     it2 = find(elist.begin(), elist.end(), d2);
01854     it3 = find(elist.begin(), elist.end(), d3);
01855     it4 = find(elist.begin(), elist.end(), d4);
01856     
01857     TraitsType::swapEdge(dart);
01858     // Update the current dart which may have changed
01859     *it = dart;
01860     
01861     // Update darts that may have changed again (if they were present)
01862     // Note that dart is delivered back after swapping
01863     if (it1 != elist.end()) {
01864       d1 = dart; d1.alpha1().alpha0();
01865       *it1 = d1;
01866     }
01867     if (it2 != elist.end()) {
01868       d2 = dart; d2.alpha2().alpha1();
01869       *it2 = d2;
01870     }
01871     if (it3 != elist.end()) {
01872       d3 = dart; d3.alpha2().alpha1().alpha0().alpha1();
01873       *it3 = d3;
01874     }
01875     if (it4 != elist.end()) {
01876       d4 = dart; d4.alpha0().alpha1();
01877       *it4 = d4;
01878     }
01879   }

template<class TraitsType , class DartType , class ListType >

void ttl::swapEdgesAwayFromBoundaryNode	(	DartType &	dart,
		ListType &	swapped_edges
	)			`[inline]`

Swaps edges away from the (boundary) node associated with dart in such a way that when removing the edges that remain incident with the node, the boundary of the triangulation will be convex.

This function is used as a first step in ttl::removeBoundaryNode

Return values:

dart

A CCW dart incident with the node

TraitsType::swapEdge (DartType& dart)
Note: Must be implemented such that dart is delivered back in a position as seen if it was glued to the edge when swapping (rotating) the edge CCW

Assumes:

The node associated with dart is at the boundary of the triangulation.

See also:: ttl::swapEdgesAwayFromInteriorNode

Definition at line 1740 of file ttl.h.

References isBoundaryEdge(), and positionAtNextBoundaryEdge().

01740                                                                                 {
01741     
01742     // All darts that are swappable.
01743     // To treat collinear nodes at an existing boundary, we must allow degeneracy
01744     // when swapping to the boundary.
01745     // dart is CCW and at the boundary.
01746     // The 0-orbit runs CCW
01747     // Deliver the dart back in the "same position".
01748     // Assume for the swap in the traits class:
01749     // - A dart on the swapped edge is delivered back in a position as
01750     //   seen if it was glued to the edge when swapping (rotating) the edge CCW
01751     
01752     //int degree = ttl::getDegreeOfNode(dart);
01753     
01754 passes:
01755   
01756   // Swap swappable edges that radiate from the node away
01757   DartType d_iter = dart; // ???? can simply use dart
01758   d_iter.alpha1().alpha2(); // first not at boundary
01759   DartType d_next = d_iter;
01760   bool bend = false;
01761   bool swapped_next_to_boundary = false;
01762   bool swapped_in_pass = false;
01763   
01764   bool allowDegeneracy; // = true;
01765   DartType tmp1, tmp2;
01766   
01767   while (!bend) {
01768     
01769     d_next.alpha1().alpha2();
01770     if (ttl::isBoundaryEdge(d_next))
01771       bend = true;  // then it is CW since alpha2
01772     
01773     // To allow removing among collinear nodes at the boundary,
01774     // degenerate triangles must be allowed
01775     // (they will be removed when used in connection with removeBoundaryNode)
01776     tmp1 = d_iter; tmp1.alpha1();
01777     tmp2 = d_iter; tmp2.alpha2().alpha1(); // don't bother with boundary (checked later)
01778     
01779     if (ttl::isBoundaryEdge(tmp1) && ttl::isBoundaryEdge(tmp2))
01780       allowDegeneracy = true;
01781     else
01782       allowDegeneracy = false;
01783     
01784     if (ttl::swappableEdge<TraitsType>(d_iter, allowDegeneracy)) {
01785       TraitsType::swapEdge(d_iter);
01786       
01787       // Collect swapped edges in the list
01788       // "Hide" the dart on the other side of the edge to avoid it being changed for
01789       // other swapps
01790       DartType swapped_edge = d_iter; // it was delivered back
01791       swapped_edge.alpha2().alpha0(); // CCW
01792       swapped_edges.push_back(swapped_edge);
01793       
01794       //degree--; // if degree is 2, or bend=true, we are done
01795       swapped_in_pass = true;
01796       if (bend)
01797         swapped_next_to_boundary = true;
01798     }
01799     if (!bend)
01800       d_iter = d_next;
01801   }
01802   
01803   // Deliver a dart as output in the same position as the incoming dart
01804   if (swapped_next_to_boundary) {
01805     // Assume that "swapping is CCW and dart is preserved in the same position
01806     d_iter.alpha1().alpha0().alpha1();  // CW and see below
01807   }
01808   else {
01809     d_iter.alpha1(); // CW and see below
01810   }
01811   ttl::positionAtNextBoundaryEdge(d_iter); // CCW 
01812   
01813   dart = d_iter; // for next pass or output
01814   
01815   // If a dart was swapped in this iteration we must run it more
01816   if (swapped_in_pass)
01817     goto passes;
01818   }

template<class TraitsType , class DartType , class ListType >

void ttl::swapEdgesAwayFromInteriorNode	(	DartType &	dart,
		ListType &	swapped_edges
	)			`[inline]`

Swaps edges away from the (interior) node associated with dart such that that exactly three edges remain incident with the node.

This function is used as a first step in ttl::removeInteriorNode

Return values:

dart

A CCW dart incident with the node

Assumes:

The node associated with dart is interior to the triangulation.

TraitsType::swapEdge (DartType& dart)
Note: Must be implemented such that dart is delivered back in a position as seen if it was glued to the edge when swapping (rotating) the edge CCW

Note:

A degenerate triangle may be left at the node.
The function is not unique as it depends on which dart at the node that is given as input.

See also:: ttl::swapEdgesAwayFromBoundaryNode

Definition at line 1682 of file ttl.h.

References getDegreeOfNode().

01682                                                                                 {
01683     
01684     // Same iteration as in fixEdgesAtCorner, but not boundary    
01685     DartType dnext = dart;
01686     
01687     // Allow degeneracy, otherwise we might end up with degree=4.
01688     // For example, the reverse operation of inserting a point on an
01689     // existing edge gives a situation where all edges are non-swappable.
01690     // Ideally, degeneracy in this case should be along the actual node,
01691     // but there is no strategy for this now.
01692     // ??? An alternative here is to wait with degeneracy till we get an
01693     // infinite loop with degree > 3.
01694     bool allowDegeneracy = true;
01695     
01696     int degree = ttl::getDegreeOfNode(dart);
01697     DartType d_iter;
01698     while (degree > 3) {
01699       d_iter = dnext;
01700       dnext.alpha1().alpha2();
01701       
01702       if (ttl::swappableEdge<TraitsType>(d_iter, allowDegeneracy)) {
01703         TraitsType::swapEdge(d_iter); // swap the edge away
01704         // Collect swapped edges in the list
01705         // "Hide" the dart on the other side of the edge to avoid it being changed for
01706         // other swaps
01707         DartType swapped_edge = d_iter; // it was delivered back
01708         swapped_edge.alpha2().alpha0(); // CCW (if not at boundary)
01709         swapped_edges.push_back(swapped_edge);
01710         
01711         degree--;
01712       }
01713     }
01714     // Output, incident to the node
01715     dart = dnext;
01716   }

template<class TraitsType , class DartType >

bool ttl::swappableEdge	(	const DartType &	dart,
		bool	allowDegeneracy
	)			`[inline]`

Checks if the edge associated with dart is swappable, i.e., if the edge is a diagonal in a strictly convex (or convex) quadrilateral.

Parameters:

allowDegeneracy

If set to true, the function will also return true if the numerical calculations indicate that the quadrilateral is convex only, and not necessarily strictly convex.

TraitsType::crossProduct2d (Dart&, Dart&)

Definition at line 1277 of file ttl.h.

References ttl_util::crossProduct2d(), and isBoundaryEdge().

01277                                                                    {
01278     
01279     // How "safe" is it?
01280     
01281     if (isBoundaryEdge(dart))
01282       return false;
01283     
01284     // "angles" are at the diagonal
01285     DartType d1 = dart;
01286     d1.alpha2().alpha1();
01287     DartType d2 = dart;
01288     d2.alpha1();
01289     if (allowDegeneracy) {
01290       if (TraitsType::crossProduct2d(d1,d2) < 0.0)
01291         return false;
01292     }
01293     else {
01294       if (TraitsType::crossProduct2d(d1,d2) <= 0.0)
01295         return false;
01296     }
01297     
01298     // Opposite side (still angle at the diagonal)
01299     d1 = dart;
01300     d1.alpha0();
01301     d2 = d1;
01302     d1.alpha1();
01303     d2.alpha2().alpha1();
01304     
01305     if (allowDegeneracy) {
01306       if (TraitsType::crossProduct2d(d1,d2) < 0.0)
01307         return false;
01308     }
01309     else {
01310       if (TraitsType::crossProduct2d(d1,d2) <= 0.0)
01311         return false;
01312     }
01313     return true;
01314   }

template<class TraitsType , class DartType >

bool ttl::swapTestDelaunay	(	const DartType &	dart,
		bool	cycling_check
	)			`[inline]`

Checks if the edge associated with dart should be swapped according to the Delaunay criterion, i.e., the circumcircle criterion (or equivalently the MaxMin angle criterion).

Parameters:

cycling_check Must be set to true when used in connection with optimization algorithms, e.g., optimizeDelaunay. This will avoid cycling and infinite loops in nearly neutral cases.

TraitsType::scalarProduct2d (DartType&, DartType&)
TraitsType::crossProduct2d (DartType&, DartType&)

Definition at line 1505 of file ttl.h.

References ttl_util::crossProduct2d(), isBoundaryEdge(), and ttl_util::scalarProduct2d().

01505                                                                     {
01506 #endif
01507     
01508     // The general strategy is taken from Cline & Renka. They claim that
01509     // their algorithm insure numerical stability, but experiments show
01510     // that this is not correct for neutral, or almost neutral cases.
01511     // I have extended this strategy (without using tolerances) to avoid
01512     // cycling and infinit loops when used in connection with LOP algorithms;
01513     // see the comments below.
01514     
01515     typedef typename TraitsType::real_type real_type;
01516     
01517     if (isBoundaryEdge(dart))
01518       return false;
01519     
01520     DartType v11 = dart;
01521     v11.alpha1().alpha0();
01522     DartType v12 = v11;
01523     v12.alpha1();
01524     
01525     DartType v22 = dart;
01526     v22.alpha2().alpha1().alpha0();
01527     DartType v21 = v22;
01528     v21.alpha1();
01529     
01530     real_type cos1 = TraitsType::scalarProduct2d(v11,v12);
01531     real_type cos2 = TraitsType::scalarProduct2d(v21,v22);
01532     
01533     // "Angles" are opposite to the diagonal.
01534     // The diagonals should be swapped iff (t1+t2) .gt. 180
01535     // degrees. The following two tests insure numerical
01536     // stability according to Cline & Renka. But experiments show
01537     // that cycling may still happen; see the aditional test below.
01538     if (cos1 >= 0  &&  cos2 >= 0) // both angles are grater or equual 90
01539       return false;
01540     if (cos1 < 0  &&  cos2 < 0) // both angles are less than 90
01541       return true;
01542     
01543     real_type sin1 = TraitsType::crossProduct2d(v11,v12);
01544     real_type sin2 = TraitsType::crossProduct2d(v21,v22);
01545     real_type sin12 = sin1*cos2 + cos1*sin2;
01546     if (sin12 >= 0) // equality represents a neutral case
01547       return false;
01548     
01549     if (cycling_check) {
01550       // situation so far is sin12 < 0. Test if this also
01551       // happens for the swapped edge.
01552       
01553       // The numerical calculations so far indicate that the edge is
01554       // not Delaunay and should not be swapped. But experiments show that
01555       // in neutral cases, or almost neutral cases, it may happen that
01556       // the swapped edge may again be found to be not Delaunay and thus
01557       // be swapped if we return true here. This may lead to cycling and
01558       // an infinte loop when used, e.g., in connection with optimizeDelaunay.
01559       //
01560       // In an attempt to avoid this we test if the swapped edge will
01561       // also be found to be not Delaunay by repeating the last test above
01562       // for the swapped edge.
01563       // We now rely on the general requirement for TraitsType::swapEdge which
01564       // should deliver CCW dart back in "the same position"; see the general
01565       // description. This will insure numerical stability as the next calculation
01566       // is the same as if this function was called again with the swapped edge.
01567       // Cycling is thus impossible provided that the initial tests above does
01568       // not result in ambiguity (and they should probably not do so).
01569       
01570       v11.alpha0();
01571       v12.alpha0();
01572       v21.alpha0();
01573       v22.alpha0();
01574       // as if the edge was swapped/rotated CCW
01575       cos1 = TraitsType::scalarProduct2d(v22,v11);
01576       cos2 = TraitsType::scalarProduct2d(v12,v21);
01577       sin1 = TraitsType::crossProduct2d(v22,v11);
01578       sin2 = TraitsType::crossProduct2d(v12,v21);
01579       sin12 = sin1*cos2 + cos1*sin2;
01580       if (sin12 < 0) {
01581         // A neutral case, but the tests above lead to swapping
01582         return false;
01583       }
01584     }
01585     
01586     return true;
01587   }

ttl Namespace Reference

Functions

Detailed Description

Function Documentation