Detailed Description

compute Shortest-Paths-Tree on a polygon

Given a Polygon, a Triangulation and a set of points: find all shortest paths from one point to all other points.

This is a slight extension of an algorithm by Guibas, Hershberger et al. Based on a "funnel" algorithm by Lee and Preparata.

Search structure is not a finger tree, but a specialized double-ended-queue (because it is much easier to implement).

The class provides some abstract functions that derived classes can override to implement custom activities. (this is where the Free-Space will be updated)

Author: Peter Schäfer

Definition at line 32 of file shortest_paths.h.

#include <shortest_paths.h>

Inherited by frechet::poly::PolygonShortestPathsFS.

Public Types
typedef Triangulation::Vertex_handle	Vertex_handle

typedef Triangulation::Face_handle	Face_handle

typedef Triangulation::Face_circulator	Face_circulator

typedef Triangulation::Edge	Edge

typedef DoubleEndedQueue< Vertex_handle >	Funnel

Public Member Functions
	PolygonShortestPaths (Triangulation &atri)
	default constructor More...

Triangulation &	triangulation () const

void	findShortestPaths (Vertex_handle start_point)
	traverse the polygon and report found paths More...

Curve	find1ShortestPath (double p1, double p2)
	compute the shortest path between two points on the boundary of the polygon More...

virtual void	shortestPath ()
	callback-function when a new shortest-path has been found. derived classes hook in to perform additional computations More...

virtual void	undo ()
	callback-function when backtrcking derived classes hook in to perform additional computations More...

void	assertFunnel () const
	assertion for unit testing: is the Funnel in a consistent state? More...

const Funnel &	getFunnel () const
	for debugging only: access to funnel More...

Static Public Member Functions
template<typename Float >
static int	halfplaneTest (Vertex_handle a, Vertex_handle b, Vertex_handle p)
	half-plane test. More...

Protected Member Functions
void	search (Vertex_handle start_point, Face_handle f)
	compute the shortest-paths tree More...

void	search (Edge e)
	compute the shortest-paths tree More...

virtual bool	updateSPSegment (Vertex_handle prev, Vertex_handle v)
	called whenever a ne segment is added to the shortest path tree; hook for derived classes More...

int	findTangent (Vertex_handle v) const
	find a tangent from a point to the funnel More...

int	findTangentLeft (int t1, int t2, Vertex_handle v) const
	find a tangent from a point to the left part of the funnel More...

int	findTangentRight (int t1, int t2, Vertex_handle v) const
	find a tangent from a point to the right part of the funnel More...

bool	isTangent (int t, Vertex_handle v) const
	tangent test More...

Protected Attributes
Triangulation &	tri
	the Triangulation More...

Funnel	funnel
	the Funnel More...

Member Typedef Documentation

◆ Edge

typedef Triangulation::Edge frechet::poly::PolygonShortestPaths::Edge

Definition at line 38 of file shortest_paths.h.

◆ Face_circulator

typedef Triangulation::Face_circulator frechet::poly::PolygonShortestPaths::Face_circulator

Definition at line 37 of file shortest_paths.h.

◆ Face_handle

typedef Triangulation::Face_handle frechet::poly::PolygonShortestPaths::Face_handle

Definition at line 36 of file shortest_paths.h.

◆ Funnel

typedef DoubleEndedQueue<Vertex_handle> frechet::poly::PolygonShortestPaths::Funnel

Definition at line 39 of file shortest_paths.h.

◆ Vertex_handle

typedef Triangulation::Vertex_handle frechet::poly::PolygonShortestPaths::Vertex_handle

Definition at line 35 of file shortest_paths.h.

Constructor & Destructor Documentation

◆ PolygonShortestPaths()

PolygonShortestPaths::PolygonShortestPaths ( Triangulation & atri )

default constructor

Parameters

atri	a triangulation of a polygon

Definition at line 15 of file shortest_paths.cpp.

Member Function Documentation

◆ assertFunnel()

void PolygonShortestPaths::assertFunnel ( ) const

assertion for unit testing: is the Funnel in a consistent state?

both parts of the funnel should be convex and linked with prev pointers

Definition at line 445 of file shortest_paths.cpp.

◆ find1ShortestPath()

frechet::Curve PolygonShortestPaths::find1ShortestPath	(	double	p1,
		double	p2
	)

compute the shortest path between two points on the boundary of the polygon

Parameters

p1	offset of first point
p2	offset of first point

Returns: the curve representing the shortest path between p1 and p2

Definition at line 41 of file shortest_paths.cpp.

◆ findShortestPaths()

void PolygonShortestPaths::findShortestPaths ( Vertex_handle start_point )

traverse the polygon and report found paths

Parameters

start_point starting point of the algorithm

Perform a Depth-First-Search of the Dual Tree i.e. we follow the faces of the triangulation and update our funnel as we go.

Definition at line 66 of file shortest_paths.cpp.

◆ findTangent()

