Fieldtree
In computer science, a fieldtree is a hierarchical data structure that is used to index geometric objects. It groups these objects into rectangular regions called "fields", where the fields at a given level are regularly-spaced, have the same size, and may overlap. Contrary to its name, a fieldtree is not strictly speaking a tree, rather its fields form a directed acyclic graph.
While PR quadtrees and PR octrees are technically fieldtrees, the term usually refers to either partition or cover fieldtrees. A partition fieldtree is a fieldtree where the fields at each level are offset from the fields at the previous level and they do not overlap. On the other hand, a cover fieldtree is a fieldtree where the fields at each level are aligned with the fields at the previous level but they do overlap.
Fieldtrees were originally designed for use in spatial databases, but they also have applications in multikey database indexes, video games, the Internet of Things and simulations.
History
Quadtrees have been used as database indexes since the 1970s. A disadvantage of quadtrees, called "stickiness", is that when a small object lies across the line between two regions it must be stored at a higher level in order to fit entirely within a single region. This results in small objects being stored at unnecessarily high levels and it reduces the effectiveness of the partitioning. Early attempts to solve this involved storing the sicky objects in both regions, either by duplicating them or by using pointers.In 1983, Andrew U. Frank published a thesis describing "the field tree" as a data structure for use in geographic information systems. It solved the stickiness problem by allowing adjacent regions to overlap. In 1990, Frank refined the fieldtree concept by describing both partition and cover fieldtrees.
In the late 1990s, Thatcher Ulrich independently reinvented cover fieldtrees for use in video games. Ulrich noted that, as well as being effective at avoiding stickiness, they were more performant than octrees for handling moving objects.
Description
A fieldtree has multiple "levels", and each level has several regularly-spaced square "fields". Within each level there are no gaps between the fields. The levels are usually listed in order of decreasing field size, with the largest fields at the top level and the smallest fields at the bottom level. Each object is associated with exactly one of the fields that completely contain it. Smaller objects are placed in smaller fields.Fieldtrees are similar to quadtrees in that they start by assigning all objects to a single field. Then, when a field reaches its capacity, it is split into four smaller fields. These smaller fields form part of the next level of the data structure. This splitting process repeats until either all fields are below capacity or the fieldtree has reached a predefined maximum number of levels.
The main difference between fieldtrees and quadtrees is how the fields at each level are arranged. Depending on the type of fieldtree, the fields in each level may overlap or they may be offset from the fields in the previous level. In either case, a field in one level may intersect multiple fields in the levels below and above it.
One way of thinking about a fieldtree is as a directed acyclic graph, where each edge connects a field in one level with a field that intersects it in the next level. This graph does not have any cycles because the edges always point from fields in higher levels to fields in lower levels. Contrary to what the name "fieldtree" might suggest, the data structure is not a true tree because a field may have multiple parents and multiple children. However, it is useful to systematically select a subset of the edges to form a tree to allow for various optimizations.
Partition fieldtree
A partition fieldtree is a type of fieldtree where each layer is slightly offset from the last, so that every corner of a field in one level lines up with the center of a field in the next level. This requires a shift in both the x and y directions of half of the smaller field's width, relative to where the fields would be in a quadtree. The fields in each level do not overlap.This small shift ensures that an object never needs to be stored more than two levels up from the smallest level that could contain it, improving the efficiency of operations on the fieldtree.
A partition fieldtree is so called because, unlike a cover fieldtree, the fields at each level partition the space without overlapping.
Cover fieldtree
A cover fieldtree is a type of fieldtree where the fields in each level are expanded so that they overlap. The centers of the fields remain in the same place as they would be in a quadtree.The amount that the fields overlap is described by the expansion factor, which must be a positive real number. The width of each field can be found using . A typical value for is 1, which results in the fields being twice as wide as they would be in a quadtree. The overlap between adjacent fields ensures that any object of width can be stored in a given level. In the case of, an object never needs to be stored more than one level up from the smallest level that could contain it, improving the efficiency of operations on the fieldtree.
A cover fieldtree is so called because the fields at each level cover the space but, unlike with a partition fieldtree, there is some overlap.