Fréchet View  1.6.0
A Tool for Exploring Fréchet Distance Algorithms
frechet::poly::PolygonUtilities Class Reference

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

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
pan 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
ua vertex index
vanother vertex index
nnumer of vertexes in polygon
partitionholds 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
algodecomposition algorithm to use
verifyif 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
triholds 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
polya CGAL polygon structure
triholds 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
polya polygon
tolerancetolerance 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
piterator to a vertex
precisiontolerance 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
partitionholds 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
polya 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: