QTree.pm

Summary
QTree.pm
BE4::QTreeRepresentation of a quad tree image pyramid : pyramid’s image = Node
Constructors
newQTree constructor.
_initChecks and stores informations.
_loadDetermines all nodes from the bottom level to the top level, thanks to the data source.
Nodes determination methods
identifyBottomNodesCalculate all nodes in bottom level concerned by the datasource (tiles which touch the data source extent or provided in a file).
identifyAboveNodesCalculate all nodes in above levels.
Compute methods
computeYourselfDetermine codes and weights for each node of the current QTree, and share work on scripts, so as to optimize execution time.
computeBranchRecursive method, which allow to browse tree downward.
computeBottomImageTreats a bottom node : determine code or weight.
computeAboveImageTreats an above node (different to the bottom level) : determine code or weight.
Writer methods
writeCodeRecursive method, which allow to browse tree (downward) and write commands in associated node’s script.
Cut level methods
shareNodesOnJobsDetermine the cutLevel to optimize sharing into scripts and execution time.
Getters - Setters
getDataSource
getPyramid
getCutLevelID
getTopID
getTopOrder
getBottomOrder
getScriptFinisher
containsNodeReturns a boolean : TRUE if the node belong to this tree, FALSE otherwise (if a parameter is not defined too).
updateBBoxCompare provided and stored extrems coordinates and update values.
getPossibleChildrenReturns a Node array, containing children (length is always 4, with undefined value for children which don’t exist), an empty array if the node is a leaf.
getChildrenReturns a Node array, containing real children (max length = 4), an empty array if the node is a leaf.
getNodesOfLevelReturns a Node array, contaning all nodes of the provided level.
getNodesOfTopLevel
Export methods
exportLevelsForScriptDefine levels into bash varaiables
exportForDebugReturns all informations about the quad tree.

BE4::QTree

Exporter
BE4::QTree

Representation of a quad tree image pyramid : pyramid’s image = Node

To generate this kind of graph, we use :

  • jobNumber scripts : to generate and format image from the bottom level to the cut level.
  • 1 script (finisher) : to generate and format image from the cut level to the top level.

=> jobNumber + 1 scripts

Organization in the Forest scripts’ array :

As a tree, a node has just one parent.  As a QUAD tree, the parent belong to the above level and a node has 4 children at most.

Link between a node and his children or his father is trivial, and needn’t to be store :

  • To know parent’s indices, we divide own indices by 2 (and keep floor), and the level is the just above one
  • To know 4 possible chlidren’s, in the just below level :
i*2, j*2
i*2, j*2 + 1
i*2 + 1, j*2
i*2 + 1, j*2 + 1

Using

use BE4::QTree;

# QTree object creation
my $objQTree = BE4::QTree->new($objForest, $objDataSource, $objPyramid, $objCommands);

...

# Fill each node with computing code, weight, share job on scripts
$objQTree->computeYourself();

Attributes

forestForest - Forest which this tree belong to.
pyramidPyramid - Pyramid linked to this tree.
commandsCommands - Command to use to generate images.
datasourceDataSource - Data source to use to define bottom level nodes and generate them.
bboxdouble array - Datasource bbox, [xmin,ymin,xmax,ymax], in TMS’ SRS
nodesNode hash - Structure is:
level1 => {
   c1_r2 => n1,
   c2_r2 => n2,
   c3_r2 => n3, ...}
level2 => {
   c1_r2 => n4,
   c2_r2 => n5, ...}

