Detailed Description

a helper class for polygon analysis.

Contains test properties for polygons: is a polygon convex, clock-wise oriented, simple (not self-intersecting) ?

Performs convex decomposition of polygons and fan-triangulation of convex parts.

Author: Peter Schäfer

Definition at line 121 of file poly_utils.h.

#include <poly_utils.h>

Public Types
enum	DecompositionAlgorithm { APPROX_GREENE, APPROX_HERTEL, OPTIMAL_GREENE }
	choice of decomposition algorithm More...

Public Member Functions
	PolygonUtilities ()
	empty constructor More...

	PolygonUtilities (const Curve &p)
	default constructor with polygon More...

int	decompose (DecompositionAlgorithm algo, bool verify)
	compute a convex decomposition of the polygon. Store results in the member variable 'convex'. More...

int	partition (Partition &partition) const
	compute a list of sub-polygons, one for each convex part. This is mainly copying data to a more convenient format. More...

int	simplify ()
	Contract polygon chains to a single edge. Kepp only c-diagonal and contracted edges. (see Buchin et al. for explanation) More...

void	findReflexVertices (Polygon &poly, double tolerance=0.0)
	find all reflex (concave) vertices. More...

void	fanTriangulate (Triangulation &tri) const
	compute a fan-triangulation from a list of convex parts. Each convex sub-polygon is triangulated using a simple fan-like approach. (see Buchin et al.) More...

Basic Polygon properties
bool	is_simple () const

bool	is_convex () const

bool	is_counter_clockwise ()

Private Member Functions
bool	assertStrictlySorted (const CgalPolygon &)
	debug assertion More...

bool	simplify (CgalPolygon &poly)
	Contract polygon chains to a single edge. Kepp only c-diagonal and contracted edges. More...

void	fanTriangulate (const CgalPolygon &poly, Triangulation &tri) const
	compute a fan-triangulation for one convex part More...

Static Private Member Functions
static bool	create1Diagonal (int u, int v, int n, Partition &partition)
	create a diagonal in a convex partition More...

static bool	is_reflex_vertex (const CgalPolygon::Vertex_circulator &p, double precision=0.0)
	test whether a vertex is a reflex (concave) vertex More...

Private Attributes
CgalPolygon	cgp
	the polygon under examination More...

CgalPolygonList	convex
	list of convex parts. created by decompose(). More...

Member Enumeration Documentation

◆ DecompositionAlgorithm

enum frechet::poly::PolygonUtilities::DecompositionAlgorithm

choice of decomposition algorithm

Enumerator
APPROX_GREENE	Greene's approximation algorithm.
APPROX_HERTEL	Hertel and Mehlhorn's approximation algorithm.
OPTIMAL_GREENE	Greene's optimal algorithm.

Definition at line 132 of file poly_utils.h.

Constructor & Destructor Documentation

◆ PolygonUtilities() [1/2]

PolygonUtilities::PolygonUtilities ( )

empty constructor

Definition at line 9 of file poly_utils.cpp.

◆ PolygonUtilities() [2/2]

PolygonUtilities::PolygonUtilities ( const Curve & p )

default constructor with polygon

Parameters

p	an input polygon

Important Qt and SVG coordinate systems are y-down (0,0 is on the top-left of the drawing plane). At least this is how we interpret it, and it's consistent with most drawing programs.

CGAL expects y coordinates up. (0,0 is on the bottom-left of the drawing plane).

This affects, among other things, clockwise orientation. Frechet FreeSpace does not care. So better get it right from the start. CgalPoint constructor takes care of it!

Precondition: CgalPolygon always assumes a closed polygon. The last point should not be duplicated.

Definition at line 25 of file poly_utils.cpp.

Member Function Documentation

◆ assertStrictlySorted()

bool PolygonUtilities::assertStrictlySorted ( const CgalPolygon & cgp )

private

debug assertion

Returns: true if the vertex indexes are properly sorted

Definition at line 146 of file poly_utils.cpp.

◆ create1Diagonal()

bool PolygonUtilities::create1Diagonal	(	int	u,
		int	v,
		int	n,
		Partition &	partition
	)

staticprivate

create a diagonal in a convex partition

Parameters

u	a vertex index
v	another vertex index
n	numer of vertexes in polygon
partition	holds a list sub-polygons

Returns: true if (u,v) is a diagonal. If so, it was added to partition.

Definition at line 136 of file poly_utils.cpp.

◆ decompose()

int PolygonUtilities::decompose	(	DecompositionAlgorithm	algo,
		bool	verify
	)

compute a convex decomposition of the polygon. Store results in the member variable 'convex'.

Parameters

algo	decomposition algorithm to use
verify	if true, verify that results are convex

Returns: the number of convex parts

