Detailed Description

The FreeSpace class models the Free-Space Diagram calculated from two curves.

Holds a two-dimensional array of free-space Cell objects.

For k-Frechet we keep a map of connected components.

Author: Peter Schäfer

Definition at line 83 of file freespace.h.

#include <freespace.h>

Public Types
typedef boost::shared_ptr< FreeSpace >	ptr
	smart pointer to FreeSpace object More...

Public Member Functions
	FreeSpace (const Curve &ap, const Curve &aq)
	default constructor with two input curves More...

	FreeSpace (const FreeSpace &that)
	copy constructor More...

Components &	components ()

size_t	component (int i, int j)
	find the component ID for a cell. Empty cells return NO_COMPONENT. More...

void	calculateFreeSpace (double epsilon)
	calculate all free space intervals More...

void	calculateBounds (double epsilon)
	calculate the bounding boxes of the free-space areas (k-Frechet only) More...

Cell &	cell (int x, int y)

const Cell &	cell (int x, int y) const

bool	cellEmptyIntervals (int i, int j) const
	test if a cell is empty More...

bool	cellEmptyBounds (int i, int j) const
	test if the bounding box of a cell is empty More...

bool	cellFull (int i, int j) const
	test if a cell is completely covered by the free-space area More...

bool	isParallel (int i, int j) const
	test if the free-space area of a cell is a degenerate ellipse, i.e. two parallel lines. This is the case if the determinant is zero. More...

bool	isAlmostParallel (int i, int j) const
	test if the free-space area of a cell is a almost degenerate ellipse, This is the case if the determinant is very close to zero. For visualisation, the ellipse is replaced by two parallel lines. More...

bool	wrapRight () const
	if P is a closed curve, the free space diagram wraps at right edge More...

bool	wrapTop () const
	if Q is a closed curve, the free space diagram wraps at top edge More...

QRectF	segmentBounds (int i, int j)

std::list< data::Interval >	collectFreeVerticalIntervals (int i) const
	traverse one column of the free-space and find all connected intervals. This method is needed by the algorithm for simple polygons during the computation of valid placements. More...

template<typename Float >
void	calculateEllipseBoundaries (const Point &p1, const Point &p2, const Point &q1, const Point &q2, double epsilon, double lambda[2])

Static Public Member Functions
template<typename Float >
static void	calculateFreeSpaceSegment (const Point &p, const Point &q, const Point &r, double epsilon, data::Interval &result)
	compute intervals for one point and segment. As parameters we expect a point on one curve (P,or Q) and a line segment on the other curve (Q,or P). More...

static void	fixBorderCase (data::Interval N, data::Interval E, data::Interval S, data::Interval W)
	fix border case at the joint of four intervals More...

Public Attributes
const Curve &	P
	first input curve More...

const Curve &	Q
	second input curve More...

const int	n
	number of vertexes in P More...

const int	m
	number of vertexes in Q More...

Static Public Attributes
static const QRectF	UNIT_RECT
	the unit rectangle [0,1]x[0,1] More...

static const double	DET_MINIMUM = 1e-12
	minimum determinant to avoid roundoff errors More...

Private Member Functions
double	determinant (int i, int j) const

template<typename Float >
void	calculateEllipseBoundaries (const Point &p1, const Point &p2, const Point &q1, const Point &q2, double epsilon, double lambda[2])
	compute the bounding box of one cell in the free-space are. As parameters we expect two segments of P and Q More...

Private Attributes
data::Array2D< Cell >	cells
	free line segments as Intervals subset of [0..1] More...

Components	_components
	tracks connected components for k-Frechet algorithm More...

Member Typedef Documentation

◆ ptr

typedef boost::shared_ptr<FreeSpace> frechet::fs::FreeSpace::ptr

smart pointer to FreeSpace object

Definition at line 92 of file freespace.h.

Constructor & Destructor Documentation

◆ FreeSpace() [1/2]

FreeSpace::FreeSpace	(	const Curve &	ap,
		const Curve &	aq
	)

default constructor with two input curves

Parameters

ap	first input curve
aq	second input curve

Definition at line 14 of file freespace.cpp.

◆ FreeSpace() [2/2]

FreeSpace::FreeSpace ( const FreeSpace & that )

copy constructor

Parameters

that	object to copy from

Definition at line 22 of file freespace.cpp.

Member Function Documentation

◆ calculateBounds()

void FreeSpace::calculateBounds ( double epsilon )

calculate the bounding boxes of the free-space areas (k-Frechet only)

Parameters

epsilon current value of epsilon

Definition at line 112 of file freespace.cpp.

◆ calculateEllipseBoundaries() [1/2]

template<typename Float >

