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< PolygonTraits >	CgalPolygon
	CGAL::Polygon_2 built upon custom type. More...

typedef std::list< CgalPolygon >	CgalPolygonList
	a list of CgalPolygons More...

typedef std::vector< int >	Polygon
	Polygon a sub-set of vertex indexes. More...

typedef std::set< Segment >	Segments
	a set of Segment objects More...

typedef std::list< Polygon >	Partition
	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

typedef std::list<CgalPolygon> frechet::poly::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

topo	use 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

out	output stream
seg	a 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.