Summary

QTree.pm | |

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

Constructors | |

new | QTree constructor. |

_init | Checks and stores informations. |

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

Nodes determination methods | |

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

identifyAboveNodes | Calculate all nodes in above levels. |

Compute methods | |

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

computeBranch | Recursive method, which allow to browse tree downward. |

computeBottomImage | Treats a bottom node : determine code or weight. |

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

Writer methods | |

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

Cut level methods | |

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

Getters - Setters | |

getDataSource | |

getPyramid | |

getCutLevelID | |

getTopID | |

getTopOrder | |

getBottomOrder | |

getScriptFinisher | |

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

updateBBox | Compare provided and stored extrems coordinates and update values. |

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. |

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

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

getNodesOfTopLevel | |

Export methods | |

exportLevelsForScript | Define levels into bash varaiables |

exportForDebug | Returns all informations about the quad tree. |

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

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();

forest | Forest - Forest which this tree belong to. |

pyramid | Pyramid - Pyramid linked to this tree. |

commands | Commands - Command to use to generate images. |

datasource | DataSource - Data source to use to define bottom level nodes and generate them. |

bbox | double array - Datasource bbox, [xmin,ymin,xmax,ymax], in TMS’ SRS |

nodes | Node 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

cutLevelID | string - 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. |

bottomID | string - Bottom level identifiant |

topID | string - Top level identifiant |

Summary

Constructors | |

new | QTree constructor. |

_init | Checks and stores informations. |

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

Nodes determination methods | |

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

identifyAboveNodes | Calculate all nodes in above levels. |

Compute methods | |

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

computeBranch | Recursive method, which allow to browse tree downward. |

computeBottomImage | Treats a bottom node : determine code or weight. |

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

Writer methods | |

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

Cut level methods | |

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

Getters - Setters | |

getDataSource | |

getPyramid | |

getCutLevelID | |

getTopID | |

getTopOrder | |

getBottomOrder | |

getScriptFinisher | |

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

updateBBox | Compare provided and stored extrems coordinates and update values. |

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. |

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

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

getNodesOfTopLevel | |

Export methods | |

exportLevelsForScript | Define levels into bash varaiables |

exportForDebug | Returns all informations about the quad tree. |

sub new

QTree constructor. Bless an instance.

objForest | Forest - Forest which this tree belong to |

objSrc | DataSource - Datasource which determine bottom level nodes |

objPyr | Pyramid - Pyramid linked to this tree |

objCommands | Commands - Commands to use to generate pyramid’s images |

sub _init

Checks and stores informations.

objForest | Forest - Forest which this tree belong to |

objSrc | DataSource - Data source which determine bottom level nodes |

objPyr | Pyramid - Pyramid linked to this tree |

objCommands | Commands - Commands to use to generate pyramid’s images |

sub computeYourself

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

- 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>

sub computeBranch

Recursive method, which allow to browse tree downward.

2 cases.

- the node belong to the bottom level -> computeBottomImage
- the node does not belong to the bottom level -> computeBranch on each child, then computeAboveImage

node | Node - Node to compute. |

sub computeBottomImage

Treats a bottom node : determine code or weight.

- lossless compression and images as data -> Commands::mergeNtiff
- reprojection or lossy compression or just a WMS service as data -> Commands::wms2work

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

node | Node - Bottom level’s node, to treat. |

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.

node | Node - Above level’s node, to treat. |

sub writeCode

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

node | Node - Node whose code is written. |

sub shareNodesOnJobs

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

- 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.

sub containsNode

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

level | string - Level ID of the node we want to know if it is in the quad tree. |

i | integer - Column of the node we want to know if it is in the quad tree. |

j | integer - Row of the node we want to know if it is in the quad tree. |

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.

Do not mistake with getChildren

node | Node - Node whose we want to know possible children. |

sub getChildren

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

Do not mistake with getPossibleChildren

node | Node - Node whose we want to know children. |

sub getNodesOfLevel

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

level | string - Level ID whose we want all nodes. |

BE4

Perl tools and libraries

Descibe a node of a QTree or a Graph.

QTree constructor.

sub new

Checks and stores informations.

sub _init

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

sub _load

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

sub identifyBottomNodes

Calculate all nodes in above levels.

sub identifyAboveNodes

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

sub computeYourself

Recursive method, which allow to browse tree downward.

sub computeBranch

Treats a bottom node : determine code or weight.

sub computeBottomImage

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

sub computeAboveImage

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

sub writeCode

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

sub shareNodesOnJobs

sub getDataSource

sub getPyramid

sub getCutLevelID

sub getTopID

sub getTopOrder

sub getBottomOrder

sub getScriptFinisher

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

sub containsNode

Compare provided and stored extrems coordinates and update values.

sub updateBBox

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 getPossibleChildren

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

sub getChildren

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

sub getNodesOfLevel

sub getNodesOfTopLevel

Define levels into bash varaiables

sub exportLevelsForScript

Returns all informations about the quad tree.

sub exportForDebug

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.

Use the ‘MergeNtiff’ bash function.

sub mergeNtiff

Fetch image corresponding to the node thanks to ‘wget’, in one or more steps at a time.

sub wms2work

Copy image from work directory to cache and transform it (tiled and compressed) thanks to the ‘Work2cache’ bash function (tiff2tile).

sub work2cache

Use the ‘Merge4tiff’ bash function.

sub merge4tiff

Provides functions to compute the max value or the min index of an array.