void frechet::fs::FreeSpace::calculateEllipseBoundaries	(	const Point &	p1,
		const Point &	p2,
		const Point &	q1,
		const Point &	q2,
		double	epsilon,
		double	lambda[2]
	)

Definition at line 281 of file freespace.cpp.

◆ calculateEllipseBoundaries() [2/2]

template<typename Float >

void frechet::fs::FreeSpace::calculateEllipseBoundaries	(	const Point &	p1,
		const Point &	p2,
		const Point &	q1,
		const Point &	q2,
		double	epsilon,
		double	lambda[2]
	)

private

compute the bounding box of one cell in the free-space are. As parameters we expect two segments of P and Q

Parameters

p1	start point of segment on P
p2	end point of segment on P
q1	start point of segment on Q
q2	end point of segment on Q
epsilon	value of epsilon
lambda	on return, holds two bounding intervals 'long double' values may be used for improved accuracy. End results are always 'double' precision.

Template Parameters

Float floating point type for intermediate results.

◆ calculateFreeSpace()

void FreeSpace::calculateFreeSpace ( double epsilon )

calculate all free space intervals

Parameters

epsilon current value of epsilon

Supports parallel computation. On multi-core systems, the computation is distributed over all processors. Each processor copmutes a number of columns of the free-space.

Definition at line 35 of file freespace.cpp.

◆ calculateFreeSpaceSegment()

template<typename Float >

void frechet::fs::FreeSpace::calculateFreeSpaceSegment	(	const Point &	p,
		const Point &	q,
		const Point &	r,
		double	epsilon,
		data::Interval &	result
	)

static

compute intervals for one point and segment. As parameters we expect a point on one curve (P,or Q) and a line segment on the other curve (Q,or P).

Parameters

p	point on P (resp. Q)
q	start of segment on Q (resp. P)
r	end of segment on Q (resp. P)
epsilon	value of epsilon

Template Parameters

Float floating point type for intermediate results. 'long double' values may be used for improved accuracy. End results are always 'double' precision.

Parameters

result on return, holds the free-space interval (L_ij, resp. B_ij)

Definition at line 8 of file freespace_impl.h.

◆ cell() [1/2]

Cell& frechet::fs::FreeSpace::cell	(	int	x,
		int	y
	)

inline

Parameters

x	grid column
y	grid row

Returns: the free-space data for a cell

Definition at line 160 of file freespace.h.

◆ cell() [2/2]

const Cell& frechet::fs::FreeSpace::cell	(	int	x,
		int	y
	)		const

inline

Parameters

x	grid column
y	grid row

Returns: the free-space data for a cell

Definition at line 170 of file freespace.h.

◆ cellEmptyBounds()

bool FreeSpace::cellEmptyBounds	(	int	i,
		int	j
	)		const

test if the bounding box of a cell is empty

Parameters

i	grid column
j	grid row

Returns: true if all four bounding intervals are empty

Definition at line 174 of file freespace.cpp.

◆ cellEmptyIntervals()

bool FreeSpace::cellEmptyIntervals	(	int	i,
		int	j
	)		const

test if a cell is empty

Parameters

i	grid column
j	grid row

Returns: true if all four intervals are empty

Definition at line 182 of file freespace.cpp.

◆ cellFull()

bool FreeSpace::cellFull	(	int	i,
		int	j
	)		const

test if a cell is completely covered by the free-space area

Parameters

i	grid column
j	grid row

Returns: true if the cell is full

Definition at line 190 of file freespace.cpp.

◆ collectFreeVerticalIntervals()

std::list< Interval > FreeSpace::collectFreeVerticalIntervals ( int i ) const

traverse one column of the free-space and find all connected intervals. This method is needed by the algorithm for simple polygons during the computation of valid placements.

Parameters

i	grid column

Returns: a list of connected intervals in a given column

Definition at line 217 of file freespace.cpp.

◆ component()

size_t frechet::fs::FreeSpace::component	(	int	i,
		int	j
	)

inline

find the component ID for a cell. Empty cells return NO_COMPONENT.

Parameters

i	grid column
j	grid row

Returns: the component representative ("ID")

Definition at line 133 of file freespace.h.

◆ components()

Components& frechet::fs::FreeSpace::components ( )

inline

Returns: map of connected components (used by k-Frechet algorithm)

Definition at line 124 of file freespace.h.

◆ determinant()

double FreeSpace::determinant	(	int	i,
		int	j
	)		const

private

Parameters

i	grid column
j	grid row

Returns: determinant of the ellipse transform

Definition at line 200 of file freespace.cpp.

◆ fixBorderCase()

