![]() |
Fréchet View
1.6.0
A Tool for Exploring Fréchet Distance Algorithms
|
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.
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... | |
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.
PolygonUtilities::PolygonUtilities | ( | ) |
empty constructor
Definition at line 9 of file poly_utils.cpp.
PolygonUtilities::PolygonUtilities | ( | const Curve & | p | ) |
default constructor with polygon
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!
Definition at line 25 of file poly_utils.cpp.
|
private |
debug assertion
Definition at line 146 of file poly_utils.cpp.
|
staticprivate |
create a diagonal in a convex partition
u | a vertex index |
v | another vertex index |
n | numer of vertexes in polygon |
partition | holds a list sub-polygons |
Definition at line 136 of file poly_utils.cpp.
int PolygonUtilities::decompose | ( | DecompositionAlgorithm | algo, |
bool | verify | ||
) |
compute a convex decomposition of the polygon. Store results in the member variable 'convex'.
algo | decomposition algorithm to use |
verify | if true, verify that results are convex |
Definition at line 58 of file poly_utils.cpp.
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.)
tri | holds the triangulation data structure on return |
Definition at line 254 of file poly_utils.cpp.
|
private |
compute a fan-triangulation for one convex part
poly | a CGAL polygon structure |
tri | holds the triangulation data on return |
Definition at line 226 of file poly_utils.cpp.
void PolygonUtilities::findReflexVertices | ( | Polygon & | poly, |
double | tolerance = 0.0 |
||
) |
find all reflex (concave) vertices.
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.
bool PolygonUtilities::is_convex | ( | ) | const |
Definition at line 48 of file poly_utils.cpp.
bool PolygonUtilities::is_counter_clockwise | ( | ) |
Definition at line 53 of file poly_utils.cpp.
|
staticprivate |
test whether a vertex is a reflex (concave) vertex
p | iterator to a vertex |
precision | tolerance for half-plane test. May be use to compensate round-off errors. |
Halfplane Test Given a line segment [ab] is p on the left or the right of the segment?
Definition at line 290 of file poly_utils.cpp.
bool PolygonUtilities::is_simple | ( | ) | const |
Definition at line 43 of file poly_utils.cpp.
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.
partition | holds the sub-polygons on return |
Definition at line 107 of file poly_utils.cpp.
int PolygonUtilities::simplify | ( | ) |
Contract polygon chains to a single edge. Kepp only c-diagonal and contracted edges. (see Buchin et al. for explanation)
Definition at line 163 of file poly_utils.cpp.
|
private |
Contract polygon chains to a single edge. Kepp only c-diagonal and contracted edges.
poly | a CGAL polygon structure |
Definition at line 182 of file poly_utils.cpp.
|
private |
the polygon under examination
Definition at line 125 of file poly_utils.h.
|
private |
list of convex parts. created by decompose().
Definition at line 127 of file poly_utils.h.