|
Extending Geographic Information System from two-dimensional to three-dimensional approaches
5. Compression Algorithm
Whilst most compression techniques assume that the data must be fully decompressed when it is used, we propose a heuristic technique that allows partial decompression on the compressed dataset. This technique is especially useful for 3D GIS because only tetrahedrons that are located near to the query points will be extracted for next level testing. Compression technique can be classified into two categories of lossless and lossy. A Lossless algorithm prevents any loss of information during the compression/decompression process, whilst lossy algorithm does not guaranty that. Lossless algorithms for tetrahedral compression can be found in Yang et al. (2000) and Gumhold et al. (1999) and similar algorithm is used here. The compression algorithm is using an important property of DTT: any of the tetrahedrons is sharing at least one of its faces with adjacent tetrahedrons; thus, by rearranging the vertices orders it is possible to have a compact storage model, by storing the two faces that are sharing same vertices only. 
Table 1 contains 24 entries (6 tetrahedrons x 4 vertices) and those entries that can be grouped (G), are re-arranged into two subsets {G1: 8, 4, 7, 5, 3, 6, 2} and {G2: 2, 3, 5, 1, 4}. Both subsets are now containing 12 entries in total after compression. Upon decompression, the tetrahedrons (T) can be recreated using a set of four adjacent-vertices. For example, {T1: 8, 4, 7, 5}, {T2: 4, 7, 5, 3}, {T3: 7, 5, 3, 6}, {T4: 5, 3, 6, 2}, {T5: 2, 3, 5, 1}, and {T6: 3, 5, 1, 4}. The arrangement of faces (F) become {F1: 8, 4, 7}, {F2: 8, 4, 5}, {F3: 8, 7, 5}, {F4: 4, 7, 5}, …, {F12: 3, 6, 2}. The similar process is repeated for result that is shown in Table 2. Three subsets have then been defined {G1: 10, 9, 5, 6, 4, 1, 2}, {G2: 9, 6, 4, 7, 2, 3} and {G3: 3, 4, 7, 8, 9}. There are 18 entries in total - half of the 36 entries which are listed in Table 2. As was stated above, the texture data (C) need to be included in the model structure, thus another subset can be defined as following: {C: [default texture value], [face no.], [new texture value], [face no.], …}. To preserve storage space, a default texture value is assigned for every face and this value is used unless a texture value is declared for a particular face. For example above the face F2, can be coloured with colour code “000256”. If we assume that colour code “000000” is the default, we can decode it as {G1: 8, 4, 7, 5, 3, 6, 2} {C: 000000, 2, 000256}. 6. Indexing Method Indexing methods are used to facilitate queries, especially when the dataset is large. K-D-B-tree (Robinson, 1981), R-tree (Guttman, 1984) and grid files (Nievergelt et al., 1984) are among the indexing methods that were first proposed to handle spatial data and they indeed work well with the conventional GIS; nevertheless they are not suitable to be applied for high dimensional features, as they are geared towards 2D data. For geographic data, three or four dimensionality of indexing method should be sufficient. However, by adding more dimensions, we can query spatial and non-spatial attributes using the same index. For example, the query “select all the buildings that are inside specific zone” can be extended to “select all the buildings that are inside specific zone and higher than 10 meters from the ground, and painted light yellow colour, and using bricks as building material”. This query combines the search possibility ranging from geographic positioning to feature similarity such as colour and construction material.  Figure 4: (a) A 2D representation of Space partitioning within Hybrid Tree index node. Partitioning may not always be mutually disjoint as requested in K-D-B-tree (b) Corresponding representation. Internal nodes of KD-trees maintain 2 split positions (left split line and right split line) instead of one to represent overlapping splits Hybrid Tree (Chakrabarti and Mehrotra, 1999) is a multidimensional data structure for indexing high dimensional feature space, and its main advantage is in performing feature based similarity search. The technique works by mapping data items as points in a high dimensional space, which is then indexed using the mechanism of Hybrid Tree. The structure of Hybrid Tree is similar to K-D-B-tree but it allows overlap between index nodes to increase space utilization (Figure 4a), at the same time, the tree operation is similar to R-trees, where indexed subspaces are treated as bounding rectangle (Figure 4b). The Hybrid Tree is designed for feature based similarity search and as it is using point-based structure, it may not be suitable to index spatial data, which is normally consisting of lines and polygons. For example in Figure 4a, if a 2D feature that is represented by rectangle from (1, 1) to (5, 5) is inserted to the index space which has been already partitioned we might end-up with four new vertices (1, 1), (5, 1), (5, 5) and (1, 5) that are distributed into four separate nodes. Due to the separation, it probably will cause problems for some spatial queries such as overlap. However, due to the use of DTT, the point-based index structure of the Hybrid Tree is adequate, because inside DTT, all tetrahedrons are mutually disjoint and therefore it is possible to collapse its representation to a point, as we explain in the following sections. |