## DESCRIPTION

r.xtent computes a raster map layer representing the Voronoi diagram, weighted Voronoi diagram or a more complex territorial partitioning of space around points (centers) in a vector input map (option centers=), based on the XTENT formula.

## BACKGROUND

The algorithm is based on the simple XTENT formula, first published by Renfrew and Level in 1979:

I = C^a - k*d

In the formula above, I is the strength of influence that each centers has on any given location (i.e. raster map cell) in the current region. The basic idea is that each cell will be allocated to the center that scores the highest I for that cell. The magnitude of I at a cell x for each center is determined by two terms that are weighted against each other: center weight (or size) C and distance d. Obviously, a large center in close proximity will have the best chance to score the highest I (i.e. "dominate" a cell). But a very large center can also be dominant, even if it is farther away. The two coefficients a and k determine the balance between center size and distance. The importance of distance increases in a linear manner while the importance of size increases exponentially. Thus, larger centers will compete stronger in relation to smaller ones, even at an increased distance.

The result map (option output=) is of type CELL (integer) raster with each cell representing the unique ID (category value) of the center to whose territory it belongs.

Under certain parameters (specifically: k=1, no -s flag given and straight-line distance used), r.xtent will produce the equivalent of a simple (constant C=1 and a=0.5) or weighted (variable C) Voronoi diagram. Using a distance measurement derived from a cost surface raster will improve result accuracy.

## BASIC USAGE

In the most simple case, using the default values a=0.5 and k=1.0 and keeping C=1.0 (see below), the result will equal that of a voronoi diagram calculated with v.voronoi. But r.xtent offers many options for inclusion of center size (weight), movement cost, barriers, pathways and a priori constraints to provide more detailed, realistic models of territorial allocation processes.

By default, r.xtent behaves differently than the original model published by Renfrew and Level in that it will always produce a complete partitioning of space where each cell is assigned to the territory of exactly one center.
The original definition of the XTENT formula demands that I>=0.0. This can be enforced using the "strict" flag (-s) in which case cells for which no center produces an I>=0.0 will be set to NULL in the result map. This allows modeling incomplete partitionings of space where one ore more cells may not be assigned to the territory of any center. Another way of achieving an incomplete partitioning, which offers a bit more control, is to specify a "reach" attribute for each center (see section on "CONSTRAINTS" below).

The a and k coefficients are set globally, but center weight C must be set individually for each center. This is done by specifying the name of a double type attribute in the input vector points map (option c=). The program will read each center's weight from that attribute. If no attribute name is given, then C will be set to constant "1.0" for every center in the input map. Note: attribute values will be normalized to be in the range [0..1].

### CATEGORIES, LABELS, COLORS AND REPORTS

The basic output map is an integer (CELL) type raster map. Each cell stores the unique number (ID) that represents the most dominant center at that location. By default, the integer type attribute "cat", which should be present in any GRASS vector map will be used to assign category numbers to each center. As an alternative, any attribute in the input points vector map of type integer may be chosen to represent the category number (option categories=) , but the user must make sure that every value is unique!
If no category value is specified and "cat" (the default category attribute for GRASS vector maps) is not present, the new IDs will be generated automaticall starting at "1" and being increased by one for each center in the input map.
Output map analysis may be facilitated if in addition to this a string (text) type attribute is specified to label the output map (i.e. for providing center names; option labels=).

The color of centers' territories in the output map can be controlled by suppling an attribute of type string that is set to the format RRR:GGG:BBB to specify red, green and blue intensity, respectively (option rgb_column=). Intensities can be in the range 0 to 255 for each component. E.g. 125:125:125 is a neutral gray. By default, r.xtent looks for a coloring attribute named "GRASSRGB" in the input map, which is in accordance with the behavior of d.vect.

Category and color attributes have default names ("cat" and "GRASSRGB"), which will be used, if present. If the respective attributes are not found or not of the rigth type, a warning will be issued and defaults used (i.e., a new index starting at "1" and a random color table).

A summary of the model output can be written to an ASCII file using the report= option. To get an output that is better suited for import into a spreadsheet, set the "tabular" flag (-t).

The report will contain at most the following fields for each center (some of the fields will not be shown or set to "n.a.", depending on the model option and results):

• id: the category value of the center
• name: the name of the current center
• dominates: a list of other centers (ids and names) that lie within the territory of the current site
• dominated by: id and name of the center in whose territory the current center lies
• cells: the number of map cells within the current site's territory
• area: current site's territory in square meters (does not work for non-world coordinate systems)
• reach cost/dist: (cost) distance between current center and farthest cell within its territory
• aggressor: number of times that the current center is second in influence to any other center
• competitor: id and name of the most frequent competitor for this center (see later)
• competitor strength avg/var/std: statistics for the competitor's strength within the current center's territory

The "dominates" line is skipped in the tabular report output as it will potentially create very long fields. The "dominates" relationship can be vizualized using a vector map symbology based on the "dominated by" attribute.

### DISTANCE AND MOVEMENT COSTS

