GISdevelopment.net ---> Technology ---> Geographic Information System

Development of Mapping System by Application of Symbol-Placement Methods

Masanori WATAGAWAab, Yoichi URAMOTOa & Hiroyuki SHIMADAb
a PASCO Corporation, 1-1-2, Higashiyama, Meguro-ku, Tokyo 153-0043, JAPAN
b Graduate School of Maritime Sciences, Kobe University, 5-1-1 Fukae,
Higashi-nada-ku, Kobe city
E-mail:(masanori_watagawa)@pasco.co.jp

Abstract
Map symbol in digital map is one of the important map elements, and the map expression follows the representation rules in each country. In this study, we evaluated the most suitable methodology to generate map symbol on accurate position for digital mapping. Our methodology generated the map symbols by three steps. Step 1: Algorithm for analyzing geometry (geographical objects) on the map and dividing pattern. Step 2: Algorithm for generating assistance line for drawing the symbols to geographical objects on the map from the algorithm as pattern analysis. Step 3: Algorithm for generating symbol on accurate position in the map to classified geographical features shape with assistance line. Our methodology corresponded to various geographical features in digital map. We developed Mapping system using Symbol-Placement Methodology. We verified this system and methodology by examining the generation rate of the symbol. The results obtained show that despite their simplicity, these methods give relatively accurate results and are sufficient for developing of the mapping system. Our research suggests that Symbol-placement methodology might be more efficient in digital mapping than manual digitization by human. However, this research needed introduction of more different types of data into algorithms for the future works. We are going to investigate analysis of various geographical features for the digital mapping.

1.0 Introduction
Map symbol in digital map is one of the important map elements, and the map expression follows the representation rules in each country. Geographic information related to the topographic map is measured by digital format, and there is digital mapping technology that constructs the numeric topographical map systematically arranged depending on the computer technology. In topographic map production, specifications for symbols are published by governmental organization. The map symbol for the digital mapping is provided to show geographical objects for users. However geographical features in the topographical map are complex including many elements. When creating maps, we often come across difficulty in placing map elements. The map input operators create the symbols by interpreting aerial photographs, and in the process, they have to confirm complex geographical objects one by one. Specifically, the operator has to specify the selection of the figure, the generation part on the map, and the beginning point and the terminal of the symbol generation. As a result, the map production cost increases because the input work is excessively time-consuming. It is also noticeable that the operator inputs the symbol by the subjectivity. Those problems have been discussed and for past several years.1-3 An example of such studies can be label placement methods on a given map.

In this paper, we have evaluated the most suitable methodology to generate the symbol on accurate position for digital mapping.
2.0 Symbol-placement methodology

Our methodology generated the map symbols by three steps.

Step 1: Algorithm for analyzing geometry (geographical objects) on the map and dividing pattern.

Step 2: Algorithm for generating assistance line for drawing the symbols to geographical objects on the map from the algorithm as pattern analysis.

Step 3: Algorithm for generating symbols on accurate position in the classified geographical features with assistance line. Algorithms are described in the following subsections.

2.1 The geographic objects of target
Topographical map consists of a number of geographic objects with symbols. Our study targets hachure (slope and encircling shape) of the topographical map; being surveyed at 1:500 and 1:1,000 scales. The hachure are composite objects consisted of upper line, lower line and inside line as shown in Table 1. Upper line and lower line are polylines which include origin of line, end of the line and midpoint. Inside line is not provided on a given map. Our methods aim to generate the hachure (inside line).


Table 1: Symbol of Hachure


2.2 Algorithm for analyzing geometry
We propose algorithm for analyzing geometry that can classify geographic objects into five patterns as follows:

Pattern 1: Feature where connection point of the edge is composed of two points. This type is standard composite objects.

Pattern 2: Feature where starting points of the line group connects to the terminal points. This type consists of closed path.

Pattern 3: Feature where connection point of even number point in four points or more. This type is the divergent geological feature.

Pattern 4:Feature where connection point is composed of odd number point in one or more. This type shows that the part of composite objects is not connected to the point.

Pattern5: Feature where edge point doesn't connect with other figure. This type is an error line because there is not another line for composite objects.

2.3 Algorithm for generating assistance line
We propose algorithm for generating assistance line that can support to draw the hachure (inside line) to geographical objects on the targets figure. This algorithm works as follows:

Process 1: Generate a vertex from the origin of line to terminal on the target shape.

