# Example using TTL and the half-edge data structure

```//==================================================================================================
//
// File: main.cpp
//
// Created:
//
// Author: Øyvind Hjelle <oyvind.hjelle@math.sintef.no>
//
// Revision: \$Id: main.cpp,v 1.2 2006/07/26 12:08:44 oyvindhj Exp \$
//
// Description:
//
//==================================================================================================
//
// This file is part of an example program for TTL.  This example
// program may be used, distributed and modified without limitation.
//
//==================================================================================================

//#define DEBUG_TTL_CONSTR
//#define DEBUG_TTL_CONSTR_PLOT

#include <ttl/halfedge/HeTriang.h>
#include <ttl/halfedge/HeDart.h>
#include <ttl/halfedge/HeTraits.h>
//using namespace hed; // (to avoid using prefix hed::)

#include <fstream>
#include <iostream>
#include <algorithm>
using namespace std;

// ------------------------------------------------------------------------------------------------
// Interpret two points as being coincident
inline bool eqPoints(hed::Node*& p1, hed::Node*& p2) {
double dx = p1->x() - p2->x();
double dy = p1->y() - p2->y();
double dist2 = dx*dx + dy*dy;
const double eps = 1.0e-12;
if (dist2 < eps)
return true;

return false;
}

// ------------------------------------------------------------------------------------------------
// Lexicographically compare two points (2D)
inline bool ltLexPoint(const hed::Node* p1, const hed::Node* p2) {
return (p1->x() < p2->x()) || (p1->x() == p2->x() && p1->y() < p2->y());
};

// =================================================================================================
// A main program using TTL and the half-edge data structure to create
// a Delaunay triangulation.
// The program also demonstrates how to use other function templates in TTL.
// =================================================================================================

int main() {

// ===============================================================
// CREATE A DELAUNAY TRIANGULATION FROM RANDOM POINTS IN THE PLANE
// ===============================================================

// Create random test data.
int no_of_nodes = 100;
std::vector<hed::Node*>* nodes = ttl_util::createRandomData<hed::Node>(no_of_nodes);

// Sort the nodes lexicographically in the plane.
// This is recommended since the triangulation algorithm will run much faster.
// (ltLexPoint is defined above)
std::sort(nodes->begin(), nodes->end(), ltLexPoint);

// Remove coincident points to avoid degenerate triangles. (eqPoints is defined above)
std::vector<hed::Node*>::iterator new_end = std::unique(nodes->begin(), nodes->end(), eqPoints);

// Make the triangulation
hed::Triangulation triang;
triang.createDelaunay(nodes->begin(), new_end);

// <... Print triangulation; see end of file ...>

// ========================================================
// SOME EXAMPLES USING TTL (Functions in namespace ttl)
// ========================================================

// Insert a new node in the Delaunay triangulation.
// We need an arbitrary CCW (counterclockwise) dart for TTL.
// Make the dart from the first edge in the list of leading edges.
// ( Could also use Triangulation::createDart() )
hed::Edge* edge = *l_edges.begin();
hed::Dart dart(edge);
hed::Node* point = new hed::Node(0.3, 0.6, 0);
ttl::insertNode<hed::TTLtraits>(dart, *point);

// Locate a triangle in the triangulation containing the given point.
// The given dart will be repositioned to that triangle while maintaining
// its orientation (CCW or CW).
// If the given point is outside the triangulation, the dart will be
// positioned at a boundary edge.
point->init(0.5, 0.5, 0);
bool found = ttl::locateTriangle<hed::TTLtraits>(*point, dart);
if (!found) {
cout << "The given points is outside the triangulation" << endl;
// (and the dart is positioned at a boundary edge)
exit(-1);
}

// The degree (or valency) of a node V in a triangulation, is defined
// as the number of edges incident with V.
// Get the degree of the node associated with the dart.
int degree = ttl::getDegreeOfNode(dart);
cout << "Degree of node = " << degree << endl;

// Check if the edge associated with the dart is at the boundary of the triangulation.
if (ttl::isBoundaryEdge(dart))
cout << "The edge is at the boundary" << endl;

// Check if the node associated with the dart is at the boundary of the triangulation.
if (ttl::isBoundaryNode(dart))
cout << "The node is at the boundary" << endl;

// Remove the node associated with the dart used above.
ttl::removeNode<hed::TTLtraits>(dart);

// Get the boundary of the triangulation represented as a list of darts.
edge = triang.getBoundaryEdge();
hed::Dart b_dart(edge);
list<hed::Dart> boundary;
ttl::getBoundary(b_dart,boundary);
cout << "No. of edges on boundary = " << boundary.size() << endl;

// Check if the triangulation is Delaunay
// (This is not a TTL function)
if (triang.checkDelaunay())
cout << "Triangulation is Delaunay" << endl;
else
cout << "WARNING: Triangulation is not Delaunay" << endl;

// Insert two nodes and then insert a constrained edge between them
// (Note that this could also be implemented in the code for the data structure.
//  Here we call ttl directly to demonstrate the generic concept.)
hed::Dart d1 = triang.createDart(); // an arbitrary CCW dart
ttl::insertNode<hed::TTLtraits>(d1, *new hed::Node(0.1, 0.25, 0));
hed::Dart d2 = triang.createDart();
ttl::insertNode<hed::TTLtraits>(d2, *new hed::Node(0.6, 0.85, 0));
// (Note that d1 is not necessarily valid after having inserted d2 since insertion
//  of d2 may affect d1. Here d2 is "far from" d1, so we are relatively safe).
bool optimizeDelaunay = true; // optimizes to a constrained Delaunay triangulation
dart = ttl::insertConstraint<hed::TTLtraits>(d1, d2, optimizeDelaunay);

// Set the edge as constrained (fixed) such that it is not swapped when inserting nodes later
dart.getEdge()->setConstrained();

// Insert nodes and a constraint near that above to demonstrate fixed edges
d1 = triang.createDart();
ttl::insertNode<hed::TTLtraits>(d1, *new hed::Node(0.35, 0.56, 0));
d2 = triang.createDart();
ttl::insertNode<hed::TTLtraits>(d2, *new hed::Node(0.1, 0.9, 0));
dart = ttl::insertConstraint<hed::TTLtraits>(d1, d2, optimizeDelaunay);
dart.getEdge()->setConstrained();

// Check if the boundary is convex (in the plane)
if (ttl::convexBoundary<hed::TTLtraits>(b_dart))
cout << "\nBoundary is convex:" << endl;

// Print the nodes at the boundary
list<hed::Dart>::const_iterator it;
for (it = boundary.begin();  it != boundary.end(); ++it)
cout << it->getNode()->x() << " " << it->getNode()->y() << '\n';

// Print the triangulation (its edges)  to file
// (for gnuplot or other line drawing programs)
cout << "\nPrinting edges to file qweEdges.dat..." << endl;
cout << "Plot triangulation with: gnuplot qwe.gnu" << endl;

ofstream ofile("qweEdges.dat");
triang.printEdges(ofile);

return 0;
}
```

Generated on Wed Nov 17 17:44:27 2010 for TTL by  1.6.1