cX : node's column
rX : node's row
nX : BE4::Node
cutLevelIDstring - Cut level identifiant.  To parallelize work, split scripts will generate cache from the bottom to this level.  Script finisher will be generate from this above, to top.
bottomIDstring - Bottom level identifiant
topIDstring - Top level identifiant
Summary
Constructors
newQTree constructor.
_initChecks and stores informations.
_loadDetermines all nodes from the bottom level to the top level, thanks to the data source.
Nodes determination methods
identifyBottomNodesCalculate all nodes in bottom level concerned by the datasource (tiles which touch the data source extent or provided in a file).
identifyAboveNodesCalculate all nodes in above levels.
Compute methods
computeYourselfDetermine codes and weights for each node of the current QTree, and share work on scripts, so as to optimize execution time.
computeBranchRecursive method, which allow to browse tree downward.
computeBottomImageTreats a bottom node : determine code or weight.
computeAboveImageTreats an above node (different to the bottom level) : determine code or weight.
Writer methods
writeCodeRecursive method, which allow to browse tree (downward) and write commands in associated node’s script.
Cut level methods
shareNodesOnJobsDetermine the cutLevel to optimize sharing into scripts and execution time.
Getters - Setters
getDataSource
getPyramid
getCutLevelID
getTopID
getTopOrder
getBottomOrder
getScriptFinisher
containsNodeReturns a boolean : TRUE if the node belong to this tree, FALSE otherwise (if a parameter is not defined too).
updateBBoxCompare provided and stored extrems coordinates and update values.
getPossibleChildrenReturns a Node array, containing children (length is always 4, with undefined value for children which don’t exist), an empty array if the node is a leaf.
getChildrenReturns a Node array, containing real children (max length = 4), an empty array if the node is a leaf.
getNodesOfLevelReturns a Node array, contaning all nodes of the provided level.
getNodesOfTopLevel
Export methods
exportLevelsForScriptDefine levels into bash varaiables
exportForDebugReturns all informations about the quad tree.

Constructors

new

sub new

QTree constructor.  Bless an instance.

Parameters (list)

objForestForest - Forest which this tree belong to
objSrcDataSource - Datasource which determine bottom level nodes
objPyrPyramid - Pyramid linked to this tree
objCommandsCommands - Commands to use to generate pyramid’s images

See also

_init, _load

_init

sub _init

Checks and stores informations.

Parameters (list)

objForestForest - Forest which this tree belong to
objSrcDataSource - Data source which determine bottom level nodes
objPyrPyramid - Pyramid linked to this tree
objCommandsCommands - Commands to use to generate pyramid’s images

_load

sub _load

Determines all nodes from the bottom level to the top level, thanks to the data source.

Nodes determination methods

identifyBottomNodes

sub identifyBottomNodes

Calculate all nodes in bottom level concerned by the datasource (tiles which touch the data source extent or provided in a file).

Parameters (list)

ct<Geo::OSR::CoordinateTransformation> - To convert data extent or images’ bbox.

identifyAboveNodes

sub identifyAboveNodes

Calculate all nodes in above levels.  We generate a above level node if one or more children are generated.

Compute methods

computeYourself

sub computeYourself

Determine codes and weights for each node of the current QTree, and share work on scripts, so as to optimize execution time.

Three steps

  • we add weights (own and accumulated) and commands for each node : computeBranch
  • we determine the cut level, to distribute fairly work : shareNodesOnJobs
  • we write commands in the script associated to the node : <writeBranchCode> and <writeTopCode>

computeBranch

sub computeBranch

Recursive method, which allow to browse tree downward.

2 cases.

Parameters (list)

nodeNode - Node to compute.

computeBottomImage

sub computeBottomImage

Treats a bottom node : determine code or weight.

2 cases

Then the work image is formatted and move to the final place thanks to Commands::work2cache.

Parameters (list)

nodeNode - Bottom level’s node, to treat.

computeAboveImage

sub computeAboveImage

Treats an above node (different to the bottom level) : determine code or weight.

To generate an above node, we use Commands::merge4tiff with children.

Then the work image is formatted and move to the final place thanks to Commands::work2cache.

Parameters (list)

nodeNode - Above level’s node, to treat.

Writer methods

writeCode

sub writeCode

Recursive method, which allow to browse tree (downward) and write commands in associated node’s script.

Parameters (list)

nodeNode - Node whose code is written.

Cut level methods

shareNodesOnJobs

sub shareNodesOnJobs

Determine the cutLevel to optimize sharing into scripts and execution time.

For each level

  • we sort nodes by descending accumulated weight
  • we deal nodes on scripts.  Not a round robin distribution, but we assign node generation to the lighter script.
  • we add the heavier weight and the finisher weight : we obtain the worst weight and we memorized it to finally keep the smaller worst weight.

The cut level could be the bottom level (splits only generate bottom level nodes) or the top level (finisher script do nothing).

To manipulate weights array, we use the tool class Array.

Getters - Setters

getDataSource

sub getDataSource

getPyramid

sub getPyramid