Process 2: Generate a triangle consists of the segment from the origin of upper line to nth vertex of lower line.

Process 3: Generate an assistance line from the origin point on the triangle to terminal.

Figure 1-3 shows the example of generation process of the divergent geological feature (Pattern 3).

Figure 1: Vertex on the target



Figure 2: Triangle consists of segments



Figure 3: Assistance line



Figure 4: Sense of the hachure with assistance line


2.4 Algorithm for generating symbol

Algorithm for generating symbols is final process for Symbol-placement methods. This algorithm works as follows:
  1. Get the midpoint of an upper line.
  2. Drop a vertical line from the midpoint of the upper line to the assistance center line.
  3. Get the point at the intersection of the lower line and the vertical line.
  4. Generate the hachure (long line).
  5. Measure the distance of hachure that has been generated.
  6. Get the point with the distance of hachure from the origin of hachure on the upper line.
  7. Drop a vertical line from the given point to the assistance center line.
  8. Get the point at the intersection of the lower line and the vertical line.
  9. Calculate the sense of the hachure (inside line) previously generated.
  10. Calculate the sense of the hachure (inside line) secondly generated.
  11. Calculate the sense of the line to bisect hachure described 9 and 10.
  12. Calculate the sense of bisector of hachure.
  13. Calculate the midpoint at the intersection of the upper line, the lower line and the bisector.
  14. Generate the hachure (short line) from the intersection of the upper line to the midpoint of the bisector.
  15. Generate the hachure (short line) from the intersection of the upper line to the midpoint of the bisector.

Figure 4 shows the sense of the hachure (inside line) using assistance line. Figure 5 shows the example of the geographical feature after generating hachure. This is final output of our methodology.

Figure 5: Example of the geographical shape after generating Hachure


3.0 Verification of the methodology
We developed prototype by application of symbol-placement methods and verified this prototype methodology by sampling inspection plan. We extracted the target feature by examining the map.

3.1 Experimental maps
Five topographical maps are surveyed at 1:500. Experimental maps include the targets consists of upper line and lower line without inside line.

3.2 Equipment
The customized CAD software and program were developed by PASCO Corporation. This prototype program is based on symbol-placement methods.

3.3 Procedure
We count the number of pattern of each feature and generation rate of the symbol on experimental map via symbol-placement methods.

3.4 Result
All of the results are summarized in Table 2. From this result, simulated algorithm analyzed pattern 1-5 and other patterns. We found that almost target feature consisted of pattern 1 as standard type. Map Number 4 contained a lot of error segments (Pattern 5) and success rate was 33%. Another map also contained pattern 5 as error segments but we found success of generating hachure on each feature. We found 77 % average success rate of experimental map. We achieved other error pattern. For example, the upper line crossed the lower line and those lines did not make pair for generating hachure.


Table 2: Pattern and Success rate of Experimental maps


4.0 Conclusion
The results obtained show that despite their simplicity, these methods give relatively accurate results and are sufficient for developing of the mapping system. Our research suggests that symbol-placement methodology might be more efficient in digital mapping than manual digitization. However, results proved that maps were containing more error pattern than our expectations. This research needs the introduction more different types of data into algorithms for the feature works. We are going to investigate the analysis of various geographical features in digital mapping utilizing this methodology.

5.0 References
[1] BARTONEK, D. (2003).A Genetic Algorithm for Automatic Map Symbols Placement. Electronic Journal of Polish Agricultural Universities. Geodesy and Cartography, Volume 6, Issue 1.

[2] T. Sano (2004).Algorithm for A Character String Automatic Placing in A Mapping System for Electric Power Distribution System(in Japanese), IEEJ Transactions on Industry Applications , Volume 124-D Number 5, pp.431-441.

[3] Van Dijk S. Van Kreveld M. Strijk T. Wolff A. (2002). Towards an evaluation of quality for names placement methods. International Journal of Geographical Information Science, Volume 16, Number 7, 1 November 2002 , pp. 641-661(21).

[4] Geographical Survey Institute. Technical Report of GSI. A1-No.291 (in Japanese). http://psgsv.gsi.go.jp/koukyou/download/dmkaitei/index.htm (accessed on 20 May 2007)

[5] Geographical Survey Institute. Technical Report of GSI.A1-No.264. http://www.gsi.go.jp/ENGLISH/RESEARCH/GIS/jsgi-manual.pdf (accessed on 12 May 2008)

© GISdevelopment.net. All rights reserved.