Basic coordinate transformation

In the process of projection transformation, there are three basic operations: translation, rotation and zooming.

1）Translation

Translation is to move a part or the whole of the graph to another position in the Cartesian coordinate system (Fig. 61-1-a),the transformation formula is as follows:

X’=X+T:sub:`x`

Y’=Y+T:sub:`y`

2）Zoom

Scaling operations can be used to output graphics of different sizes (Fig. 6-11-b), the formula is as follows:

X’=XS:sub:`x`

Y’=YS:sub:`y`

3）Rotation

In map projection transformation, it is often necessary to apply a rotation operation (Fig. 61-1-c), to achieve a rotation operation, a trigonometric function is used, assuming a clockwise rotation angle of θ, the formula is :

X’=Xcosθ+Ysinθ

Y’=-Xsinθ+Ycosθ

Translation

Zoom

Graphic rotation

Figure 6-11: Graphic coordinate transformation

Affine tranformation

If the translation, rotation and scaling of graphics are considered comprehensively, the coordinate transformation formulas are as follows:

The upper formula is an orthogonal transformation, and its more general form is:

The latter is called two-dimensional affine transformation (Affine Transformation), the affine transformation can have different compression and expansion in different directions, which can transform the sphere into an ellipsoid and turn the square into a parallelogram (Figure 6-12). ).

Graph modification

In the process of establishing the topological relationship, some errors in the process of digital input need to be corrected, otherwise, the established topological relationship will not correctly reflect the relationship between objects.

ESRI defines the following six criteria for judging whether the input graph is correct or not, which can help to detect topological errors.

1. All input entities can be represented;

2. No additional entities are entered;

3. All entities are in the right position, and their shapes and sizes are correct;

4. All connected entities are connected;

5. All polygons have and only one marker to identify them.

6. All entities are within boundaries.

The above criteria, especially Articles 5 and 6, are only for ESRI’s ARC/INFO software, and other GIS software may vary depending on the implementation.

Due to the digitization of maps, especially the digitization of hand-held tracking, it is a time-consuming and cumbersome manpower, the mistakes in the digitization process are almost inevitable, the specific reasons for digitization errors include:

1. Missing certain entities;

2. It is difficult to record exactly which entities have been inputted and which entities have not been inputted, because the map information is two-dimensional distributed and the amount of information is generally large.

3. Inaccurate positioning, digitizer resolution can cause positioning error, but the human factor is the main reason for inaccurate position, such as hand shake during hand-held tracking digitization, and the movement of drawings between two entries can make Inaccurate location; more importantly, it is difficult to achieve completely accurate positioning during the digitization of hand-held tracking, for example, in the entry of water system (Fig. 6-14), it is basically impossible to record the end point of the tributary just on the main stream (Figure 6). -14-a), more commonly the two cases shown in Figures (b) and (c).

On digitized maps, the specific manifestations of errors are as follows:

1) Pseudo Node, the pseudo-node makes a complete line into two segments (Figure 15), the reason for the pseudo-node is often that one line has not been entered at one time.

2) Dangling Node, if a node is only connected to a line, then the node is called a suspension node, and the suspension node has a polygon that is not closed (Figure 6-16-a), too late and too (Figure 6-104-b, Figure 6-1-4-c), the nodes do not coincide (Figure 6-16-b) and so on.

polygons are not closed; nodes do not coincide

Figure 6-16: Two cases of suspended nodes

3) Debris polygon or sliver polygon

The strip polygon (Fig. 6-17) is generally caused by repeated entry, because the position of the same line is not exactly the same twice before and after, resulting in a “debris” polygon. In addition, “debris” polygons may also be generated due to data updates with maps of different scales.

4) Irreg Polygon

Irregular polygons (Fig. 6-18) are caused by the inversion of the order or inaccurate position of points on the input line. In the process of topology generation, the “debris” polygon will also be generated.

The above errors are generally found during the process of establishing the topology and need to be edited and modified. Some errors, such as hanging nodes, can be automatically modified by the software at the same time of editing, the usual implementation method is to set a “capture distance”, when the distance between nodes or between nodes and lines is less than this value, it is automatically connection;

Establishing topological relations