getCutLevelID

sub getCutLevelID

getTopID

sub getTopID

getTopOrder

sub getTopOrder

getBottomOrder

sub getBottomOrder

getScriptFinisher

sub getScriptFinisher

containsNode

sub containsNode

Returns a boolean : TRUE if the node belong to this tree, FALSE otherwise (if a parameter is not defined too).

Parameters (list)

levelstring - Level ID of the node we want to know if it is in the quad tree.
iinteger - Column of the node we want to know if it is in the quad tree.
jinteger - Row of the node we want to know if it is in the quad tree.

updateBBox

sub updateBBox

Compare provided and stored extrems coordinates and update values.

Parameters (list)

xmin, ymin, xmax, ymaxdouble - New coordinates to compare with current bbox.

getPossibleChildren

sub getPossibleChildren

Returns a Node array, containing children (length is always 4, with undefined value for children which don’t exist), an empty array if the node is a leaf.

Warning

Do not mistake with getChildren

Parameters (list)

nodeNode - Node whose we want to know possible children.

getChildren

sub getChildren

Returns a Node array, containing real children (max length = 4), an empty array if the node is a leaf.

Warning

Do not mistake with getPossibleChildren

Parameters (list)

nodeNode - Node whose we want to know children.

getNodesOfLevel

sub getNodesOfLevel

Returns a Node array, contaning all nodes of the provided level.

Parameters (list)

levelstring - Level ID whose we want all nodes.

getNodesOfTopLevel

sub getNodesOfTopLevel

Export methods

exportLevelsForScript

sub exportLevelsForScript

Define levels into bash varaiables

Example

# QTree levels
TOP_LEVEL="0"
CUT_LEVEL="10"
BOTTOM_LEVEL="11"

exportForDebug

sub exportForDebug

Returns all informations about the quad tree.  Useful for debug.

Example

Descibe a node of a QTree or a Graph.
sub new
QTree constructor.
sub _init
Checks and stores informations.
sub _load
Determines all nodes from the bottom level to the top level, thanks to the data source.
sub identifyBottomNodes
Calculate all nodes in bottom level concerned by the datasource (tiles which touch the data source extent or provided in a file).
sub identifyAboveNodes
Calculate all nodes in above levels.
sub computeYourself
Determine codes and weights for each node of the current QTree, and share work on scripts, so as to optimize execution time.
sub computeBranch
Recursive method, which allow to browse tree downward.
sub computeBottomImage
Treats a bottom node : determine code or weight.
sub computeAboveImage
Treats an above node (different to the bottom level) : determine code or weight.
sub writeCode
Recursive method, which allow to browse tree (downward) and write commands in associated node’s script.
sub shareNodesOnJobs
Determine the cutLevel to optimize sharing into scripts and execution time.
sub getDataSource
sub getPyramid
sub getCutLevelID
sub getTopID
sub getTopOrder
sub getBottomOrder
sub getScriptFinisher
sub containsNode
Returns a boolean : TRUE if the node belong to this tree, FALSE otherwise (if a parameter is not defined too).
sub updateBBox
Compare provided and stored extrems coordinates and update values.
sub getPossibleChildren
Returns a Node array, containing children (length is always 4, with undefined value for children which don’t exist), an empty array if the node is a leaf.
sub getChildren
Returns a Node array, containing real children (max length = 4), an empty array if the node is a leaf.
sub getNodesOfLevel
Returns a Node array, contaning all nodes of the provided level.
sub getNodesOfTopLevel
sub exportLevelsForScript
Define levels into bash varaiables
sub exportForDebug
Returns all informations about the quad tree.
Creates and manages all graphs, NNGraph and QTree.
Store all informations about a pyramid.
Configure and assemble commands used to generate pyramid’s images.
Manage a data source, physical (image files) or virtual (WMS server) or both.
sub mergeNtiff
Use the ‘MergeNtiff’ bash function.
sub wms2work
Fetch image corresponding to the node thanks to ‘wget’, in one or more steps at a time.
sub work2cache
Copy image from work directory to cache and transform it (tiled and compressed) thanks to the ‘Work2cache’ bash function (tiff2tile).
sub merge4tiff
Use the ‘Merge4tiff’ bash function.
Provides functions to compute the max value or the min index of an array.
Close