Panda3D
|
This class can triangulate a convex or concave polygon, even one with holes. More...
#include "triangulator.h"
Classes | |
struct | monchain_t |
struct | node_t |
struct | point_t |
struct | segment_t |
struct | trap_t |
class | Triangle |
struct | vertexchain_t |
Public Member Functions | |
void | add_hole_vertex (int index) |
Adds the next consecutive vertex of the current hole. | |
void | add_polygon_vertex (int index) |
Adds the next consecutive vertex of the polygon. | |
int | add_vertex (double x, double y) |
Adds a new vertex to the vertex pool. | |
int | add_vertex (const LPoint2d &point) |
Adds a new vertex to the vertex pool. | |
void | begin_hole () |
Finishes the previous hole, if any, and prepares to add a new hole. | |
void | clear () |
Removes all vertices and polygon specifications from the Triangulator, and prepares it to start over. | |
void | clear_polygon () |
Removes the current polygon definition (and its set of holes), but does not clear the vertex pool. | |
int | get_num_triangles () const |
Returns the number of triangles generated by the previous call to triangulate(). | |
int | get_num_vertices () const |
Returns the number of vertices in the pool. | |
int | get_triangle_v0 (int n) const |
Returns vertex 0 of the nth triangle generated by the previous call to triangulate(). | |
int | get_triangle_v1 (int n) const |
Returns vertex 1 of the nth triangle generated by the previous call to triangulate(). | |
int | get_triangle_v2 (int n) const |
Returns vertex 2 of the nth triangle generated by the previous call to triangulate(). | |
const LPoint2d & | get_vertex (int n) const |
Returns the nth vertex. | |
bool | is_left_winding () const |
Returns true if the polygon vertices are listed in counterclockwise order, or false if they appear to be listed in clockwise order. | |
MAKE_SEQ (get_vertices, get_num_vertices, get_vertex) | |
void | triangulate () |
Does the work of triangulating the specified polygon. | |
Friends | |
struct | segment_t |
class | Triangle |
This class can triangulate a convex or concave polygon, even one with holes.
It is adapted from an algorithm published as:
Narkhede A. and Manocha D., Fast polygon triangulation algorithm based on Seidel's Algorithm, UNC-CH, 1994.
http://www.cs.unc.edu/~dm/CODE/GEM/chapter.html
It works strictly on 2-d points. You'll have to convert your polygon into a plane if you have 3-d points.
Definition at line 38 of file triangulator.h.
void Triangulator::add_hole_vertex | ( | int | index | ) |
Adds the next consecutive vertex of the current hole.
This vertex should index into the vertex pool established by repeated calls to add_vertex().
The vertices may be listed in either clockwise or counterclockwise order. Vertices should not be repeated.
Definition at line 104 of file triangulator.cxx.
void Triangulator::add_polygon_vertex | ( | int | index | ) |
Adds the next consecutive vertex of the polygon.
This vertex should index into the vertex pool established by repeated calls to add_vertex().
The vertices may be listed in either clockwise or counterclockwise order. Vertices should not be repeated. In particular, do not repeat the first vertex at the end.
Definition at line 77 of file triangulator.cxx.
int Triangulator::add_vertex | ( | const LPoint2d & | point | ) |
Adds a new vertex to the vertex pool.
Returns the vertex index number.
Definition at line 46 of file triangulator.cxx.
Referenced by add_vertex().
int Triangulator::add_vertex | ( | double | x, |
double | y | ||
) | [inline] |
Adds a new vertex to the vertex pool.
Returns the vertex index number.
Definition at line 23 of file triangulator.I.
References add_vertex().
void Triangulator::begin_hole | ( | ) |
Finishes the previous hole, if any, and prepares to add a new hole.
Definition at line 88 of file triangulator.cxx.
void Triangulator::clear | ( | ) |
Removes all vertices and polygon specifications from the Triangulator, and prepares it to start over.
Definition at line 34 of file triangulator.cxx.
References clear_polygon().
void Triangulator::clear_polygon | ( | ) |
Removes the current polygon definition (and its set of holes), but does not clear the vertex pool.
Definition at line 59 of file triangulator.cxx.
Referenced by clear().
int Triangulator::get_num_triangles | ( | ) | const |
Returns the number of triangles generated by the previous call to triangulate().
Definition at line 216 of file triangulator.cxx.
int Triangulator::get_num_vertices | ( | ) | const [inline] |
Returns the number of vertices in the pool.
Note that the Triangulator might append new vertices, in addition to those added by the user, if any of the polygon is self-intersecting, or if any of the holes intersect some part of the polygon edges.
Definition at line 37 of file triangulator.I.
int Triangulator::get_triangle_v0 | ( | int | n | ) | const |
Returns vertex 0 of the nth triangle generated by the previous call to triangulate().
This is a zero-based index into the vertices added by repeated calls to add_vertex().
Definition at line 230 of file triangulator.cxx.
int Triangulator::get_triangle_v1 | ( | int | n | ) | const |
Returns vertex 1 of the nth triangle generated by the previous call to triangulate().
This is a zero-based index into the vertices added by repeated calls to add_vertex().
Definition at line 245 of file triangulator.cxx.
int Triangulator::get_triangle_v2 | ( | int | n | ) | const |
Returns vertex 2 of the nth triangle generated by the previous call to triangulate().
This is a zero-based index into the vertices added by repeated calls to add_vertex().
Definition at line 260 of file triangulator.cxx.
const LPoint2d & Triangulator::get_vertex | ( | int | n | ) | const [inline] |
bool Triangulator::is_left_winding | ( | ) | const [inline] |
Returns true if the polygon vertices are listed in counterclockwise order, or false if they appear to be listed in clockwise order.
Definition at line 60 of file triangulator.I.
void Triangulator::triangulate | ( | ) |
Does the work of triangulating the specified polygon.
After this call, you may retrieve the new triangles one at a time by iterating through get_triangle_v0/1/2().
Definition at line 118 of file triangulator.cxx.
References Randomizer::random_int().