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

Detailed Description

classes for computing the Fréchet Distance on simple polygons.

Classes

class  Algorithm
 base class for algorithm for simple polygons. More...
 
class  AlgorithmMultiCore
 Multi-Core implementaion. Uses Intel TBB to perform some parallel computation. More...
 
class  AlgorithmSingleCore
 Sequential implementation for a single processor core. More...
 
class  AlgorithmTopoSort
 implementation with a sorted call-graph. More...
 
class  CgalPoint
 a polygon vertex to be used with CGAL::Polygon_2. Derives from CGAL::Point_2 but is convertible to an from QPoint (which is used troughout the rest of the program). Also stores the index of the polygon vertex. More...
 
class  DecideWorkerJob
 worker job for executing the decision variant of the algorithm for simple polygons. More...
 
class  DoubleEndedQueue
 A double ended queue, or "Funnel". Used by the algorithm for Shortest Paths Trees (Guibas et al.). More...
 
struct  DummyTDS
 Dummy class acting as a default for template arguments (required by CGAL::Triangulation_data_structure_2) More...
 
class  OptimiseCurveWorkerJob
 worker job for executing the optimisation variant, or approximation variant, on curves (not on simple polygons). More...
 
class  OptimisePolyWorkerJob
 worker job for executing the optimisation variant, or approximation variant, of the algorithm for simple polygons. More...
 
struct  PartitionTraits
 type traits for a polygon partition Defines the type for Points and Polygons More...
 
class  PolygonFSPath
 a feasible-path for simple polygons. More...
 
class  PolygonShortestPaths
 compute Shortest-Paths-Tree on a polygon More...
 
class  PolygonShortestPathsFS
 Guibas' Algorithm with additional Free-Space computation. More...
 
struct  PolygonTraits
 type traits for CgalPolygon. Defines the type for Points. More...
 
class  PolygonUtilities
 a helper class for polygon analysis. More...
 
class  PolygonWorkerJob
 Abstract base class for executing the algorithm for simple polygons in a background thread. As any worker job, it may be interrupted by the user. More...
 
class  Segment
 Represents a polygon line segment from node i to j. More...
 
class  Triangulation
 Wrapper for CGAL::Triangulation_Data_Structure https://doc.cgal.org/latest/TDS_2/index.html. More...
 
class  Vertex_base
 base class for vertexes in a Triangulation Data Structure. More...
 

Typedefs

typedef CGAL::Exact_predicates_inexact_constructions_kernel Kernel
 
typedef CGAL::Polygon_2< PolygonTraitsCgalPolygon
 CGAL::Polygon_2 built upon custom type. More...
 
typedef std::list< CgalPolygonCgalPolygonList
 a list of CgalPolygons More...
 
typedef std::vector< int > Polygon
 Polygon a sub-set of vertex indexes. More...
 
typedef std::set< SegmentSegments
 a set of Segment objects More...
 
typedef std::list< PolygonPartition
 a partitioning of a polygon, that is a list of sub-sets More...
 

Functions

Algorithm::ptr newPolyAlgorithm (bool topo)
 factory method for creating a new algorithm object. Choose the appropriate implementation based on availability of multi-core and GPGPU processors. More...
 
std::ostream & operator<< (std::ostream &out, const frechet::poly::CgalPolygon &poly)
 print operator (for debugging) More...
 
std::ostream & operator<< (std::ostream &out, const frechet::poly::CgalPolygonList &polys)
 print operator (for debugging) More...
 
std::ostream & operator<< (std::ostream &out, const Segment &seg)
 print operator; for debuggin More...
 
print operators for debugging
std::ostream & operator<< (std::ostream &out, const Triangulation &tri)
 
std::ostream & operator<< (std::ostream &out, const Triangulation::Vertex_handle &v)
 
std::ostream & operator<< (std::ostream &out, const Triangulation::Face_handle &f)
 
std::ostream & operator<< (std::ostream &out, const Triangulation::Edge &e)
 
std::ostream & operator<< (std::ostream &out, const Triangulation::Edge_iterator &e)
 

Variables

static const int SOUTH_POLE_INDEX = -2
 artifical vertex used by Triangulation More...
 

Typedef Documentation

◆ CgalPolygon

typedef CGAL::Polygon_2<PolygonTraits> frechet::poly::CgalPolygon

CGAL::Polygon_2 built upon custom type.

Definition at line 95 of file poly_utils.h.

◆ CgalPolygonList

a list of CgalPolygons

Definition at line 97 of file poly_utils.h.

◆ Kernel

typedef CGAL::Exact_predicates_inexact_constructions_kernel frechet::poly::Kernel

CGAL computation kernel; predicates are exact, constructions are bound to have roundoff errors (we can't avoid those anyway)

Definition at line 25 of file poly_utils.h.

◆ Partition

typedef std::list<Polygon> frechet::poly::Partition

a partitioning of a polygon, that is a list of sub-sets

Definition at line 117 of file types.h.

◆ Polygon

typedef std::vector<int> frechet::poly::Polygon

Polygon a sub-set of vertex indexes.

Definition at line 113 of file types.h.

◆ Segments

typedef std::set<Segment> frechet::poly::Segments

a set of Segment objects

Definition at line 115 of file types.h.

Function Documentation

◆ newPolyAlgorithm()

Algorithm::ptr frechet::poly::newPolyAlgorithm ( bool  topo)

factory method for creating a new algorithm object. Choose the appropriate implementation based on availability of multi-core and GPGPU processors.

Parameters
topouse implementaion with topological sorting
Returns
a newly created instance of an algorithm

Definition at line 11 of file parallel.cpp.

◆ operator<<() [1/8]

std::ostream & frechet::poly::operator<< ( std::ostream &  out,
const Segment seg 
)

print operator; for debuggin

Parameters
outoutput stream
sega Segment object
Returns
out

Definition at line 672 of file algorithm.cpp.

◆ operator<<() [2/8]

std::ostream & frechet::poly::operator<< ( std::ostream &  out,
const frechet::poly::CgalPolygon poly 
)

print operator (for debugging)

Definition at line 338 of file poly_utils.cpp.

◆ operator<<() [3/8]

std::ostream & frechet::poly::operator<< ( std::ostream &  out,
const frechet::poly::CgalPolygonList polys 
)

print operator (for debugging)

Definition at line 351 of file poly_utils.cpp.

◆ operator<<() [4/8]

std::ostream & frechet::poly::operator<< ( std::ostream &  out,
const Triangulation tri 
)

Definition at line 697 of file triangulation.cpp.

◆ operator<<() [5/8]

std::ostream& frechet::poly::operator<< ( std::ostream &  out,
const Triangulation::Vertex_handle v 
)

◆ operator<<() [6/8]

std::ostream & frechet::poly::operator<< ( std::ostream &  out,
const Triangulation::Face_handle f 
)

Definition at line 709 of file triangulation.cpp.

◆ operator<<() [7/8]

std::ostream & frechet::poly::operator<< ( std::ostream &  out,
const Triangulation::Edge e 
)

Definition at line 717 of file triangulation.cpp.

◆ operator<<() [8/8]

std::ostream & frechet::poly::operator<< ( std::ostream &  out,
const Triangulation::Edge_iterator e 
)

Definition at line 729 of file triangulation.cpp.

Variable Documentation

◆ SOUTH_POLE_INDEX

const int frechet::poly::SOUTH_POLE_INDEX = -2
static

artifical vertex used by Triangulation

Definition at line 21 of file types.h.