ISPRS, Vol.34, Part 2W2, “Dynamic and Multi-Dimensional GIS", Bangkok, May 23-25, 2001
3.3 Topological information on map: Voronoi neitfibours
As has been discussed in the previous section, the construction
of dual graph for map features is a difficult task because the vast
majority of map features are disjoint. However, with the Vonoroi
region, all features have been connected together to form a
tessellation. The generation of dual graph for map features could
be replaced by the dual graph of the Voronoi region of these
features. This is illustrated in Figure 5. Figure 5(a) is the
Voronoi region and Figure 5(b) is the corresponding dual graph.
Figure 5 A Voronoi diagram and its dual graph
Then, the entropy of this map can also be computed as did for
the graphs in Figure 2.
It has also been discussed before the entropy computed using
the number of nodes in the graph is that of the distribution of
different kind of vertices. It does not really reflect the complexity
of dual graph directly. Indeed, sometimes, it is misleading, as
shown in the case of Figure 2. Therefore, a new index needs to
be designed. As the complexity of a dual graph can be indicated
by the number of neighbours for each vertex, therefore, this
number is a good measure already. In order to compare the
complexity of dual graph with different vertices, the average
number of neighbours for each vertex may be used as a value to
indicate the complexity of a dual graph.
M,
n Nj
In
V
K N U
(13)
Suppose there are in total N symbols on a map, the total amount
of thematic information for this map is then
H(TM) = jr H, (TM) (14)
;=l
4. A COMPARATIVE ANALYSIS THROUGH EXPERIMENTS
In the previous section, a set of new measures has been
proposed for the spatial information of a map. It is appropriate to
conduct some experimental tests on the usefulness of these new
measures and also to see whether these new measures are
more meaningful than existing ones.
4.1 Metric information vs statistical information
The first test is on metric information. The two maps in Figure 1
were used. The corresponding Voronoi regions are shown in
Figure 3. The results for the entropy of Voronoi regions and the
ratio between mean and standard are listed in Table 1.
Table 1 Metric information of the two maps in Figure 1
(The area of the map is a unit)
H(M)
Rm
S E
o
Map in Figure 1 (a)
4.2848
80.51%
0.025
2.84%
Map in Figure 1 (b)
5.1260
96.32%
0.025
1.51%
From Table 1, it is clear that the map shown in Figure 1(b)
contains higher metric information than that in Figure 1(a).
Considering the fact that they should have the same amount of
statistical information as pointed out in Section 2, it seems logic
to claim that these measures is more appropriate than the
statistical information.
Let, N s be the sum of the numbers of neighbours for all vertices
and N T the total number of vertices in a dual graph. Then, the
average number of neighbour for each vertex is:
3.4 Thematic information on map: Entropy of neighbour
types
Thematic information related to the thematic types of features. It
is understandable that, if a symbol has all neighbours with the
same thematic hype, then the importance of this symbol is very
low, in terms of thematic meaning. In the other hand, if a symbol
has neighbours with different thematic types, it should be
regarded as having higher thematic information. [Here, the
neighbours are also defined by the immediately-neighbouring
Voronoi regions]-. Based on this assumption, the thematic
information of a map symbol can then be defined. Suppose, for
the i ,h map symbol, there are in total Ni neighbours and Mi types
of thematic neighbours. There are in total nj neighbours for j ,h
thematic type. Then the probability of the neighbours with f
thematic type is as follows:
p j=Y' = (12)
The thematic information of the ith map symbol is then as
follows:
4.2 Topological information: new vs old
The second test is on the topological information. Using the new
index, the results for the two graphs in Figure 2 would be
different. In Figure 2(a), there are seven vertices and the total
number of neighbours for all vertices are twelve. The average
number of neighbours for each vertex is 1.7. In Figure 2(b),
there are seven vertices as well but the total number of
neighbours for all vertices are fourteen. The average number of
neighbour for each vertex is 2.0. It is then clear that Figure 2 (b)
is more complex than Figure 2 (a).
Table 2 The average number of neighbours for Figs. 3 and 5
N T
N s
H T
Figure 3(a)
40
206
5.15
Figure 3(b)
40
188
4.70
Figure 5
13
54
4.15
To further elaborate the adequacy of this new measure, the index
value for the Voronoi regions shown in Figure 3 and 5 are also
computed and listed in Table 2. It shows that the map shown in
Figure 1(a) is more complex than that shown in Figure 1(b). This
is because the three symbols are mixed into the building
symbols.
