GeometricGraph2 Class Reference

A simple geometric graph. More...

#include <geometricgraph.h>

Public Member Functions
	GeometricGraph2 ()
	Create an empty geometric graph.
	GeometricGraph2 (const QVector< Vector2 > &, bool=false)
	Create an empty geometric graph.
	GeometricGraph2 (const Mesh2 &)
	Create a geometric graph from a mesh.
void	AddEdge (int, int, double)
	Add an edge to the graph.
void	AddEdge (int, int)
	Add an edge to the graph.
int	Edges () const
	Return the number of edges.
QPoint	Edge (int) const
	Return the i-th edge as a pair or integers.
Segment2	GetSegment (int) const
	Return the i-th edge as a geometric segment.
GeometricGraph2	Kruskal () const
	Compute the minimum spanning tree using Kruskal's algorithm.
GeometricGraph2	Nearest () const
	Compute the nearest geometric graph.
GeometricGraph2	Urquhart () const
	Generate the Urquhart graph.
GeometricGraph2	Relative () const
	Compute the relative neighbor graph.
GeometricGraph2	Gabriel () const
	Compute the Gabriel graph.
GeometricGraph2	Gamma (double) const
	Compute the gamma-skeleton graph.
GeometricGraph2	Beta (double, bool=false) const
	Compute the beta-skeleton graph, either using a circle or lens based definition.
GeometricGraph2	SubNearest (const Vector2 &, int) const
	Compute the minimum spanning tree using Kruskal's algorithm.
GeometricGraph2	Delaunay () const
	Compute the Delaunay triangulation.
double	Weight () const
	Compute the global weight of the geometric graph.
bool	Exists (int, int) const
	Tests if an edge exists in the graph.
GeometricGraph2	Reverse () const
	Return the reversed geometric graph.
void	Draw (QGraphicsScene &) const
	Draw the cluster.

Protected Attributes
std::vector< WeightEdge >	edges
	Set of edges.

Friends
std::ostream &	operator<< (std::ostream &s, const GeometricGraph2 &g)
	Overloaded output-stream operator.

Detailed Description

A simple geometric graph.

Geometric graphs.

Constructor & Destructor Documentation

GeometricGraph2() [1/2]

GeometricGraph2::GeometricGraph2 ( const QVector< Vector2 > & v, bool complete = false )

explicit

Create an empty geometric graph.

Parameters

v	Vector set.
complete	Boolean to check if complete graph should be computed.

GeometricGraph2() [2/2]

GeometricGraph2::GeometricGraph2 ( const Mesh2 & mesh )

explicit

Create a geometric graph from a mesh.

Parameters

mesh

The mesh.

Member Function Documentation

AddEdge() [1/2]

void GeometricGraph2::AddEdge	(	int	a,
		int	b )

Add an edge to the graph.

Weight is computed from the points as the Euclidean distance

Parameters

a,b

Indexes.

AddEdge() [2/2]

void GeometricGraph2::AddEdge	(	int	a,
		int	b,
		double	w )

Add an edge to the graph.

Parameters

a,b	Indexes.
w	Weight.

Beta()

GeometricGraph2 GeometricGraph2::Beta	(	double	beta,
		bool	circle = false ) const

Compute the beta-skeleton graph, either using a circle or lens based definition.

The Gabriel graph is the closed 1-skeleton and the relative neighborhood graph is the open 2-skeleton.

Parameters

beta	Beta parameter, should be >1.
circle	Set to true to use the circle-based definiton, lens-based otherwise.

Delaunay()

GeometricGraph2 GeometricGraph2::Delaunay

(

)

const

Compute the Delaunay triangulation.

Note that this function simply uses Mesh2::Delaunay

See also

Mesh2::Delaunay

Draw()

void GeometricGraph2::Draw

(

QGraphicsScene &

scene

)

const

Draw the cluster.

Parameters

scene

Graphics scene.

Exists()

bool GeometricGraph2::Exists	(	int	a,
		int	b ) const

Tests if an edge exists in the graph.

Parameters

a,b	Vertex indexes.

Gabriel()

GeometricGraph2 GeometricGraph2::Gabriel

(

)

const

Compute the Gabriel graph.

The function does not use the Delaunay triangulation, its complexity is O(n^3).

Gamma()

GeometricGraph2 GeometricGraph2::Gamma

(

double

gamma

)

const

Compute the gamma-skeleton graph.

Parameters

gamma

Gamma parameter, should be >1.

Relative()

GeometricGraph2 GeometricGraph2::Relative

(

)

const

Compute the relative neighbor graph.

An undirected graph defined on a set of points in the Euclidean plane by connecting two points if there does not exist a third point that is closer to both those than they are to each other.

Toussaint, G. T. The relative neighborhood graph of a finite planar set. Pattern Recognition, 12 (4): 261–268, 1980.

Jaromczyk, J.W.; Toussaint, G.T. Relative neighborhood graphs and their relatives. Proceedings of IEEE, 80 (9): 1502-1517, 1992.

Reverse()

GeometricGraph2 GeometricGraph2::Reverse

(

)

const

Return the reversed geometric graph.

The graph has the same number of edges but with opposite directions, and preserves weigth.

Urquhart()

GeometricGraph2 GeometricGraph2::Urquhart

(

)

const

Generate the Urquhart graph.

Formed by removing the longest edge from every triangle in the Delaunay triangulation, it was originally proposed as a fast method to compute the relative neighborhood graph.

See also

Mest::Delaunay

Weight()

double GeometricGraph2::Weight

(

)

const

Compute the global weight of the geometric graph.

Weight is defined as the sum of the weights of the edges.

Friends And Related Symbol Documentation

operator<<

std::ostream & operator<< ( std::ostream & s, const GeometricGraph2 & g )

friend

Overloaded output-stream operator.

Parameters

g	Geometric graph.
s	Stream.