Алгоритмы и структуры данных геоинформационных систем: Методические указания для студентов специальности 071903 – «Геоинформационные системы»

  • Published on
    27-Dec-2016

  • View
    217

  • Download
    5

Embed Size (px)

Transcript

  • 3

    2003

  • 4

    528.9(07) 21 21 : 071903 / . .. , .. , .. . : , 2003, 34 .

    -

    , 2003

  • 5

    -

    - - 071903 .

    , - . - ().

    . -, - , , - . -, - -.

    - , - , - , MapInfo.

  • 6

    1. 1.1. -

    . - , , .. - . -, . - , . - . - .

    -, - (. 1-). - . , -, . - . . - , (. 1-). - , . Boustrophedon (. , - ). . - .

    . 1. ,

    : ) ; ) Boustrophedon. ( ,

    Canada GIS) - . -

    A A A A

    A B B B

    A A B B

    A A A B

    AAAA ABBB AABB AAAB5A 3B 2A 2B 3A 1B 12

    16

    A A A A

    A B B B

    A A B B

    A A A B

    AAAA BBBA AABB BAAA 4A 3B 3A 3B 3A 8

    16

    ) )

  • 7

    ( ). - . , - .

    2 x 2 . 4 x 4 - 2 x 2, , 2 x 2 (. 2). 2n. , 2 x 2. - . . -, , , 7 8. -, , .

    . 2. .

    ,

    . . 3 -. - , , .

    - . Boustrophedon . - .

    . A(2, 3) . - A -

    2 3

    0 1

    10 11

    8 9

    14 15

    12 13

    2 3

    0 1

    6 7

    4 5

    42 43

    40 41

    46 47

    44 45

    34 35

    32 33

    38 39

    36 37

    58 59

    56 57

    62 63

    60 61

    50 51

    48 49

    54 55

    52 53

    10 11

    8 9

    14 15

    12 13

    2 3

    0 1

    6 7

    4 5

    26 27

    24 25

    29 31

    28 30

    18 19

    16 17

    22 23

    20 21

    AAAAABBBABAABBAA 5A 3B 1A 1B 2A 2B 2A

    A A A A

    A B B B

    A A B B

    A A A B

  • 8

    N , A N, . N=( 1 1 0 1 )2=13 A .

    . 3. .

    . B

    . - : N=10=(1010)2 . A(3, 0).

    1.2.

    . - - - . - . , . - .

    . 4 16 x 16, - 255 A B. -. 8 x 8 0, 1, 2, 3 . , - . , . ,

    15 12

    14 13

    11 10

    8 9

    1 2

    0 3

    6 7

    4 5

    21 22

    20 23

    25 26

    24 27

    19 18

    16 17

    29 28

    30 31

    37 38

    36 39

    41 42

    40 43

    35 34

    32 33

    45 44

    46 47

    15 12

    14 13

    11 10

    8 9

    1 2

    0 3

    7 6

    4 5

    53 52

    54 55

    51 48

    50 49

    57 56

    58 59

    61 62

    60 63

    AAAAABBBBBAAABAA 5A 5B 3A 1B 2A

    A A A A

    A B B B

    A A B B

    A A A B

  • 9

    , .

    . m x m - .

    . 4. .

    - . , . . 4 B 0311. N=0311=(00110101)2. - , .

    , , - . , . , . 4 .

    . 5. .

    : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 : 2 6 A A A A A A 10 A 14 A A A B A A : 0 1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4

  • 10

    , - - . , : - .

    n ( 2n*2n) m . B, , m . - , . , (, , B . 4), n . - .

    1. .

    -

    m n 4 n2 * 1 **

    Boustrophedon m *** m **** m *** m ****

    . * ; **

    ; *** ; **** .

    , ,

    , ( - ). , , - , -. - . : - , -. - . - 1 -, 20.

  • 11

    1.3. -

    . - : , - .

    , , - , . , , 1 (. 6) A. SA = 1*(Count leaf (00,02,03,32)) + 4*(Count leaf (2)) = 8.

    . 6. .

    -

    , . , -, . , , - . , (. 6).

    AB 12

    A A A B

    A A B B

    A B B B

    A A B B

    1 2 2 2

    1 1 2 2

    2 2 2 2

    1 2 2 2

    AB + 12

    1 2

  • 12

    , , . 4 , . tesseral , . , 1000 1 = 0010 , 1 + 0001 = 0100.

    : . -, tesseral 1 10. , 01 03 , 0011 0001 = 10. - 033 211 , 001111 + 10 = 100101. 01 30 , 1100 0001 = 1001.

    2. 01 10. - - ( ). - . , - .

    , , 02 2 . : 024 = 00102 , 24 = 102 . - 01 10. 0010+1=0001, 0010+10=1000, 001010=0000. 00101 , -. , 002=04 102=24. , 2 02 .

    1.4.

    . - , - .

    . , . -. NULL. . - , (. 7).

    -, .

  • 13

    , . - , , , .

    , , , x y, -. ( ). . .

    . 7. .

    -

    R- (R rectangle, ), - . - , - . , - . , , . - (. 8).

    . 8. R.

    2 20 NULL 1113

    2

    4

    5

    6

    7

    8

    9 1011

    12 13

  • 14

    2.

    . -, , - .

    2.1.

    . , (merge dissolve) . - , . - .

    : , AB (4, 2) (2, 0) CD (0, 4) (4, 0) , ? AB CD - (. 9-). y=a+bx , . b=(y2y1) / (x2x1). , -, a=yibxi . y=x2, y=4x. , (3, 1).

    . 9. : ) ; ) . , y=a1+b1x y=a2+b2x,

    x = (a1a2) / (b1b2); y = a1+b1x. - - . , - (. 9-). , (x, y) A, B, C, D :

    (xA x)(x xB) >= 0; (xC x)(x xD) >= 0; (yA y)(y yB) >= 0; (yC y)(y yD) >= 0.

    0 2 4

    4

    2

    0 2 4

    4

    2

    ) )

  • 15

    . b , . , . , - y=const y=a2+b2x. - , b1b2 .

    . n1 n2 . - . , n1 * n2 , . - , , , -. .

    , - . - x y. , . . AB CD , - (xA, xB) (xC, xD) (yA, yB) (yC, yD).

    , ArcInfo, , x y (. 10-). x y. . . , , .. , - . , . O(n1 + n2).

    . 10- . , - . , -. , , , - . . 10-

  • 16

    , - .

    , , , , . . , .

    . 10. ,

    : ) ; ) ; ) .

    2.2. , -

    . . , , , , x, x (. 11-). , (xA,yA) (xB,yB), S=(xB xA)* (yB yA) / 2.

    - . , xi > xi+1, (. 11-). , , - , .

    X . Y .

    X . Y .

    X . Y .

    X . Y .

    X . Y .

    X . Y . X .

    Y .

    max(y)

    max(x)

    min(x) max(x)

    min(x)

    min(y)

    X

    Y

    X

    Y

    x . y .

    x . y .

    X . y .

    x . y .

    x . y .

    x . y .

    x . y .

    x . y .

    ) )

    )

  • 17

    . 11. : ) ; ) .

    , , , -. , . , , . y . y , y=const, const y- .

    x y (-, - - x=6200000; y=16500000), - . - . , , - . .

    - . - . , - . - , .

    , -. A(u, v) P=(xi, yi) i=1..n , . . A (xi, yi) (xi, ) - . -, . (. 12).

    ) )

  • 18

    . 12. . x=u (xi, yi)

    (xi+1, yi+1) . y=a+bx , x=u - (u, a+b*u). . xi=xi+1 xiu, . xi=xi+1 xi=u, 0 2. - , (a+b*u=v). - (. 13).

    . 13. . ,

    . , - . - , , .

    , . -, . . 14,

    2

    3

  • 19

    . -, , .

    . 14. .

    A -

    : x= ((yi yi+1) (xi2 + xi xi+1 + xi+12) / 6A); y= ((xi xi+1) (yi2 + yi yi+1 + yi+12) / 6A). - x y.

    - . , - , . . - (. 15). - , .

    . 15. .

    , . - . - , - .

  • 20

    2.3. , , -

    -, , . -, - - .

    . - A B, A B. . 16 - , , 1 4 .

    . , - , - . , . , - , .

    . , A, A B A B -. , .

    . 16. .

    .

    - , - . ,

    1 (AB) 2 A B 3 A B 4 BA

  • 21

    , . . . , , . .

    , - . . 17 A ( ) 1 ( ). 0. , , - . - , 00, A0, A1, 01. , .

    - , . 8.

    . 17. : ) ; ) ; ) .

    (. 18).

    1 A, B C. - - . , 3, 6 8 1. . , . , 1. , 1. , , - B. - . B1. -, B1.

    a) ))

  • 22

    . 18. .

    1

    . . 1 01. , .

    , . , - . . 19- 19- .

    . 19. : ) ; ) ;

    ) .

    )

    ) )

  • 23

    , , . -, . , , - . , n1 n2 , - (2n1n2/(n1+n2) 3) .

    - , . , - . , - . , (. 20-). , - .

    . 20. : ) ;

    ) .

    , - . - . . - -. 1 2 A B, B1 A2 (. 20-). - , . , .

    ) )

    12

    BA

  • 24

    3. , -

    , , .. , -. - . - -, , .. (digital elevation model - DEM). , .

    , , - . , , , .. -: - , , -, . - .

    - , , . , - . , , - . - - . , - , ( triangulated irregular networks TIN).

    - . , - , .

    , . - -. . , . . , -

  • 25

    , / ( ).

    , , , .. . - DEM , . .

    3.1. ,

    , - . , - , - . DEM - .

    , , - - . , - . . (. 21-). .

    . 21. : ) ; ) ;

    ) ,

    , (. 21-). , , -,

    X1 X2

    150 150

    Y1

    Y2 z1

    z2 z3

    z4

    Z (x, y)

    ) )

    z1

    z2 z3

    z4 Z6

    Z5

    z1

    Z ( x, y)

    )

  • 26

    . Z (x, y) = c0 + c1x + c2y. c0 + c1x + c2y .

    ( ) -

    , (. 21-). , x1 = x2 , y2 = y3, x3 x2 = 1, y2 y1 = 1. - Z5 = Z2 + (Z3 Z2) x Z6 = Z1 + (Z4 Z1) x. Z = Z6 + (Z5 Z6) y.

    DEM - . 3 x 3. - - (. 22-). - . - (. 22-). - S = arctan [(Z/ x)2 + (Z/ y)2]1/2 . - (aspect) A = arctan [ (Z/ y) / (Z/ x)].

    . 22. : ) ;

    ) .

    DEM. Z / x Z4 Z5 , Z / y Z4 Z5 (. 3-). , Z/x = (49 40) / 20 = 0.45; Z/y = (45 48) / 20 = 0.15. S = arctan [(0.45)2 + (0.15)2]1/2 = 25.38. :

    A = arctan [ (0.15) / (0.45) ] = 18.43.

    .

    1

    2

    1

    0

    2

    2

    =

    i

    i

    i

    iii

    iii

    iii

    zy

    zx

    z

    ccc

    yxyy

    xyxx

    yx

    %;100/% = lhS

    )./arctan( lhS =

    h

    l

    ) )

  • 27

    . 23.

    : ) ; ) .

    , . 23-. Z/x Z/y , . - m x n 3 x 3. - , - , (m 2) (n 2).

    . 23-, DEM - z1, z3, z6, z8. - (. 24-).

    . 24.

    3- : ) ; ) . Z/x = [1*(4742) + 2*(4940) + 1*(5244)] / 80 = 0.39; Z/y =

    [1*(4752) + 2*(4548) + 1*(4244)] / 80 = 0.16. - S = arctan [(0.39)2 + (0.16)2]1/2 = 22.9, = arctan [ (0.16) / (0.39) ] = 22.36.

    Z / x Z / y

    ) )

    Z / x Z / y

    ) )X

    Y

  • 28

    , , . - . - . 25-. - - . - , DEM . - -, - 270360, 90180, 090 180270 (. 25-).

    . 25. : ) ; )

    . DEM -

    , (. 26). . ( ) ( ). , , .

    DEM - . - , , - (. 27-).

    ) )

  • 29

    . 26. DEM : ) -

    , , ; ) .

    100 . -

    { 110; 125; 115; 160; }. , 110, 125, 160 , 115 . . 27- - .

    . 27. : ) ;

    ) ( ).

    )

    )

    ) )

  • 30

    3.2. (TIN) (Triangulation Irregular Network

    TIN) DEM , -, . TIN 1970- - .

    TIN DEM. , : , . - , , . , . TIN- - : TIN- - DEM . -, TIN : - , , - .

    - : DEM , , - TIN-. DEM.

    - , , .. - 3 x 3. , , . , , . , , -. , :

    { + + + + } = 2 ; { + + + + } = 4 .

    2 x 2 ,

    . , . , , . -, , , ( ). - , , , . .

  • 31

    VIP ( ) -

    , , - , 3 x 3. ESRI Arc/Info. DEM , (. 28-).

    . 28. VIP: ) ; ) .

    -

    (. 8-). - , , - . - DEM. - , .

    . DEM ( ), - -.

    -. DEM. - . , - . , - , , DEM . - . - , - .

    , TIN, - . , - TIN, - . .

    10 9 8

    6 6 8

    4 5 8

    4

    1

    2

    3 2

    6

    10 1: { 8 6 4 }

    2

    6

    10 3: { 10 6 8 }

    V = 0 V > 0

    ) )

  • 32

    . - . - , . , - . TIN-, .

    . , , . , - . - . , . .

    . 29. : ) ; )

    , ; ) ;

    ) .

    . , - . - . (. 29). , - . - , - . , . - , . - .

    ) ) ) )

  • 33

    TIN: . , , - , (. 30-). (. 30-) , , ( ).

    . 30. TIN: ) ; ) .

    TIN-. . (xa,ya), (xb,yb), (xc,yc). P

    P -

    :

    1

    2

    3 4 5

    6

    7

    8 9

    10

    5

    1

    2

    3

    4

    6 7

    8 9

    ID 10

    (X 10, 1 ; Y 10, 1 ; Z 10, 1 ) (X 10, 2 ; Y 10, 2 ; Z 10, 2 ) (X 10, 3 ; Y 10, 3 ; Z 10, 3 )

    1 1 2 4 3 7

    ID 8

    (X 8 ; Y 8 ; Z 8 )

    6, 7, 9, 4, 5

    )

    )

    .)()()()()()()()()()()()(

    =

    =

    c

    b

    a

    acabacab

    acabacab

    acabacab

    ppp

    xxyyyyxxzzxxxxzzyyzzzzyy

    P

    .;;;;2222222222222ba

    b

    ba

    a

    cba

    c

    cba

    b

    cba

    a

    pppf

    pppe

    ppppi

    pppph

    ppppg

    +=

    +=

    ++=

    ++=

    ++=

  • 34

    (. 31):

    . 31. .

    , . - ( ) P = {pa, pb, pc}, M0(x0, y0, z0), pa ( x x0) + pb ( y y0) + pc ( z z0) = 0. x y .

    - . . : - . - . , .

    DEM . z, . , , - .

    .arccos)arccos(;arccos)arccos(22222

    +==

    ++==

    ba

    b

    cba

    c

    pppf

    ppppi

    Y (0, 1, 0)

    Z (0, 0, 1)

    X (1, 0, 0)

    P (g, h, i)

    A

    C

    B (e, f, 0)

  • 35

    . DEM ( ). () - Z=const. . . , -, (. 32).

    . 32. ()

    (). -

    . DEM - TIN . : - , - (. 33).

    . 33. .

    100

    100 100

    100 100

    300

    50

    50

    50

    100 100

    100

    150 300

    300 300

    130

    300

    100

    100

    170

    ) )

    ,

    ,

  • 36

    1. .., .. -

    : / : , 2001.

    2. .., .. . : - , 1995.

    3. .. - - ( ) // -, 1994. 1, 59-62.

    4. .., .. / . .. . .: - , 1993.

    5. .. : . .: - , 1997.

    6. ., . . . , 1985.

    7. . - : / : - , 2001.

    1. ........................................... 6

    1.1. .............................................................. 6 1.2. ..................................................... 8 1.3. ......................................................... 11 1.4. .............................................................. 12

    2. ................................................. 14 2.1. ............................................................................ 14 2.2. .................................................................... 16 2.3. ............................................................................ 20

    3. ................................................................. 24 3.1. ......................................... 25 3.2. (TIN)................................. 30

    .................................................................................................... 36

    1. 1.1. 1.2. 1.3. 1.4.

    2. 2.1. 2.2. 2.3.

    3. 3.1. 3.2. (TIN)

Recommended

View more >