void FreeSpace::fixBorderCase	(	data::Interval *	N,
		data::Interval *	E,
		data::Interval *	S,
		data::Interval *	W
	)

static

fix border case at the joint of four intervals

Parameters

N	north interval
E	east interval
S	south interval
W	west interval

If (0,0) is in L, it must also be in B. ...unless it slipped out by numerical precision.

We make sure that adjacent intervals are consistent. This is especially important for "critical values".

Definition at line 252 of file freespace.cpp.

◆ isAlmostParallel()

bool frechet::fs::FreeSpace::isAlmostParallel	(	int	i,
		int	j
	)		const

inline

test if the free-space area of a cell is a almost degenerate ellipse, This is the case if the determinant is very close to zero. For visualisation, the ellipse is replaced by two parallel lines.

Parameters

i	grid column
j	grid row

Returns: true if the free-space area is "degenerate"

Definition at line 217 of file freespace.h.

◆ isParallel()

bool frechet::fs::FreeSpace::isParallel	(	int	i,
		int	j
	)		const

inline

test if the free-space area of a cell is a degenerate ellipse, i.e. two parallel lines. This is the case if the determinant is zero.

Parameters

i	grid column
j	grid row

Returns: true if the free-space area is "degenerate"

Definition at line 205 of file freespace.h.

◆ segmentBounds()

QRectF FreeSpace::segmentBounds	(	int	i,
		int	j
	)

Parameters

i	grid column
j	grid row

Returns: bounding rectangle of a free-space cell

Definition at line 211 of file freespace.cpp.

◆ wrapRight()

bool frechet::fs::FreeSpace::wrapRight ( ) const

inline

if P is a closed curve, the free space diagram wraps at right edge

Returns: true if the free-space wraps at the right edge

Definition at line 225 of file freespace.h.

◆ wrapTop()

bool frechet::fs::FreeSpace::wrapTop ( ) const

inline

if Q is a closed curve, the free space diagram wraps at top edge

Returns: true if the free-space wraps at the right edge

Definition at line 230 of file freespace.h.

Member Data Documentation

◆ _components

Components frechet::fs::FreeSpace::_components

private

tracks connected components for k-Frechet algorithm

Definition at line 108 of file freespace.h.

◆ cells

data::Array2D<Cell> frechet::fs::FreeSpace::cells

private

free line segments as Intervals subset of [0..1]

Question: Is is really necessary to store the whole array of cells? A workings sets of two columns would be sufficient.

Answer: the algorithm for simple polygons needs the complete information. Memory requirements are modest, anywway.

Definition at line 106 of file freespace.h.

◆ DET_MINIMUM

const double FreeSpace::DET_MINIMUM = 1e-12

static

minimum determinant to avoid roundoff errors

Definition at line 97 of file freespace.h.

◆ m

const int frechet::fs::FreeSpace::m

number of vertexes in Q

Definition at line 89 of file freespace.h.

◆ n

const int frechet::fs::FreeSpace::n

number of vertexes in P

Definition at line 88 of file freespace.h.

◆ P

const Curve& frechet::fs::FreeSpace::P

first input curve

Definition at line 86 of file freespace.h.

◆ Q

const Curve& frechet::fs::FreeSpace::Q

second input curve

Definition at line 87 of file freespace.h.

◆ UNIT_RECT

const QRectF FreeSpace::UNIT_RECT

static

the unit rectangle [0,1]x[0,1]

Definition at line 95 of file freespace.h.

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

include/frechet/freespace/freespace.h
src/frechet/freespace/freespace.cpp
include/frechet/freespace/freespace_impl.h

Detailed Description

Public Types

Public Member Functions

Static Public Member Functions

Public Attributes

Static Public Attributes

Private Member Functions

Private Attributes

Member Typedef Documentation

◆ ptr

Constructor & Destructor Documentation

◆ FreeSpace() [1/2]

◆ FreeSpace() [2/2]

Member Function Documentation

◆ calculateBounds()

◆ calculateEllipseBoundaries() [1/2]

◆ calculateEllipseBoundaries() [2/2]

◆ calculateFreeSpace()

◆ calculateFreeSpaceSegment()

◆ cell() [1/2]

◆ cell() [2/2]

◆ cellEmptyBounds()

◆ cellEmptyIntervals()

◆ cellFull()

◆ collectFreeVerticalIntervals()

◆ component()

◆ components()

◆ determinant()

◆ fixBorderCase()

◆ isAlmostParallel()

◆ isParallel()

◆ segmentBounds()

◆ wrapRight()

◆ wrapTop()

Member Data Documentation

◆ _components

◆ cells

◆ DET_MINIMUM

◆ m

◆ n

◆ P

◆ Q

◆ UNIT_RECT