After the graphics are modified, it means that the correct topological relationship can be established, the topological relationship can be automatically generated by the computer, at present, most GIS software also provides complete topology functions; however, in some cases, you need to manually modify the topology relationships created by the computer, a typical example is network connectivity.

As described in the definition of the topology, when establishing a topological relationship, only the connections and adjacent relationships between the entities need to be concerned, and the non-topological attributes such as the position of the node and the specific shape of the arc do not affect the establishment process of the topology.

1) Establishment of topological relations of polygons

If DIME or similar encoding models are used, the expression of polygon topological relationships needs to describe the relationships between the following entities:

• Composition arc of polygon;

• Polygons on the left and right sides of the arc segment and nodes at both ends of the arc segment;

• The arc connected by nodes.

In fact, the process of establishing polygon topology is to determine the above relationship. Specific topology building process is related to data structure, but its basic principle is consistent, the following is a brief description of the process of polygon topology building (Figure 6-19).

There are four nodes in Figure 6-19, which are represented by A, B, C and D, six arcs which are represented by numbers, and three polygons of I, II and III (Fig. 6-19-a). First, the following concepts are defined:

• Since the arc segment is directional, the starting node of the arc segment Ais called the head node N:sub:`s`(A), and the terminating node is the tail node * N_E(A)*;

• Considering the directionality of the arc, along the direction of the arc, the adjacent polygons are defined as left and right polygons P:sub:`L`(A)and P: Sub:`R`(A).

Before building the topology, first set the left and right polygons of all the arcs (in the implementation, you can use the coding of the polygon) to be empty; then calculate the angle at the junction of the connected arcs for each node and sort them (Figure 6-19-b) (note that this sort is circular). The algorithm for establishing a topology is as follows:

1. Get the first arc A and set it to the current arc;

2. Determine if P:sub:`L`(A)and P:sub:`R`(A)is empty. If it is not empty, go to the first step, when all the arcs have been processed, the algorithm ends;

3. If the left polygon is empty, create a new polygon P, the first arc of the polygon is the current arc, and set P:sub:`L`(A)= P, set the search start node to N:sub:`s`(A)and search for the current node as N:sub:`E`(A). If the right polygon is empty, create a new polygon P, the first arc of the polygon is the current arc, and set P:sub:`R`(A)=P, set the search start node N:sub:`0`=N:sub:`E`(A), search for the current node N:sub:`C`=N:sub:`S`(A).

4. Judge whether N:sub:`0` and N:sub:`C` are equal, if so, all arcs of the polygon have been found, go to the first step .

5. Check the sequence of arcs that have been aligned with the current node, and use the next arc of the current arc segment A’as the second arc of the polygon.

6. If N:sub:`C`=N:sub:`S`(A’)，set P:sub:`L`(A’)=P，N:sub:`C`=N:sub:`E`(A)；If N:sub:`C`=N:sub:`E`(A’)，set P:sub:`R`(A’)=P，N:sub:`C`=N:sub:`S`(A)，go to step 4.

As shown in Figure 6-19-c, if you search from arc 4 and find node C, the next arc is 2 according to the order of the arc; then find node A, arc 1, and the whole search ends. Polygon I, which has an arc of 4, 2, and 1.

According to this algorithm, the arcs that generate polygons are arranged counterclockwise from the inside of the polygon. If the node arcs are sorted clockwise, the algorithm uses P:sub:`L`(A)instead of P:sub:`R`(A), with * P_R(A)*Instead of P:sub:`L`(A), the generated polygon arcs are arranged clockwise.

To establish the polygon topology, pay attention to the case of the polygon “island”, according to the above algorithm, for a polygon with an “island”, or a ring, the arc segment contains a plurality of closed curves, and the arc of the “island” The segment ordering is clockwise (Figure 6-20) (actually, it is still counterclockwise from the inside of the ring polygon).

Figure 6-20: Results of a topology with polygons with “islands”.

2) Establishment of network topology relations

When inputting information such as roads, water systems, pipe networks, and communication lines, it is necessary to determine the connection relationship between line entities in order to perform traffic and connectivity analysis. The establishment of the network topology relationship includes determining the relationship between the node and the connection line, this work can be done automatically by the computer, but in some cases, such as road traffic applications, some roads intersect on the plane but are not actually connected, as an overpass, which requires manual modification, removes connected nodes (Figure 6-21).