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.