Polygon triangulation library
=============================
Version 0.1
Copyright (C) 2019 Dr. Matthias Meixner
meixner@users.sourceforge.net
This software is for splitting simple (i.e. not self-intersecting, no holes)
polygons into triangles.
Usage
=====
Just add triangulate.cpp to your project, include triangulate.h and invoke
triangulate and pass an array cointaining the points, the number of the points
and a functor (e.g. a callback function) that gets invoked for each triangle
generated. The functor will be called with three parameters representing the
points of the triangle.
For example using a C++11 lambda a small demo would like this:
--------------------------------------------------------------------------------
#include "triangulate.h"
#include <stdio.h>
int main()
{
Vertex p[]={ {0,0}, {0,10}, {5,5}, {10,10}, {10,0}, {5,4} };
triangulate(p,6,[](const Vertex &p1, const Vertex &p2, const Vertex &p3) {
printf("(%g,%g), (%g,%g), (%g,%g)\n",p1.x,p1.y,p2.x,p2.y,p3.x,p3.y);
});
return 0;
}
--------------------------------------------------------------------------------
compile it like this:
g++ -std=c++11 src/simple.cpp src/triangulate.cpp
Or simply type 'make'
The resulting program will print the triangles that are the result of splitting
the polygon in the test program.
Algorithm
=========
The idea behind my algorithm is, that by removing a triangle that consists of
three points from the polygon and that lies completely within the polygon, the
polygon is split into two separate polygons, that can be triangulated
recursively.
Given a polygon consisting of the vertices v[0]..v[N-1] it works as follows:
- If the polygon consists of 3 vertices, it is already a triangle and this is
written out.
- It chooses the edge v[N-1], v[0] as one of the edges of the triangle.
- It searches a vertex i, so that v[N-1], v[0], v[i] form a triangle that
completely lies inside the polygon. By using the search sequence i=N/2, N/2-1,
N/2+1, N/2-2... it tries to find a triangle that splits the polygon into two
polygons of similar size.
- For checking whether the triangle completely lies within the polygon, it
checks whether the vertex is on the inside of the edge and it checks whether
one of the edges v[j]..v[j+1] of the polygon intersects the triangle. The
corner-cases that points of the triangle are the same points of an edge of the
polygon are handled separately: If the intersection only covers the common
points, then the intersection is ignored.
- If a vertex i has been found, the triangle v[N-1], v[0], v[i] is written out
and the triangulation is performed recursively for the polygons v[0]..v[i]
and v[i]..v[N-1] as long as these consist of at least 3 vertices.
- If no vertex i is found, the polygon was not simple and an error is returned.
+ For checking if a vertex is on the inside of an edge, a preprocessing step
determines whether the vertices are ordered clockwise or counterclockwise.
In the first case, the inside of the polygon is on the right side of the edge
vector, in the second case it is on the left side.
+ As optimization use recursion only for the smaller of the two resulting
polygons after removing the triangle and iteratively restart the triangulation
function. By this the amount of memory on stack is limited to O(log n).
Due to the selection of the starting edge and vertex, it is not required to
rearrange vertices in memory for the recursion. As a result the algorithm does
not need to allocate memory from the heap.
In the best case, e.g. for convex polygons, the run time is in O(n log n):
- Selecting i=N/2, the triangle v[N-1], v[0], v[i] already completely lies
within the polygon, i.e. no additional vertices will have to be tested.
- Checking that this triangle does not intersect edges from the polygon takes
N-1 tests, i.e. is in O(n)
- Since i is N/2, the polygon is split into two polygons of aboult half the
size. Therefore, the recursion tree has height O(log n).
=> In the best case the run time is in O(n log n)
In the worst case the run time is in O(n^3):
- Only the last vertex in the search sequence belongs to a triangle that
completely lies within the polygon, each of the N-2 vertices has to be tested
against all N-2 edges, which is in O(n^2)
- As a result removing the triangle does not split the polygon into two polygons
but just reduces the size of one polygon by 1, therefore, the recursion has
depth N.
=> Overall in the worst case time complexity is in O(n^3)
Summary:
========
- Does not need to allocate memory from the heap
- Stack memory is in O(log n)
- Best case run time is in O(n log n)
- Worst case run time is in O(n^3)
License:
========
Copyright (c) 2019 Dr. Matthias Meixner
Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.
