#include "Polygon.h"
#include "Point.h"
#include "Triangle.h"
static void recursive_triangulation (Polygon &, list<Triangle> &);
void triangulate (const Polygon & input_P, list<Triangle> & output)
{
Polygon P = input_P;
// Make a working copy of parameter
output.clear ();
// Only the first time. Recursive
// calls should not clear the list of triangles
recursive_triangulation (P, output);
}
static void recursive_triangulation (Polygon & P, list<Triangle> & output)
{
int bla (const Polygon &, int);
Polygon::iterator current = P.begin();
if ((current+3) == current) // If polygon contains 3 vertices
{
output.push_back (Triangle (*current, *(current+1), *(current+2)));
return;
}
bool done = false;
do
{
Triangle t (*(current-1), *current, *(current+1));
if (t.orientation() == counter_clockwise) // if convex vertex
{
bool empty_triangle = true;
Polygon::const_iterator i = current+2, farthest_point = current-1;
do
{
if (t.contains (*i))
{
empty_triangle = false;
if (Triangle(*(current+1), *(current-1), *i).area() >
Triangle(*(current+1), *(current-1), *farthest_point).area())
{
farthest_point = i;
}
}
i++;
}
while (i != current-1);
if (empty_triangle) // send it to the triangulation
{
output.push_back (t);
current = P.remove (current);
current--;
if ((current+3) == current) // If P became a triangle, done
{
output.push_back (Triangle (*current, *(current+1), *(current+2)));
return;
}
}
else // t not empty ==> split the polygon and triangulate both halves
{
Polygon first_half, second_half;
for (i = current; i != farthest_point; i++)
{
first_half.push_back (*i);
}
first_half.push_back (*farthest_point);
recursive_triangulation (first_half, output);
for (i = farthest_point; i != current; i++)
{
second_half.push_back (*i);
}
second_half.push_back (*current);
recursive_triangulation (second_half, output);
return;
}
}
current++;
}
while (true);
}
Return to article