An objective method of simplification of a broken line when the scale of a map changes

Tadeusz Chrobak, Prof., Ph.D.
St. Staszic Academy of Mining and Metallurgy in Cracow

An introduction

The paper discusses elements of simplification of a broken line. According to Robinson, the elements of simplification take into account data characteristics in order to indicate which of them are to remain on the map during the simplification process. Elimination of undesired details is the method used most frequently. The most difficult problem during the process is the decision which elements should remain and which should be removed. In computer cartography it is possible to substitute continuous spatial data with their chains of discrete points. The process is called digitalisation. In this way lines become chains of points and surfaces turn into sets of chains of points which determine the area of the surface. In computer cartography many rules of line simplification have been developed, nevertheless, most usually they are subjective solutions because the result of a process depends on the values of parameters adopted by the editor. This paper proposes a method of broken line simplification which eliminates the subjective factor.

The method of simplification of an open and closed broken line

This is a method of simplification of open and closed broken lines which depends on the scale of a map and the method of drawing presentation (a monitor of a computer, a paper map). This method retains the hierarchy of line apexes and their topology. The hierarchy of apexes (of the primary line) is determined from its shape on the basis of local extremes determined in closed intervals (created from neighbouring apexes: invariants in the transformation process). The beginning and the end of a line are the first two apexes-invariants which have the highest position in the hierarchy. The following invariants on a line are determined using elementary triangle. The apexes of the beginning and the end of the simplified line form a side of the base of a triangle. The third apex of the triangle is determined by that analysed point which has the biggest height in relation to the base of the triangle out of all points on the line. In a triangle formed thus, when:

'the length of its sides is at least equal to E_j: the shortest length of an elementary triangle',

the analysed point remains on the simplified line. This point is the following (third) apex-invariant in the hierarchy after the beginning and the end of a line. In this way there are two pairs of invariants: the beginning - the third point, and the end - the third point (the order, i.e. the beginning - the third, the end - the third, or the other way round does not influence the final result of the simplified line). Next pairs of apexes-invariants of the simplified line are created in an analogous way. When all apexes of the analysed line have been checked (by comparison with the elementary triangle) with retained sequence and hierarchy of apexes, the stage of choosing of apexes-invariants is finished. The triangle used in the simplification process allows to keep the topology of line apexes because the basis is always determined by two apexes-invariants and the third keeps the by now existing sequence of apexes-invariants of the primary line.

In the simplification process an elementary triangle in which the length of its shortest side determines the relation:

To determine value 's' the following were used:

On the basis of the values determined in items 'a)', 'b)' and 'c', a measure of length ,s' was determined: equal to:

After determination of apexes-invariants, the next stage of simplification is an analysis of apexes-points in intervals made of neighbouring apexes-line invariants. Apexes are analysed in these intervals in order to determine when a chain of points may be substituted with:

- one section, i.e. a chord which connects the beginning and the end of an interval,

- two sections; first, which connects the beginning of the interval with a new: intermediate point (which is not an invariant of the simplified line) and a second section which connects the new point with the end of the interval.

The simplifying method assures a unanimous answer when in an analysed interval a chain of points may be substituted with one or two sections of a line because:

- For a sum of sides (of the analysed interval), when it is smaller than or equal to 2E_n, a chain of points is represented by a chord (after simplification),

- In the second case when in the interval the sum of the lengths of sides of a chain of items is bigger than 2E_n it is possible to create a new point.

Concurrence of the itineration process is a necessary condition to create a new point. In the analysed interval the process is concurrent when in the interval independent variables of all increments of point co-ordinates have a constant sign. If increments of co-ordinates of an independent variable have different signs, the itineration process is divergent. Then, a chain of points on a line in that interval shall be substituted with a chord which connects the points of the beginning and the end of the interval.

The last stage of the proposed method of line simplification is evaluation of process accuracy based on the following facts:

- choice and removal of apexes is determined unanimously,

- the shape of the primary line is least different from the real shape in geographical space; by that, the random variable determined from (primary) geodesic data describes the most probable shape of the line,

- every generalisation (simplification) is described by apexes of the primary line,

- the shortest distances between rejected and remaining apexes on the primary line are determined unanimously; these distances are equal to apparent errors.

Using the law of propagation of errors and one degree of freedom for n removed apexes, the mean error of the process of m_w simplified line is determined. If the accuracy of primary data: m₀ and mean error of a process are known, one may determine m_d: the error of data after the process:

  (2)

In this method the user determines M_n: the denominator of the scale of the created map and one of the values of s_i (i = 1, 2). Other actions: line simplification and evaluation of accuracy of the simplification process are performed automatically.

The result of curve simplification using an objective method versus the scale of source data

In the process of curve simplification based on an objective method, a research was made to determine the number of signals defined by parameters: x, y and recorded in the following way:

  (3)

