Panda3D
Classes | Public Member Functions | Public Attributes | Friends | List of all members
Triangulator Class Reference

This class can triangulate a convex or concave polygon, even one with holes. More...

#include "triangulator.h"

Inheritance diagram for Triangulator:
Triangulator3

Public Member Functions

void add_hole_vertex (int index)
 Adds the next consecutive vertex of the current hole. More...
 
void add_polygon_vertex (int index)
 Adds the next consecutive vertex of the polygon. More...
 
int add_vertex (const LPoint2d &point)
 Adds a new vertex to the vertex pool. More...
 
int add_vertex (double x, double y)
 Adds a new vertex to the vertex pool. More...
 
void begin_hole ()
 Finishes the previous hole, if any, and prepares to add a new hole. More...
 
void clear ()
 Removes all vertices and polygon specifications from the Triangulator, and prepares it to start over. More...
 
void clear_polygon ()
 Removes the current polygon definition (and its set of holes), but does not clear the vertex pool. More...
 
int get_num_triangles () const
 Returns the number of triangles generated by the previous call to triangulate(). More...
 
int get_num_vertices () const
 
int get_triangle_v0 (int n) const
 Returns vertex 0 of the nth triangle generated by the previous call to triangulate(). More...
 
int get_triangle_v1 (int n) const
 Returns vertex 1 of the nth triangle generated by the previous call to triangulate(). More...
 
int get_triangle_v2 (int n) const
 Returns vertex 2 of the nth triangle generated by the previous call to triangulate(). More...
 
const LPoint2d & get_vertex (int n) const
 
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. More...
 
void triangulate ()
 Does the work of triangulating the specified polygon. More...
 

Public Attributes

 get_num_vertices
 Returns the number of vertices in the pool. More...
 
 get_vertex
 Returns the nth vertex. More...
 

Friends

struct segment_t
 
class Triangle
 

Detailed Description

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. See Triangulator3 for 3-d points.

Definition at line 32 of file triangulator.h.

Member Function Documentation

◆ add_hole_vertex()

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 83 of file triangulator.cxx.

◆ add_polygon_vertex()

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 63 of file triangulator.cxx.

◆ add_vertex() [1/2]

int Triangulator::add_vertex ( const LPoint2d &  point)

Adds a new vertex to the vertex pool.

Returns the vertex index number.

Definition at line 38 of file triangulator.cxx.

Referenced by add_vertex().

◆ add_vertex() [2/2]

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 18 of file triangulator.I.

References add_vertex().

◆ begin_hole()

void Triangulator::begin_hole ( )

Finishes the previous hole, if any, and prepares to add a new hole.

Definition at line 71 of file triangulator.cxx.

◆ clear()

void Triangulator::clear ( )

Removes all vertices and polygon specifications from the Triangulator, and prepares it to start over.

Definition at line 29 of file triangulator.cxx.

References clear_polygon().

Referenced by Triangulator3::clear().

◆ 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 49 of file triangulator.cxx.

Referenced by clear().

◆ get_num_triangles()

int Triangulator::get_num_triangles ( ) const

Returns the number of triangles generated by the previous call to triangulate().

Definition at line 206 of file triangulator.cxx.

◆ get_triangle_v0()

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 218 of file triangulator.cxx.

◆ get_triangle_v1()

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 231 of file triangulator.cxx.

◆ get_triangle_v2()

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 244 of file triangulator.cxx.

◆ is_left_winding()

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 47 of file triangulator.I.

◆ triangulate()

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 94 of file triangulator.cxx.

Member Data Documentation

◆ get_num_vertices

int Triangulator::get_num_vertices
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 42 of file triangulator.h.

◆ get_vertex

const LPoint2d & Triangulator::get_vertex
inline

Returns the nth vertex.

Definition at line 42 of file triangulator.h.


The documentation for this class was generated from the following files: