Working through the scales
Attractors: Knitting Hierarchies Together
Download 2.64 Mb.
|
- Navigate this page:
- 3.2.1 Attractor Formation and Naming
- 3.2.2 Attractors as Containers
3.2 Attractors: Knitting Hierarchies TogetherUsing QTMIDs in place of coordinates models point locations as specific, triangular areas, thus providing a basis for handling the uncertainty and scale of point measurements. Partitioning space into triangles, while computationally convenient, yields a somewhat artificial domain for modelling positional uncertainty, which is usually described in terms of circular or elliptical deviations around a point. But as the essence of a hierarchical coordinate system is approximation of location, the shape of elements used to model locations should not be of critical importance, especially if child facets properly nest within their parents without gaps and overlaps. Error approximation might be more precise if hexagonal tessellations were employed (because hexagons are more circular), but hexagonal hierarchies do not nest properly, and in any case it is impossible to tessellate a sphere using only hexagons (but see White et al 1992). As section 3.1.1 shows, QTM’s tessellation is not geometrically uniform (no hierarchical subdivision of a sphere into triangles can be), but this is not a critical weakness. Perhaps its biggest shortcoming — which it shares with all other quadtree data structures — is that spatial relationships between facets are only explicit between children and parents and between siblings. That is, given a leaf node (QTM ID), IDs of parents and grandparents are easily determined (they are initial substring), and the IDs of siblings are obvious (they have different terminal digits), but the identities of other neighboring or nearby facets are less simple to discover. Neighboring facets may in fact have quite different IDs, especially if they lie across a major hierarchical partition. For example, two very close points, one slightly below the 45th parallel, the other slightly above, might have QTM IDs that differ only in the 2nd digit, for example 1133333333 and 1233333333. In a conventional quadtree, it is possible that these data would be stored in memory or disk locations that are quite far apart, depending on how sub-trees are spatially indexed. Using QTM as a hierarchical coordinate system — as we do — complicates this further, as the same QTM ID may occur in a number of features which may need to be handled together. GIS feature data may be well-indexed in secondary storage, but this does not assure that nearby (or even identical) point locations will be stored near one another, regardless of the scheme. A hierarchical approach to relating proximal neighbors was proposed at the time QTM was originally described (Dutton 1989a). It exploits the dual relationship between QTM facets and nodes to associate the facets surrounding each node in the global mesh. These neighborhoods are hexagonal groups of six facets interspersed with triangular ones. These regions (plus the six square neighborhoods around octahedral vertices) completely partition the sphere . At each level of subdivision, these regions densify; new ones sprout in new locations and existing ones generate children that occupy their center point but have half their diameter. We call these nodal regions attractors, as one can think of them as points with large masses that exert gravitational influence on all locations in their well-defined neighborhoods. Figure 3.8 presents an idealized view of four levels of attractors, showing their constituent triangular quadrants. Only a few QTM facets, hence attractors, are as equilateral as this figure shows; most are skewed, such as the ones shown in figure 3.9. Triangular attractors are left unshaded, allowing larger ones below them to be glimpsed. 
Figure 3.8: Four levels of Attractors occupied by a QTM facet; multiple ones exist everywhere except at the central point Attractors may be used to partition map space at a resolution appropriate to the data and map resolution being worked with. For example, a map generalization application may select a set (and size) of attractors that relate to a particular target scale, and use them to identify the features that fall within each one in a systematic fashion. Using this approach, attractors are not stored as part of a database; rather they are dynamic data structures called upon as needed to identify spatial proximities and potential conflicts in specified localities, and can then be dismissed. 3.2.1 Attractor Formation and NamingEach attractor has exactly one “proper” (concentric) child, and covers sectors of six “improper” (eccentric) children that have a second hexagonal parent that touches the first one at a point, plus two other potential parents. For any given eccentric child (which is always hexagonal) any of four lower-level attractors can be considered parents: two hexagonal attractors centered at each endpoint of the segment being split, and either of two triangular attractors that also touch at that midpoint. In a quadtree, each parent has four children, and each child has one parent; Here, each parent has one proper child and six improper ones, and each child may have up to four parents! While this is a kind of inheritance hierarchy, attractor relations are better modeled as a directed acyclic graph (DAG) than as a tree. This complex of relationships is what makes attractors useful for associating point locations: the hexagonal ones unite points in neighboring sub-trees of the QTM hierarchy. The triangular ones do not do this, but serve as keys to identifying their three hexagonal neighbors; as these are the siblings of the triangular attractor, all have the same ID except the least significant digit (lsd), which will be 1, 2 or 3 (IDs of triangular attractors all end in 0). Given a QTM facet belonging to a hexagonal attractor, the attractor’s identifier (called an AID) can be computed as the numerically smallest QTM ID of the six included facets. As an example how such naming can operate, table 3.2 presents AIDs for 11 levels of attractors at two nearby locations in northern Switzerland, starting at QTM level five. Location A Location B LAT,LON: 47.60452, 8.507163 LAT,LON: 47.601349, 8.521080 QTM ID: 1133013100101311223 QTM ID: 1133013100100210130 LVL AID LVL AID 5 113321 5 113321 6 1133323 6 1133323 7 11330131 7 11330131 8 113301310 8 113301310 9 1133013100 9 1133013100 10 11330131121 10 11330131121 11 113301310010 11 113301310010 12 1133013100121 12 1133013100100 13 11330131001313 13 11330131001212 14 113301310010131 14 113301310010131 15 1133013100101311 15 1133013100100210 Table 3.2: Attractor Identifiers for a pair of nearby locations in Switzerland In table 3.2, differences between AIDs are highlighted. Note that the common ancestor in the sequence is 1133, only four digits long (a spatial resolution of more than 600 km). From level 11 (5 km resolution) on, all the attractors share the base 11330131001, which has 11 common leading digits. Observe the abrupt shift in AID at level 10, then back again at level 11. Also observe that at level 14, the same attractor occurs, but appears to descend from two different parents. These two points lie 1.1 km apart, which is within the size of a level 14 attractor (1.22 km major diameter). They happen to be placed near the center of attractor 113301310010131, and their parents were adjacent attractors that had a common vertex at the center of it. The level 14 attractor itself does not, strictly speaking, have a proper parent; it blossomed from a point (the common vertex of two level 13 attractors) at that level of detail. Notice the general similarities between attractor and facet identifiers in this table. This results from using QTMIDs to name attractors. In the case of triangular ones, AIDs are simply quadrant QTM addresses. In the case of hexagonal attractors, the lexically smallest QTM ID of the six facets in each set is selected to identify their attractor. Under this naming convention, AIDs are simply facet IDs, to which zero or five other neighbors are aliased (or only four, in the six special cases of cardinal-point octahedral vertices). 
Figure 3.9: Four levels of vertex attractors for a polygon with 74 points Only a minority of attractors have a proper parent. Because of how they are spawned, one cannot simply remove lsd’s (unless they are repeating digits) from AIDs to ascend their hierarchy. Therefore, it is not as easy to associate attractors from different levels as it is for QTM IDs. That is, larger attractors underneath a given one may share none, some or all of its leading digits (but usually have some of the most significant ones in common, as the above example indicates). The general frequency of occurrence of “orphan” attractors is indicated by the map of attractors shown in figure 3.9. In that figure, the only attractors shown are those that this polygon’s vertices occupy. Most are hexagonal, but several triangular ones also occurred. The number of attractors at each level is a general indication of the potential for reducing line detail when implementing some of the map generalization techniques discussed in chapter 4. 3.2.2 Attractors as ContainersAn application program can choose when, where and which levels of attractors to evaluate as part of its geoprocessing strategy. But when it chooses to do this, what exactly should happen? Having named an attractor occupied by a vertex, this information needs to be put somewhere, at least temporarily. The main purpose of doing this would be to “collect” the vertices that “belong” to a given attractor. As the same or other features are processed and additional vertices fall into an already-identified attractor, this collection will grow — not without limit, but arbitrarily large. The amount of data an attractor may hold grows in direct proportion to data density, and also will tend to be larger for bigger (lower-level) attractors than for smaller ones. There are two design decisions that this raises: 1. What is the minimum set of data items that need to be stored when a vertex is added to an attractor? 2. How can these groups of observations be organized for efficient search, update, data retrieval and deletion? These questions will be addressed in chapter 4. The first one can only be answered by considering the role of attractors in one’s geoprocessing application. In this thesis, the application focus is map generalizaton, and this will color subsequent discussion. As our purpose in using attractors is to identify feature elements that are competing for map space, we need to be able to trace back to these objects from the attractors they occupy. The second question is a spatial indexing problem. It is not obvious what — if any — existing method for allocating storage for simple, ephemeral, numerous dynamic objects such as attractors is the best approach. Linked lists, heaps, hash tables, trees and directories are all potentially useful techniques for this, but novel data structuring approaches may be called for. Section 4.2.3 looks at these issues and evaluates alternative approaches. Directory: papers papers -> From Warfighters to Crimefighters: The Origins of Domestic Police Militarization papers -> The Tragedy of Overfishing and Possible Solutions Stephanie Bellotti papers -> Prospects for Basic Income in Developing Countries: a comparative Analysis of Welfare Regimes in the South papers -> Weather regime transitions and the interannual variability of the North Atlantic Oscillation. Part I: a likely connection papers -> Fast Truncated Multiplication for Cryptographic Applications papers -> Reflections on the Industrial Revolution in Britain: William Blake and J. M. W. Turner papers -> This is the first tpb on this product papers -> Basic aspects of hurricanes for technology faculty in the United States papers -> Title Software based Remote Attestation: measuring integrity of user applications and kernels Authors Download 2.64 Mb. Share with your friends:
|