pbetagraph

Builds the beta graph.

Synopsis

pbetagraph beta [-m mask] [gr_in|-] [gr_out|-]

Description

pbetagraph builds the beta graph of the input graph gr_in. A beta graph is a graph where edges that are considered as too long are cut. The principle is to cut an edge if the circumcircle centered on the node contains another node. The circumcircle between a node i and a node j is defined as follows:

   center=(1-beta/2)*p(i)+beta/2*p(j)
   radius=beta/2*distance(p(p(i),p(j))

where distance is the euclidean distance, and beta specifies the size of the intersection circle:

if beta=1 the result is the Gabriel graph.
if beta=2 the result is Relative Neighbor Graph.

The node values are kept in the output graph, whereas the edge weight values are set to 1.

Parameters

beta is an integer from [0..2] that specifies the radius of the intersection circle.

Inputs

gr_in: a graph.

Outputs

gr_out: a graph.

Result

Returns SUCCESS or FAILURE.

Examples

Calculates the Delaunay graph from the centers of mass of tangram pieces and then extracts the beta graphe:

   pbinarization 90 1e30 tangram.pan a.pan
   plabeling 8 a.pan r1.pan
   pcenterofmass r1.pan r2.pan
   pdelaunay r2.pan g2.pan
   pbetagraph 1 g2.pan g3.pan

C++ prototype

Errc PBetaGraph( const Graph2d &gr_in, Graph &gr_out, float beta );

Version française

Construction du béta-graphe d'un graphe.

Author: François Angot