One straight-forward step towards more realism is to replace the straight line measure (which is actually a geodetic distance in the case of a lat/long region) used in the distance term k*d with a cost of movement measure that considers the actual, physical effort of moving on the ground from one location (cell) to another. For this purpose, r.xtent uses a cost surface map for each center c in the input vector points map that records the cost of movement from each cell in the map to the cell containing c. For each center, the user must first calculate a cost surface using an appropriate tools such as GRASS' r.cost and r.walk modules. The name of the corresponding raster map must then be added as a text type attribute field in the input map. The costs_att= attribute is used to tell r.xtent which attribute to read the cost map names from.

### BOUNDARIES AND PATHWAYS

Boundaries and pathways are topographic features (usually of line geometry) that block or facilitate movement. Examples for boundaries may be broad rivers, mountain ridges or built walls. Pathways could be natural passes or built roads. Exactly what qualifies as a boundary or pathway depends on the type of movement modeled in the territorial allocation process.

If boundaries and/or pathways are to be added to the cost surfaces then they should be "burned" into a friction surfaces for use with r.walk. The r.burn.frict module should be used for this purpose.

Pathways should be "burned" after boundaries if pathways across boundaries (such as bridges) need to be modeled.

### COMPETITORS

Territorial allocation is not always a clear-cut case. Many different combinations of variables may lead to situations where a center A "wins" highest I only by a relatively small margin over another center B. In this context, we will refer to center B as the "competitor" and to the inverse of the margin between A and B as "competition strength". Thus, whenever there is reason to say that "center B is almost as influential as center A" at a location x, then the strength of competition will be high and B will be classified as the competitor at that location (cell). Strength of competition is normalized to the range 0..1 for the entire region, with "1.0" being the highest strength of competition achievable.

Both the competitor's ID and the competition strength can be mapped (options comp_id= and comp_strength=) and may form the basis for interpretations. It is possible, e.g., to map "conflict" zones between center A and any number of other centers by isolating the cells within the territory of A whose competition exceeds a threshold value (e.g. 0.5) and optionally filtering them by the IDs of one or more possible competitors.

Competitor ID and competitor's strength can only be calculated for models in which at least two territories share at least one boundary.

Alternatively, competition strength can be interpreted as an error measure, with higher competition in locations where the territorial allocation may be erroneous due to flawed input data.

### CONSTRAINTS

Further modeling flexibility may be gained by including a priori information as model constraints. It is possible to define a maximum distance (or costs) for each center, beyond which it cannot exercise and influence, no matter how marginal. Use the reach= option to specify a double type attribute that stores a maximum "reach" for each center. In combination with the -s flag, this provides a simple way to control model behavior. Set it to "-1.0" for centers with unrestricted reach.

It is also possible to define a center A as being dominated (ruled) by another center B, which means that it cannot compete against its "ruler" and any territory dominated by A will be allocated to B. This is done by specifying an integer attribute in the input vector map which should point to the ID of the ruling center or to that of the center itself in case there is no "ruler" (option ruler=).

### CAVEATS AND LIMITATIONS

Attributes in the input vector map that are to be used in the model (e.g. center weight, category attribute, labeling attribute) must be complete. There has to be a value for each center. The program's behavior for missing values is currently undefined.

Keep in mind that the calculation of costs between any cell in the region and a center is done by calculating the globally optimal shortest path from that cell to the center on a cost surface (or straight line). This assumes total spatial information being available, to the entities "on the move", an assumption that may or may not hold in a real-world scenario.

Territories should not get fragmented but form contiguous spatial phenomena. There are extreme cases, however, in which some small degree of fragmentation may occur, e.g. in topographically complex situations.

### COMPUTATIONAL EFFICIENCY

The memory footprint of r.xtent is very low and CPU time will grow linearly with the number of centers. If "ruler" constraints are given, however, processing time will increase exponentially.

## EXAMPLES

The following are examples of territorial models with increasing complexity.

A basic model with center weight approximated by population size and store in the attribute "size" in the input map "towns"

```r.xtent centers=towns output=territories c=size
```

The same model, but this time combined with an elevation map to get a more realistic cost of movement distance measure (attribute table field "map_names" stores the names of the cost surface maps):

```r.xtent centers=towns output=territories c=size costs_att=map_names
```

Here, an additional vector input map of a river representing a natural boundary has been added to a friction map using r.burn.frict and used in the cost surface calculation with r.walk:

Another variation, with a smaller boundary weight (read from an attribute stored in the vector map "river" when performing the r.burn.frict step) to model a river that is easier to cross:

Another basic model, but this time with the additional a priori information that two of the towns are ruled by the third. This relationship is set in the integer attribute "ruler" in the input map "towns". The value of "ruler" is set to the category value of the ruling town (or to that of the town itself):

```r.xtent centers=towns output=territories c=size ruler=ruler --o
```

## BUGS

The program may create temporary maps in the current mapset. If it crashes unexpectedly, it might leave those (prefixed with "XTENT") in the user's mapset. Use g.mremove to delete them.