Definition at line 58 of file poly_utils.cpp.

◆ fanTriangulate() [1/2]

void PolygonUtilities::fanTriangulate ( Triangulation & tri ) const

compute a fan-triangulation from a list of convex parts. Each convex sub-polygon is triangulated using a simple fan-like approach. (see Buchin et al.)

Precondition: decompose() must have computed a convex decomposition

Parameters

tri	holds the triangulation data structure on return

Definition at line 254 of file poly_utils.cpp.

◆ fanTriangulate() [2/2]

void PolygonUtilities::fanTriangulate	(	const CgalPolygon &	poly,
		Triangulation &	tri
	)		const

private

compute a fan-triangulation for one convex part

Parameters

poly	a CGAL polygon structure
tri	holds the triangulation data on return

Definition at line 226 of file poly_utils.cpp.

◆ findReflexVertices()

void PolygonUtilities::findReflexVertices	(	Polygon &	poly,
		double	tolerance = `0.0`
	)

find all reflex (concave) vertices.

Precondition: assumes the polygon is oriented counter-clockwise

Parameters

poly	a polygon
tolerance	tolerance for half-plane test. May be use to compensate round-off errors.

Definition at line 279 of file poly_utils.cpp.

◆ is_convex()

bool PolygonUtilities::is_convex ( ) const

Returns: true if the polygon is convex

Definition at line 48 of file poly_utils.cpp.

◆ is_counter_clockwise()

bool PolygonUtilities::is_counter_clockwise ( )

Returns: true if the polygon is oriented counter-clockwise. fals if it is oriented clockwise.

Definition at line 53 of file poly_utils.cpp.

◆ is_reflex_vertex()

bool PolygonUtilities::is_reflex_vertex	(	const CgalPolygon::Vertex_circulator &	p,
		double	precision = `0.0`
	)

staticprivate

test whether a vertex is a reflex (concave) vertex

Parameters

p	iterator to a vertex
precision	tolerance for half-plane test. May be use to compensate round-off errors.

Returns: true if the vertex is considered to be a reflex vertex

Halfplane Test Given a line segment [ab] is p on the left or the right of the segment?

Returns: > 0 if p is on the left side, < 0 if p is on the right side, 0 if p is colinear to [ab] (assuming a y-up coordinate system!)

Definition at line 290 of file poly_utils.cpp.

◆ is_simple()

bool PolygonUtilities::is_simple ( ) const

Returns: true if the polygon is simple, i.e. if is contains no self-intersections

Definition at line 43 of file poly_utils.cpp.

◆ partition()

int PolygonUtilities::partition ( Partition & partition ) const

compute a list of sub-polygons, one for each convex part. This is mainly copying data to a more convenient format.

Parameters

partition holds the sub-polygons on return

Precondition: decompose() must have computed a convex decomposition

Returns: the number of convex parts

Definition at line 107 of file poly_utils.cpp.

◆ simplify() [1/2]

int PolygonUtilities::simplify ( )

Contract polygon chains to a single edge. Kepp only c-diagonal and contracted edges. (see Buchin et al. for explanation)

Precondition: decompose() must have computed a convex decomposition

Returns: the number of remaining parts

Definition at line 163 of file poly_utils.cpp.

◆ simplify() [2/2]

bool PolygonUtilities::simplify ( CgalPolygon & poly )

private

Contract polygon chains to a single edge. Kepp only c-diagonal and contracted edges.

Parameters

poly	a CGAL polygon structure

Returns: the number of remaining parts

Definition at line 182 of file poly_utils.cpp.

Member Data Documentation

◆ cgp

CgalPolygon frechet::poly::PolygonUtilities::cgp

private

the polygon under examination

Definition at line 125 of file poly_utils.h.

◆ convex

CgalPolygonList frechet::poly::PolygonUtilities::convex

private

list of convex parts. created by decompose().

Definition at line 127 of file poly_utils.h.

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

include/frechet/poly/poly_utils.h
src/frechet/poly/poly_utils.cpp

Detailed Description

Public Types

Public Member Functions

Private Member Functions

Static Private Member Functions

Private Attributes

Member Enumeration Documentation

◆ DecompositionAlgorithm

Constructor & Destructor Documentation

◆ PolygonUtilities() [1/2]

◆ PolygonUtilities() [2/2]

Member Function Documentation

◆ assertStrictlySorted()

◆ create1Diagonal()

◆ decompose()

◆ fanTriangulate() [1/2]

◆ fanTriangulate() [2/2]

◆ findReflexVertices()

◆ is_convex()

◆ is_counter_clockwise()

◆ is_reflex_vertex()

◆ is_simple()

◆ partition()

◆ simplify() [1/2]

◆ simplify() [2/2]

Member Data Documentation

◆ cgp

◆ convex