The relation (3) defines, Ratajski (1989, p.199), reduction of the number of signals (of line apexes) in the process of quantitative cartographic generalisation which in result leads to a decrease of (the number) of events indicated on the map.

The line simplification method was additionally analysed to determine that the shape of the simplified curve shall not change with the accuracy of an elementary triangle for:

1) a process consisting of a few stages:   

2) consisting of one stage with any size of scale range:   

when data from1) and 2) belong to the set:   , where i = 1,2,3...n-1.

This analysis was begun with determining that a change of the scale (except from similar conversions) results in reduction of points. By that, one may not evaluate the shape of a curve after the process on the basis of the number of points. The analysis of the discussed simplification method includes also creation of new points, therefore, cases when a set:

a) has only fixed points,

b) is increased with new points, are analysed

Creation of new points causes that the accuracy of data is retained for the map scale for the M_n set for any point on the curve which:

a) undergoes displacement (P_N) in relation to the primary (P₂), (drawing 1) in result of a change of scale in curve elements after simplification which is defined by the distance d:

d < E_n : elementary length of a triangle of M_n set of the created map.

This inequality is retained because in the shortest side P_N,P₂ or P_1,P₂ or P_2,P₃ is smaller than the shortest side of an elementary triangle which causes that the condition d < E_n is retained. (Lengths of sides: P_1,P_N and P_N,P₃ are bigger than the shortest side of the elementary triangle which was the reason to create the P_N apex in the scale of the created map).

Drawing 1 Displacement of a point in the process of curve simplification when source scales and sets of points which meet the condition: are different

b) is removed (P'_N) in relation to primary (P₂),(drawing 2) in result of scale change in curves after simplification which is determined by y-coordinate (primary generalisation) h:

h < E_n : elementary length of a triangle of M_n set of the scale of the created map.

This inequality is retained because in the shortest side is smaller than the shortest side of an elementary triangle which causes that the condition h < E_n is retained.

Drawing 2. Removal of a point in the process of curve simplification when source scales are different and sets of points meet the condition:

These are all the cases in the process which result from conditions determined in items 1) and 2).

Curves simplified using an objective method for the discussed cases retain accuracy of 2^nd group of details according to Polish branch GUGiK standard, because E_n is always smaller than mean error of line length in the scale of the created map for the M_n set_. The statement that mean error retains accuracy of the 2^nd group of details in the simplification process is justified in the following way:

Length of the shortest side in an elementary triangle - E_n is the threshold measure of drawing recognizability. Processed curves, according to item 1) or 2) using the objective method in the scale of the created map, are 'identical' with the accuracy of the shortest side of an elementary triangle in the scale of the created map.

The theoretical discussion was verified by many practical analyses of curves. Results for one of analysed rivers with 161 points are presented in table 1 (the detailed data is stored in the Faculty of Geodesy and Cartography at AGH Cracow).

The results of analyses presented in table 1 confirm the result of theoretical discussion because in every case the length between the point which is changed and the nearest remaining points was not bigger than the shortest length of a side of an elementary triangle in the scale of the created map similarly to the length of y-coordinate (drawing 2) for removed points. The results indicate considerable practical and economic profits because generalised databases may be generated from detailed databases once and on their basis further generalisations may be made because the result will always be different by the measure of accuracy corresponding to the shortest side of an elementary triangle in the scale of the created map. Thanks to that, the number of data processing as well as disk memory necessary for data storage decreases.

Conclusions

The solution presented in this paper is not only an algorithm for simplification but a method of simplification of a line which does not depend on a decision of an editor of a map but on objective factors of its creation. These factors are:

• Drawing recognizability defined by the shortest side of an elementary triangle,
• The result of line simplification which depends on source data and not on the number of stages of generalisation using the proposed method.

Tab.1

2^x : changed points were situated in different locations of the simplified curve

Bibliography

1. Chrobak T. Badanie przydatności trójkąta elementarnego w komputerowej generalizacji kartograficznej. AGH Uczelniane Wydawnictwa Naukowo-Dydaktyczne, Kraków,
2. Topfera F., Pillewizer W. The principles of selection: a means of cartographic generalization. The Cartographic Journal, 3 (1), 1966 s. 10-16
3. Ratajski L. Metodyka kartografii społeczno - gospodarczej. Warszawa - PPWK 1989
4. Robinson A., Sale R., Morrison J. Podstawy kartografii. Warszawa, PWN 1988
5. Saliszczew K. A. Kartografia ogólna. Warszawa, PWN 1984

Summary

An objective method of simplification of a broken line when the scale of a map changes

This article discusses the method of simplification of a broken line which fulfils the conditions of geometric transformation. In this process, the parameters depend on the scale of the maps under discussion (always smaller than the source scale) and the shortest length of a side of an elementary triangle. This length is a measure of recognizability of a figure. This method ensures that in result of the simplification process the same shape of a broken line with the accuracy of recognizability of the figure is produced.