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

#include "triangulator.h"

Inheritance diagram for Triangulator:

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 (const LPoint2d &point)
	Adds a new vertex to the vertex pool.
int	add_vertex (double x, double y)
	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.
Protected Types
typedef pvector< vector_int >	Holes
typedef pvector< node_t >	QueryStructure
typedef pvector< Triangle >	Result
typedef pvector< segment_t >	Segments
typedef pvector< trap_t >	TrapezoidStructure
typedef struct Triangulator::point_t	vector_t
typedef pvector< LPoint2d >	Vertices
Protected Member Functions
int	_equal_to (point_t v0, point_t v1)
int	_greater_than (point_t v0, point_t v1)
int	_greater_than_equal_to (point_t v0, point_t v1)
int	_less_than (point_t v0, point_t v1)
int	_max (point_t yval, point_t v0, point_t *v1)
int	_min (point_t yval, point_t v0, point_t *v1)
int	add_segment (int segnum)
bool	check_left_winding (const vector_int &range) const
	Returns true if the list of vertices is counter-clockwise, false if it is clockwise.
int	choose_segment ()
void	cleanup_polygon_indices (vector_int &polygon)
	Removes any invalid index numbers from the list.
int	construct_trapezoids (int nseg)
int	find_new_roots (int segnum)
double	get_angle (point_t vp0, point_t vpnext, point_t *vp1)
int	get_vertex_positions (int v0, int v1, int ip, int iq)
int	init_query_structure (int segnum)
int	inserted (int segnum, int whichpt)
int	inside_polygon (trap_t *t)
int	is_left_of (int segnum, point_t *v)
int	locate_endpoint (point_t v, point_t vo, int r)
int	make_new_monotone_poly (int mcur, int v0, int v1)
void	make_segment (const vector_int &range, bool want_left_winding)
	Converts a linear list of integer vertices to a list of segment_t.
int	merge_trapezoids (int segnum, int tfirst, int tlast, int side)
int	monotonate_trapezoids (int n)
int	new_chain_element ()
int	newmon ()
int	newnode ()
int	newtrap ()
int	traverse_polygon (int mcur, int trnum, int from, int dir)
void	triangulate_monotone_polygons (int nvert, int nmonpoly)
void	triangulate_single_polygon (int nvert, int posmax, int side)
Static Protected Member Functions
static double	math_log2 (double v)
static int	math_logstar_n (int n)
static int	math_N (int n, int h)
Protected Attributes
Holes	_holes
vector_int	_polygon
Result	_result
Vertices	_vertices
int	choose_idx
pvector< monchain_t >	mchain
vector_int	mon
vector_int	permute
QueryStructure	qs
Segments	seg
TrapezoidStructure	tr
pvector< vertexchain_t >	vert
vector_int	visited
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 37 of file triangulator.h.

Member Function Documentation

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.

Referenced by ObjToEggConverter::process_f_node().

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.

bool Triangulator::check_left_winding ( const vector_int & range ) const [protected]

Returns true if the list of vertices is counter-clockwise, false if it is clockwise.

Definition at line 381 of file triangulator.cxx.

Referenced by is_left_winding(), and make_segment().

void Triangulator::cleanup_polygon_indices ( vector_int & polygon ) [protected]

Removes any invalid index numbers from the list.

Definition at line 286 of file triangulator.cxx.

Referenced by triangulate().

void Triangulator::clear ( )

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

Reimplemented in Triangulator3.

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

Referenced by ObjToEggConverter::process_f_node().

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.

Reimplemented in Triangulator3.

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

Referenced by ObjToEggConverter::process_f_node().

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

Referenced by ObjToEggConverter::process_f_node().

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

Referenced by ObjToEggConverter::process_f_node().

const LPoint2d & Triangulator::get_vertex ( int n ) const [inline]

Returns the nth vertex.

Reimplemented in Triangulator3.

Definition at line 47 of file triangulator.I.

References LPoint2d::zero().

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.

References check_left_winding().

void Triangulator::make_segment	(	const vector_int &	range,
		bool	want_left_winding
	)		`[protected]`

Converts a linear list of integer vertices to a list of segment_t.

If want_left_winding is true, the list is reversed if necessary to make it left-winding; otherwise, it is reversed to make it right-winding.

Definition at line 406 of file triangulator.cxx.

References check_left_winding().

Referenced by 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().

Reimplemented in Triangulator3.

Definition at line 118 of file triangulator.cxx.

References cleanup_polygon_indices(), make_segment(), and Randomizer::random_int().

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

panda/src/mathutil/triangulator.h
panda/src/mathutil/triangulator.cxx
panda/src/mathutil/triangulator.I

Classes

Public Member Functions

Protected Types

Protected Member Functions

Static Protected Member Functions

Protected Attributes

Friends

Detailed Description

Member Function Documentation