Detailed Description

Free-Space connected components and their projections to the domain axes.

Used by the k-Frechet algorithm. Atfer computing the free-space diagram, we find connected components and project their bounding box to the x- and y-axis.

For finding connected component, we use a union-find structure. Free-space cells are connected if their adjacent free intervals are not empty.

Each component is identified by a unique ID of type component_id_t

Author: Peter Schäfer

Definition at line 27 of file components.h.

#include <components.h>

Public Types
typedef boost::disjoint_sets_with_storage	DisjointSet
	union-find structure, or disjoint set More...

typedef data::Array2D< data::IntervalPair >	IntervalArray

Public Member Functions
	Components (int n, int m)
	default constrcutor More...

void	clear ()
	clear the component set More...

component_id_t	representative (int i, int j)
	find the component ID of a cell More...

void	calculateComponents (FreeSpace &fs)
	calculate connected components More...

component_id_t	count () const

data::BitSet::iterator	begin () const

data::BitSet::iterator	end () const

data::BitSet::iterator	first () const

data::BitSet::iterator	last () const

const IntervalArray &	intervals () const

Static Public Attributes
static const component_id_t	NO_COMPONENT = (component_id_t)SIZE_MAX
	empty cells have an invalid component ID More...

Private Member Functions
component_id_t	componentID (int i, int j)
	get the component for a cell More...

component_id_t	assignComponent (const FreeSpace &fs, int i, int j)
	compute component ID for a cell More...

void	normalize ()
	normalize union-find structure. for each component, find the smallest representative. More...

Private Attributes
int	n
	number of vertexes in P. Number of grid columns is n-1. More...

int	m
	number of vertexes in Q. Number of grid rows is m-1. More...

DisjointSet	disjointSet
	disjoint set of component IDs. More...

IntervalArray	intervalArray
	has an entry for every cell (nxm) More...

data::BitSet	intervalSet
	contains the valid representatives (a subset of all cells) More...

Member Typedef Documentation

◆ DisjointSet

typedef boost::disjoint_sets_with_storage frechet::fs::Components::DisjointSet

union-find structure, or disjoint set

Definition at line 31 of file components.h.

◆ IntervalArray

typedef data::Array2D<data::IntervalPair> frechet::fs::Components::IntervalArray

maps components to their component bounding boxes. Bounding boxes are represented by a pair of intervals.

Definition at line 34 of file components.h.

Constructor & Destructor Documentation

◆ Components()

Components::Components	(	int	n,
		int	m
	)

default constrcutor

Parameters

n	number of vertexes in P
m	number of vertexes in Q

Definition at line 24 of file components.cpp.

Member Function Documentation

◆ assignComponent()

component_id_t Components::assignComponent	(	const FreeSpace &	fs,
		int	i,
		int	j
	)

private

compute component ID for a cell

Parameters

fs	free-space diagram
i	grid column
j	grid row

Returns: component ID for the cell

Examine one cell in the free-space diagram. Find connected neighbors and update the union-find set.

Definition at line 110 of file components.cpp.

◆ begin()

data::BitSet::iterator frechet::fs::Components::begin ( ) const

inline

Returns: iterator to the beginning of the component set

Definition at line 89 of file components.h.

◆ calculateComponents()

void Components::calculateComponents ( FreeSpace & fs )

calculate connected components

Parameters

fs	the underlying Free-space diagram

initially each cell is identified by their grid location. Then we start finding connected components using the union-find set.

Definition at line 56 of file components.cpp.

◆ clear()

void Components::clear ( )

clear the component set

Definition at line 34 of file components.cpp.

◆ componentID()

component_id_t Components::componentID	(	int	i,
		int	j
	)

private

get the component for a cell

Parameters

i	grid column
j	grid row

Returns: the component ID of a cell

component ID servers as identifier for the Union-Find structure and as index into intervals array.

Definition at line 20 of file components.cpp.

◆ count()

component_id_t frechet::fs::Components::count ( ) const

inline

Returns: total number of connected components

Definition at line 86 of file components.h.

◆ end()

data::BitSet::iterator frechet::fs::Components::end ( ) const

inline

Returns: iterator past the end of the component set

Definition at line 91 of file components.h.

◆ first()

data::BitSet::iterator frechet::fs::Components::first ( ) const

inline

Returns: iterator to the first entry of the component set

Definition at line 94 of file components.h.

◆ intervals()

const IntervalArray& frechet::fs::Components::intervals ( ) const

inline

Returns: bounding boxes for components

Definition at line 99 of file components.h.

◆ last()

data::BitSet::iterator frechet::fs::Components::last ( ) const

inline

Returns: iterator to the last entry of the component set

Definition at line 96 of file components.h.

◆ normalize()

void Components::normalize ( )

private

normalize union-find structure. for each component, find the smallest representative.

Definition at line 207 of file components.cpp.

◆ representative()

component_id_t Components::representative	(	int	i,
		int	j
	)

find the component ID of a cell

Parameters

i	grid column
j	grid row

Returns: the cell's component ID, or NO_COMPONENT

Definition at line 202 of file components.cpp.

Member Data Documentation

◆ disjointSet

DisjointSet frechet::fs::Components::disjointSet

private

disjoint set of component IDs.

Definition at line 39 of file components.h.

◆ intervalArray

IntervalArray frechet::fs::Components::intervalArray

private

has an entry for every cell (nxm)

Alternatively, we could use a hash map <component_id_t,IntervalPair> and save some memory. Memory requirements are modest, however.

Definition at line 46 of file components.h.

◆ intervalSet

data::BitSet frechet::fs::Components::intervalSet

private

contains the valid representatives (a subset of all cells)

Definition at line 48 of file components.h.

◆ m

int frechet::fs::Components::m

private

number of vertexes in Q. Number of grid rows is m-1.

Definition at line 38 of file components.h.

◆ n

int frechet::fs::Components::n

private

number of vertexes in P. Number of grid columns is n-1.

Definition at line 37 of file components.h.

◆ NO_COMPONENT

const component_id_t Components::NO_COMPONENT = (component_id_t)SIZE_MAX

static

empty cells have an invalid component ID

Definition at line 60 of file components.h.

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

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

Detailed Description

Public Types

Public Member Functions

Static Public Attributes

Private Member Functions

Private Attributes

Member Typedef Documentation

◆ DisjointSet

◆ IntervalArray

Constructor & Destructor Documentation

◆ Components()

Member Function Documentation

◆ assignComponent()

◆ begin()

◆ calculateComponents()

◆ clear()

◆ componentID()

◆ count()

◆ end()

◆ first()

◆ intervals()

◆ last()

◆ normalize()

◆ representative()

Member Data Documentation

◆ disjointSet

◆ intervalArray

◆ intervalSet

◆ m

◆ n

◆ NO_COMPONENT