Calculating the minimum planar graph and generating Voronoi tessellations

Terminology

• Cell: A box or element in a map.
• Active Cell: A type of cell that is currently being evaluated. It refers to the child cell mentioned above.
• Time: An index of the iteration.
• Object: An instance of a certain data type, class, or data structure (i.e., Cell c, c then is an object of type Cell).

Data Structures

• Cell: stores its own position (row and column) and an ID.
• ActiveCell: inherits the properties of a Cell and has its own properties such as distance, originCell, parentCell, resistance, and time (or iterations). This type of cell is used to keep track of which cells are currently being evaluated.
• LinkCell: inherits the properties of a Cell and has its own properties such as cost, distance, fromCell, and originCell. This type of cell is used to create LinkMap.

Schematic representation of Cell type data structures.

• ActiveCellHolder: a type of container that stores a vector of ActiveCells in an order.
• ActiveCellQueue: contains an ActiveCellHolder. Its main purpose is to properly store the ActiveCellHolder in a vector in an order, increasing Euclidean distance.
• InputData: contains all the data that is needed for the engine to operate. The user of the engine has to create an instance of it and initialize all the properties before giving the address of the object to the engine’s constructor.
• Link: stores all the links (directly and indirectly) between the patches. Links are given a negative ID to distinguish them from patch IDs.
• OutputData: similar to InputData but it acts as a container for all the data that are calculated by the engine and gives that data to the user.
• Patch: a patch or a cluster are the habitats that are found in the resistance map, given a value for habitat.

Schematic representation of additional data structures.

Type Definitions

• lcCol: a vector of LinkCells.
• LinkMap: a vector of lcCols, which in turn creates a Map. This type stores the connections between cells.
• flCol: a vector of floating point values.
• flMap: a vector of flCol, which in turn creates a Map that contains floating point values in each element or cell.

Schematic representation of type definitions.

The Engine Class

The main calculator of the program. It creates the minimum planar graph (MPG) using the MPG algorithm, finds least cost links or paths, and finds patches or clusters.

Schematic representation of the Engine Class

How to Use the Engine

1. Create InputData and OutputData objects.
2. Initialize the InputData object’s fields. Keep in mind that the vectors in the InputData and Output data structures are all of type float.
3. Create an array of Char with the length of MAX_CHAR_SIZE or a larger value.
4. Create an Engine object and give the address of the InputData and OutputData objects, the Char array and the size of the array as arguments.
5. Call the initialization function from the Engine object.
6. If the initialization is successful, call the start function from the Engine object. If the initialization is not successful, the array of char will contain the reason for the initialization failure.
7. Once the engine is done calculating, extract all the fields needed in the OutputData object.

A snippet C++ code is shown on the next page as an example.

Note that the current Engine has two lines of code that are meant for interfacing with R. In order to make the Engine run with any programming or scripting language, remove those two lines. One of them is an include statement for Rcpp, at the very top of source code, and the other is inside the start function, the first line inside the while loop. Those two lines are convenient for R users when they want to interrupt or stop the MPG algorithm safely, without crashing their console and possibly losing their data.

vector<float> EngineInterface(vector<float> resistance, vector<float> patches,
                              int nrow, int ncol)
{
    //InputData and OutputData objects
    InputData inObj;
    OutputData outObj; 

    //Initialize InputData object
    inObj.cost_vec = resistance;
    inObj.nrow = nrow;
    inObj.ncol = ncol;
    inObj.patch_vec = patches;

    //Array of chars with a size of MAX_CHAR_SIZE
    char error[MAX_CHAR_SIZE];

    //Engine object while passing in the InputData and OutputData objects'
    // address and the array of chars
    Engine engineObj(&inObj, &outObj, error, MAX_CHAR_SIZE);

    //Initialize the engineObj;
    //If it fails output the reason why and exit the function
    if (engineObj.initialize() == false)
    {
        cout << error << endl;
        return outObj.voronoi_map;
    }

    //start the calculation
    engineObj.start();

    //extract the data needed, in this case the voronoi_map
    return outObj.voronoi_map;
}