int PolygonShortestPaths::findTangent ( Vertex_handle v ) const

protected

find a tangent from a point to the funnel

binary search the funnel for a tangent segment

Parameters

v	next point to consider

Returns: index in funnel, relative to apex

Definition at line 370 of file shortest_paths.cpp.

◆ findTangentLeft()

int PolygonShortestPaths::findTangentLeft	(	int	t1,
		int	t2,
		Vertex_handle	v
	)		const

protected

find a tangent from a point to the left part of the funnel

Parameters

t1	first point in left part
t2	last point in left part
v	next point to consider

Returns: index in funnel, or 0

Definition at line 403 of file shortest_paths.cpp.

◆ findTangentRight()

int PolygonShortestPaths::findTangentRight	(	int	t1,
		int	t2,
		Vertex_handle	v
	)		const

protected

find a tangent from a point to the right part of the funnel

Parameters

t1	first point in right part
t2	last point in right part
v	next point to consider

Returns: index in funnel, or 0

Definition at line 423 of file shortest_paths.cpp.

◆ getFunnel()

const Funnel& frechet::poly::PolygonShortestPaths::getFunnel ( ) const

inline

for debugging only: access to funnel

Returns: the double-ended queue use by the algorithm

Definition at line 94 of file shortest_paths.h.

◆ halfplaneTest()

template<typename Float >

int frechet::poly::PolygonShortestPaths::halfplaneTest	(	Vertex_handle	a,
		Vertex_handle	b,
		Vertex_handle	p
	)

static

half-plane test.

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

Parameters

a	first end of line segment
b	second end of line segment
p	point to test for

Template Parameters

Float floating point type for intermediate computation (could be float,double,long double,...)

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-down coordinate system!)

Definition at line 249 of file shortest_paths.h.

◆ isTangent()

bool PolygonShortestPaths::isTangent	(	int	t,
		Vertex_handle	v
	)		const

protected

tangent test

Parameters

t	index in funnel
v	next point to consider

Returns: true if the line through v and t is a tangent

Note: hpt==0 means colinear points. We do_not consider them as a tangent; we trust that the triangulator produces no such degenerated triangles.

Definition at line 343 of file shortest_paths.cpp.

◆ search() [1/2]

void PolygonShortestPaths::search	(	Vertex_handle	start_point,
		Face_handle	f
	)

protected

compute the shortest-paths tree

Parameters

start_point	start point of the algorithm
f	start face

Definition at line 267 of file shortest_paths.cpp.

◆ search() [2/2]

void PolygonShortestPaths::search ( Edge e )

protected

compute the shortest-paths tree

Parameters

e	start edge

Definition at line 298 of file shortest_paths.cpp.

◆ shortestPath()

virtual void frechet::poly::PolygonShortestPaths::shortestPath ( )

inlinevirtual

callback-function when a new shortest-path has been found. derived classes hook in to perform additional computations

Definition at line 79 of file shortest_paths.h.

◆ triangulation()

Triangulation& frechet::poly::PolygonShortestPaths::triangulation ( ) const

inline

Returns: the underlying triangulation

Definition at line 57 of file shortest_paths.h.

◆ undo()

virtual void frechet::poly::PolygonShortestPaths::undo ( )

inlinevirtual

callback-function when backtrcking derived classes hook in to perform additional computations

Definition at line 84 of file shortest_paths.h.

◆ updateSPSegment()

bool PolygonShortestPaths::updateSPSegment	(	Vertex_handle	prev,
		Vertex_handle	v
	)

protectedvirtual

called whenever a ne segment is added to the shortest path tree; hook for derived classes

Parameters

prev	first vertex of the segment
v	second vertex of the segment

Returns: true if the tree segment has changed

Reimplemented in frechet::poly::PolygonShortestPathsFS.

Definition at line 85 of file shortest_paths.cpp.

Member Data Documentation

◆ funnel

Funnel frechet::poly::PolygonShortestPaths::funnel

protected

the Funnel

Definition at line 45 of file shortest_paths.h.

◆ tri

Triangulation& frechet::poly::PolygonShortestPaths::tri

protected

the Triangulation

Definition at line 43 of file shortest_paths.h.

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

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

Detailed Description

Public Types

Public Member Functions

Static Public Member Functions

Protected Member Functions

Protected Attributes

Member Typedef Documentation

◆ Edge

◆ Face_circulator

◆ Face_handle

◆ Funnel

◆ Vertex_handle

Constructor & Destructor Documentation

◆ PolygonShortestPaths()

Member Function Documentation

◆ assertFunnel()

◆ find1ShortestPath()

◆ findShortestPaths()

◆ findTangent()

◆ findTangentLeft()

◆ findTangentRight()

◆ getFunnel()

◆ halfplaneTest()

◆ isTangent()

◆ search() [1/2]

◆ search() [2/2]

◆ shortestPath()

◆ triangulation()

◆ undo()

◆ updateSPSegment()

Member Data Documentation

◆ funnel

◆ tri