PlanarGC  1.0.2
 All Data Structures Functions Variables Enumerations Enumerator Friends Pages
CutGrid Class Reference

#include <CutGrid.h>

+ Inheritance diagram for CutGrid:

Public Types

enum  EDir {
  DIR_EAST,
  DIR_NORTH,
  DIR_WEST,
  DIR_SOUTH
}

Public Member Functions

 CutGrid (int nRows, int nCols)
virtual ~CutGrid ()
void setSource (int row, int col)
void setSink (int row, int col)
void getSource (int &row, int &col)
void getSink (int &row, int &col)
void setEdgeCostFunction (CapType(*edgeCostFunc)(int row, int col, EDir dir))
virtual CapType edgeCost (int row, int col, EDir dir)
double getMaxFlow ()
CutPlanar::ELabel getLabel (int row, int col)
void getLabels (CutPlanar::ELabel *lmask)

Detailed Description

CutGrid provides an interface to define graphs on a regular, rectangular grid. The overall assumption is that every node of the grid coincides with a vertex of the planar graph and vice-versa. Moreover, we assume that besides the boundary vertices every vertex has four edges leaving this vertex following the four geographic directions.

Examples:
cutgrid.cpp.

Member Enumeration Documentation

The four unique directions that exist in a regular grid are enumerated in EDir and are named with respect to their geographic direction.

Enumerator:
DIR_EAST 

East of position (row,col) is (row,col+1).

DIR_NORTH 

North of position (row,col) is (row-1,col).

DIR_WEST 

West of position (row,col) is (row,col-1).

DIR_SOUTH 

South of position (row,col) is (row+1,col).

Constructor & Destructor Documentation

CutGrid::CutGrid ( int  nRows,
int  nCols 
)

the constructor creates a graph of nRows times nCols vertices and the associated faces and edges. One only has to take care of the edges' capacity. This can be done by either overwriting the virtual method edgeCost within an inherited class of CutGrid or by calling setEdgeCostFunction directly. Even though the second approach is more convenient, it consumes more time and therefore the first approach is recommended for runtime-sensitive applications.

References PlanarVertex::setEdgesCCW().

CutGrid::~CutGrid ( )
virtual

the destructor frees all the memory that was reserved for the vertices, edges and faces created by the constructor.

Member Function Documentation

void CutGrid::setSource ( int  row,
int  col 
)

defines the source within the grid.

Referenced by CutSegment::setSourceSink().

void CutGrid::setSink ( int  row,
int  col 
)

defines the source within the grid.

Referenced by CutSegment::setSourceSink().

void CutGrid::getSource ( int &  row,
int &  col 
)

writes the coordinates of the source into the two parameters row and col.

void CutGrid::getSink ( int &  row,
int &  col 
)

writes the coordinates of the sink into the two parameters row and col.

void CutGrid::setEdgeCostFunction ( CapType(*)(int row, int col, EDir dir)  edgeCostFunc)

defines the edge costs of the whole grid.
The function edgeCostFunc has to provide the cost of every outgoing edge that leaves the vertex at position (row,col) in direction dir.

Note
If edgeCost is overwritten, the functionality of this function gets lost.
double CutGrid::edgeCost ( int  row,
int  col,
EDir  dir 
)
virtual

in the case that setEdgeCostFunction is too slow, one can overwrite this function in order to define the edge cost directly within the class.

Note
If this function is overwritten, the functionality of setEdgeCostFunction gets lost.

Referenced by getMaxFlow().

double CutGrid::getMaxFlow ( )

returns the maximum flow of the defined grid graph.

References CutPlanar::CHECK_NONE, DIR_EAST, DIR_NORTH, DIR_SOUTH, DIR_WEST, edgeCost(), CutPlanar::getMaxFlow(), and CutPlanar::initialize().

Referenced by CutSegment::segment().

CutPlanar::ELabel CutGrid::getLabel ( int  row,
int  col 
)

returns the final label of a specific vertex after computing the maximum flow.

References CutPlanar::getLabel().

void CutGrid::getLabels ( CutPlanar::ELabel lmask)

writes the value of every grid's label into the pre-allocated lmask. The method uses the column-wise format, i.e., the label of vertex (0,1) is stored in lmask(1).

References CutPlanar::getLabel().

© 2009 - 2013 by Eno Töppe, Frank R. Schmidt
generated by Doxygen