Địa lý - Chương 3: Mô hình và cấu trúc dữ liệu không gian

Chương 3 MÔ HÌNH VÀ CẤU TRÚC DỮ LIỆU KHÔNG GIAN Biên soạn: GV. Phạm Thế Hùng 3.1. GIỚI THIỆU Thực thể không gian (spatial entity) là sự vật, hiện tượng tồn tại trong thế giới thực. Đối tượng không gian (spatial object) là những thực thể không gian được biểu diễn trong máy tính. Thế giới thực Dữ liệu GIS -Truy vấn thơng tin -Cập nhật dữ liệu -Phân tích, mơ hình hĩa -Hiển thị, xuất dữ liệu Biên soạn: GV. Phạm Thế Hùng 3.1. GIỚI THIỆU Vai trò của mô hình dữ liệu trong GIS Biên soạn: GV. Phạm Thế Hùng 3.1. GIỚI THIỆU Mô hình không gian là sự đơn giản hoá thế giới thực, là tập những phần tử biểu diễn các thực thể không gian trong thế giới thực. Mô hình dữ liệu không gian tương ứng với tập các nguyên tắc để chuyển thế giới thực thành các đối tượng không gian được miêu tả một cách logic. Biên soạn: GV. Phạm Thế Hùng 3.1. GIỚI THIỆU Dữ liệu số về các đối tượng không gian được biểu diễn trong máy tính dưới dạng nhị phân theo mô hình raster hoặc vector. - Mô hình raster biểu diễn các thực thể theo một bề mặt liên tục - Mô hình vector biểu diễn các thực thể theo một bề mặt rời rạc Biên soạn: GV. Phạm Thế Hùng 3.1. GIỚI THIỆU Mô hình raster: các đối tượng không gian được chia thành những ô lưới bằng nhau gọi là điểm ảnh (pixel), mỗi điểm ảnh chỉ có một thuộc tính. Mô hình vector: các đối tượng không gian được biểu diễn như những điểm, đường, vùng. Biên soạn: GV. Phạm Thế Hùng 3.2. MÔ HÌNH DỮ LIỆU RASTER Mô hình dữ liệu Raster sử dụng một mạng lưới các ô (hình vuông, tam giác hoặc lục giác) được gọi là các pixel để thể hiện các đối tượng không gian. The raster data model uses an array of cells, or pixels, to represent real-world objects. The cells can hold any attribute values based on one of several encoding schemes including categories, and integer and floating- point numbers. Biên soạn: GV. Phạm Thế Hùng 3.2. MÔ HÌNH DỮ LIỆU RASTER Dữ liệu Raster khu vực bán đảo Olympic, bang Washington, Mỹ. Biên soạn: GV. Phạm Thế Hùng 3.3. CẤU TRÚC DỮ LIỆU RASTER Cấu trúc dữ liệu raster có hai đặc điểm cần lưu ý: - Mỗi điểm ảnh chỉ biểu diễn một thuộc tính, xác định bởi giá trị f(x,y). - Khi thay đổi độ phân giải (kích thước điểm ảnh thay đổi), dung lượng dữ liệu thay đổi theo. Dung lượng dữ liệu tăng theo bình phương tỉ lệ gia tăng độ phân giải. 3.3.1. Mô tả cấu trúc Biên soạn: GV. Phạm Thế Hùng 3.3. CẤU TRÚC DỮ LIỆU RASTER Đối tượng điểm (Point objects): 3.3.2. Đặc tính hình học Số pixel i Số hàng j (i,j) = (5,3);(7,5);(8,2) Biên soạn: GV. Phạm Thế Hùng 3.3. CẤU TRÚC DỮ LIỆU RASTER Đối tượng đường (Line objects): 3.3.2. Đặc tính hình học (1,3);(2,2);(3,2) ;(4,3); (5,4) ;(6,5) ;(7,5) ;(8,4) Biên soạn: GV. Phạm Thế Hùng 3.3. CẤU TRÚC DỮ LIỆU RASTER Đối tượng vùng (Polygon objects): 3.3.2. Đặc tính hình học Biên soạn: GV. Phạm Thế Hùng 3.3. CẤU TRÚC DỮ LIỆU RASTER Để tăng hiệu quả trong việc lưu trữ dữ liệu Raster, nhiều kỹ thuật nén dữ liệu Raster đã được nghiên cứu và đề xuất: - Mã hóa đoạn chạy (run-length encoding) - Mã hóa khối (block encoding) - Mã hóa sóng (wavelet encoding) - Mã hóa cây tứ phân (quadtrees encoding) 3.3.3. Kỹ thuật nén dữ liệu Raster Biên soạn: GV. Phạm Thế Hùng 3.3. CẤU TRÚC DỮ LIỆU RASTER Cấu trúc dữ liệu raster được thực hiện dưới nhiều định dạng số khác nhau: - GRID: Định dạng của ESRI dùng để lưu trữ và xử lý dữ liệu raster. - Định dạng công nghiệp chuẩn: JPEG, TIFF và MrSID dùng trong hiển thị nhưng không phân tích được (phải chuyển thành GRID). 3.3.4. Định dạng file đối với dữ liệu không gian raster Biên soạn: GV. Phạm Thế Hùng 3.3. CẤU TRÚC DỮ LIỆU RASTER Khi hiển thị đồng thời với dữ liệu vector, đòi hỏi phải có thông tin tọa độ tham chiếu (georeferencing information) - TIFF image.tiff image.tfw - Bitmap image.bmp image.bpw - BIL image.bil image.blw - JPEG image.jpg image.jpw Geotiff là định dạng chứa cả ảnh và thông tin tham chiếu trong cùng 1 file. 3.3.4. Định dạng file đối với dữ liệu không gian raster Biên soạn: GV. Phạm Thế Hùng 3.3. CẤU TRÚC DỮ LIỆU RASTER Cấu trúc của tập tin tham chiếu: dạng ASCII gồm 6 dòng  Dòng 1: Kích thước theo hướng x của pixel đơn vị bản đồ (A)  Dòng 2: Góc xoay quanh trục y (D)  Dòng 3: Góc xoay quanh trục x (B)  Dòng 4: Kích thước âm theo hướng y của pixel theo đơn vị bản đồ (E)  Dòng 5: Tọa độ x của tâm pixel trên trái (C)  Dòng 6: Tọa độ y của tâm pixel trên trái (F) - Công thức tính chuyển: X 1 = Ax + By + C Y 1 = Dx + Ey + F 3.3.4. Định dạng file đối với dữ liệu không gian raster x 1 , y 1 : tọa độ pixel theo đơn vị bản đồ x, y: cột và hàng của pixel trên ảnh Biên soạn: GV. Phạm Thế Hùng 3.3. CẤU TRÚC DỮ LIỆU RASTER Ví dụ:  20.17541308822119 A 0.00000000000 D 0.00000000000 B  -20.17541308822119 E 424178.11472601280548 C 4313415.90726399607956 F - Với pixel trên ảnh có tọa độ (3,4) thì  Pixel có tọa độ bản đồ là: (424238.640965277, 431335.20561164) 3.3.4. Định dạng file đối với dữ liệu không gian raster Biên soạn: GV. Phạm Thế Hùng 3.4. MÔ HÌNH DỮ LIỆU VECTOR Mô hình dữ liệu vector sử dụng các đối tượng điểm, đường, vùng để biểu diễn các thực thể không gian. In the vector data model each object in the real world is first classified into a geometric type: in the 2-D case point, line, or polygon. Points (e.g., wells, soil pits, and retail stores) are recoded as single coordinate pairs, lines (e.g., roads, streams, and geologic faults) as a series of ordered coordinate pairs (also called polylines), and polygons (census tracts, soil areas, and oil license zones) as one or more line segments that close to form a polygon area. Biên soạn: GV. Phạm Thế Hùng 3.5. CẤU TRÚC DỮ LIỆU VECTOR Các đối tượng không gian khi biểu diễn ở cấu trúc vector thường tổ chức dưới dạng điểm, đường và vùng trên một hệ thống tọa độ xác định. Mỗi điểm được xác định bởi một cặp toạ độ (x,y); đường được xác định bởi một chuỗi liên tiếp các điểm {(x1, y1),(x2, y2),...,(xn,yn)} và vùng được xác định bởi những đường khép kín. Hai cấu trúc dữ liệu Vector thông dụng là cấu trúc Spaghetti và cấu trúc Topology. 3.5.1. Mô tả cấu trúc Biên soạn: GV. Phạm Thế Hùng 3.5. CẤU TRÚC DỮ LIỆU VECTOR Các đối tượng trong không gian được phân loại thành 3 dạng: - Đối tượng điểm: Điểm dùng cho tất cả các đối tượng không gian được biểu diễn như một cặp tọa độ (x,y). - Đối tượng đường: Đường được dùng để biểu diễn tất cả các đối tượng có dạng tuyến, được tạo nên từ hai hoặc nhiều cặp tọa độ (x,y). - Đối tượng vùng: Vùng là một đối tượng hình học hai chiều 3.5.2. Đặc tính hình học Biên soạn: GV. Phạm Thế Hùng 3.5. CẤU TRÚC DỮ LIỆU VECTOR 3.5.2. Đặc tính hình học Điểm Đường Đường cong Vùng Biên soạn: GV. Phạm Thế Hùng 3.5. CẤU TRÚC DỮ LIỆU VECTOR - Điểm được xác định bằng một cặp tọa độ (x,y), - Đường được biểu diễn bằng một chuỗi những cặp toạ độ (xi,yi). - Vùng được xác định bởi một cung khép kín và được biểu diễn bằng một chuỗi cặp tọa độ (xi,yi) có tọa độ đầu và tọa độ cuối trùng nhau. 3.5.3. Cấu trúc Spaghetti Biên soạn: GV. Phạm Thế Hùng 3.5. CẤU TRÚC DỮ LIỆU VECTOR 3.5.3. Cấu trúc Spaghetti Đặc trưng Vị trí Điểm A (x A ,y A ) Cung AB (x A ,y A ), (x 1 ,y 1 ), . . . , (x B ,y B ). Vùng 1 (x 1A ,y 1A ), (x 11 ,y 11 ), . . . , (x 1i ,y 1i ), (x 1B ,y 1B ), (x 1j ,y 1j ), . . . , (x 1A ,y 1A ). Vùng 2 (x 2A ,y 2A ), (x 21 ,y 21 ), . . . , (x 2i ,y 2i ), (x 2B ,y 2B ), (x 2j ,y 2j ), . . . , (x 2A ,y 2A ). 1 2 A(x A ,y A ) B(x A ,y A ) Biên soạn: GV. Phạm Thế Hùng 3.5. CẤU TRÚC DỮ LIỆU VECTOR 3.5.3. Cấu trúc Spaghetti Cấu trúc không ghi nhận đặc trưng kề nhau của hai vùng kề nhau, nghĩa là tại đường chung của hai vùng kề nhau có hai đường độc lập. Cấu trúc Spaghetti được sử dụng để lập bản đồ số rất tốt, nhưng không thích hợp cho các bài toán phân tích GIS vì không mô tả được các quan hệ không gian. Biên soạn: GV. Phạm Thế Hùng 3.5. CẤU TRÚC DỮ LIỆU VECTOR 3.5.4. Cấu trúc Topology Tính topology rất cần thiết trong quá trình phân tích không gian. Topology thể hiện mối quan hệ hoặc sự liên kết giữa các đối tượng trong không gian. Topology là một phương pháp toán học dùng để xác định các quan hệ không gian. Biên soạn: GV. Phạm Thế Hùng 3.5. CẤU TRÚC DỮ LIỆU VECTOR 3.5.4. Cấu trúc Topology Cấu trúc topology còn được gọi là cấu trúc cung- nút (arc-node) với phần tử cơ bản là cung. Mỗi cung được mô tả như là một chuỗi những đoạn thẳng nối liền nhau, điểm đầu và cuối cung gọi là nút (node), những điểm giữa cung gọi là đỉnh (vertex). Nút là điểm giao nhau của hai hay nhiều cung, đối với những cung độc lập, nút là điểm cuối cùng của cung, không nối liền với bất kỳ cung nào khác. Biên soạn: GV. Phạm Thế Hùng 3.5. CẤU TRÚC DỮ LIỆU VECTOR 3.5.4. Cấu trúc Topology Vùng là một chuỗi những cung nối liền nhau và khép kín, những cung này chính là đường biên của vùng. Một vùng có thể được giới hạn bởi hai đường cong khép kín lồng vào nhau và không cắt nhau. Các đối tượng địa lý trong cấu trúc topology được mô tả trong bốn bảng: - Ba bảng đầu lưu trữ các phần tử không gian vùng, nút, cung. - Bảng thứ tư lưu trữ tọa độ nút, nút cuối và đỉnh. Biên soạn: GV. Phạm Thế Hùng 3.5. CẤU TRÚC DỮ LIỆU VECTOR 3.5.4. Cấu trúc Topology 0 10 3020 40 50 60 70 0 70 40 30 60 50 20 10 A C B E D,a6,N5 a1 a2 a2 a3 a5 a7 a7 a7 a7 a2 a3 N2 N1 N3 N4 N6 Biên soạn: GV. Phạm Thế Hùng 3.5. CẤU TRÚC DỮ LIỆU VECTOR 3.5.4. Cấu trúc Topology Topology vùng Vùng Cung A B C D E a1, a5, a3 a2, a5, 0, a6, 0, a7 a7 a6 vùng ngoài Topology cung Cung Nút đầu Nút cuối Vùng trái Vùng phải a1 a2 a3 a4 a5 a6 a7 N1 N2 N3 N4 N3 N5 N6 N2 N3 N1 N1 N2 N5 N6 E E E A A B B A B A A B B C Topology nút Nút Cung N1 N2 N3 N4 N5 N6 a1, a3, a4 a1, a2, a5 a2, a3, a5 a4 a6 a7 Dữ liệu toạ độ cung Cung Nút đầu (x,y) Đỉnh (vertex) (x,y) Nút cuối (x,y) a1 a2 a3 a4 a5 a6 a7 40,60 70,50 10,25 40,60 10,25 30,20 55,27 70,60 70,10;10,10 10,60 30,50 20,27;30,30;50,32 55,15;40,15;45,27 70,50 10,25 40,60 30,40 70,50 30,20 55,27 Biên soạn: GV. Phạm Thế Hùng 3.5. CẤU TRÚC DỮ LIỆU VECTOR 3.5.4. Cấu trúc Topology 0 10 3020 40 50 60 70 0 70 40 30 60 50 20 10 A CB E a7 a12 a10 a1 a6 a2 a3 N2N1 N3 N4 N9 N5 N6 N7 N8 D F a4 a5 a8 a9 a11 Biên soạn: GV. Phạm Thế Hùng 3.5. CẤU TRÚC DỮ LIỆU VECTOR 3.5.5. Định dạng file phổ biến AutoCAD (.dxf): định dạng của hãng Autodesk Coverage: định dạng dữ liệu vector của ArcInfo, 1981 Shapefile: ESRI giới thiệu với ArcView, 1993, có 3 file chính: .SHP; .SHX và .DBF TAB: định dạng của MapInfo, có 4 file chính: .TAB; .DAT; .ID và .MAP Geodatabase: định dạng mới được với thiệu với ArcGIS 8.0, 2000, gồm có: Personal Geodatabase (.mdb), File Geodatabase và Enterprise Geodatabase. Biên soạn: GV. Phạm Thế Hùng 3.6. MÔ HÌNH DỮ LIỆU TIN Mô hình mạng lưới các tam giác bất đồng dạng (TIN) được dùng để thể hiện các đối tượng bề mặt trong không gian 2,5-D hoặc 3-D (bề mặt địa hình, thang tầng địa chất,). Mô hình TIN được thành lập dựa trên mô hình dữ liệu vector thông qua 3 giá trị x,y (tọa độ) và z (độ cao). A triangulated irregular network (TIN) is a digital data structure used in GIS for the representation of a surface. A TIN is a vector-based representation of the physical land surface or sea bottom, made up of irregularly distributed nodes and lines with three-dimensional coordinates (x, y, and z) that are arranged in a network of non-overlapping triangles. Biên soạn: GV. Phạm Thế Hùng 3.6. MÔ HÌNH DỮ LIỆU TIN Cấu trúc dữ liệu mô hình TIN (Nguồn: Zeiler 1999) Biên soạn: GV. Phạm Thế Hùng 3.6. MÔ HÌNH DỮ LIỆU TIN Ứng dụng của mô hình TIN A) Bản đồ nguy cơ lở đất ở Ý; B) Sông Trường Giang ở Trung Quốc (Nguồn: Paul A. Longley, 2005) Biên soạn: GV. Phạm Thế Hùng Tobler's first law of geography: - "Everything is related to everything else, but near things are more related than distant things." - Mọi đối tượng đều có mối quan hệ với nhau nhưng những đối tượng ở gần thì sẽ quan hệ nhiều hơn những đối tượng ở xa. 3.7. MỐI QUAN HỆ GIỮA CÁC ĐỐI TƯỢNG KHÔNG GIAN Biên soạn: GV. Phạm Thế Hùng Quan hệ điểm-điểm - “Trong giới hạn (is within)”: Nằm trong giới hạn một khoảng cách cụ thể. - “Gần nhất với (is nearest to)”: Gần nhất so với một điểm cụ thể. Ví dụ ? 3.7. MỐI QUAN HỆ GIỮA CÁC ĐỐI TƯỢNG KHÔNG GIAN Biên soạn: GV. Phạm Thế Hùng 3.7. MỐI QUAN HỆ GIỮA CÁC ĐỐI TƯỢNG KHÔNG GIAN Quan hệ điểm-đường - “Nằm trên đường (on line)”: điểm nằm trên một đường. - “Gần nhất với (is nearest to)”: Điểm gần nhất so với một đường. Ví dụ? Biên soạn: GV. Phạm Thế Hùng Quan hệ điểm-vùng - “Chứa bên trong vùng (is contained in)”: Điểm chứa bên trong vùng. - “Nằm trên biên (on border of area)”: Một điểm nằm trên đường biên của vùng. Ví dụ? 3.7. MỐI QUAN HỆ GIỮA CÁC ĐỐI TƯỢNG KHÔNG GIAN Biên soạn: GV. Phạm Thế Hùng Quan hệ đường-đường - “Giao nhau (intersects)”: Hai đường giao nhau. - “Băng qua (crosses)”: Hai đường băng qua mà không giao nhau. - “Chảy vào (flow into)”: Một nhánh sông chảy vào một dòng sông. Ví dụ? 3.7. MỐI QUAN HỆ GIỮA CÁC ĐỐI TƯỢNG KHÔNG GIAN Biên soạn: GV. Phạm Thế Hùng Quan hệ đường-vùng - “Giao nhau (intersects)”: Một đường giao (cắt) với một vùng. - “Đường biên (borders)”: Đường là một phần biên của vùng. Ví dụ? 3.7. MỐI QUAN HỆ GIỮA CÁC ĐỐI TƯỢNG KHÔNG GIAN Biên soạn: GV. Phạm Thế Hùng Quan hệ vùng-vùng - “Chồng lớp (overlaps)”: Hai vùng chồng lên nhau. - “Nằm bên trong (is within)”: Một vùng nằm bên trong một vùng khác. - “Kế cận (is adjacent to)”: Hai vùng cùng có một đường biên chung. Ví dụ? 3.7. MỐI QUAN HỆ GIỮA CÁC ĐỐI TƯỢNG KHÔNG GIAN Biên soạn: GV. Phạm Thế Hùng 3.7. MỐI QUAN HỆ GIỮA CÁC ĐỐI TƯỢNG KHÔNG GIAN Biên soạn: GV. Phạm Thế Hùng 3.8. SO SÁNH GIỮA RASTER VÀ VECTOR Raster Vector Cấu trúc dữ liệu Đơn giản Phức tạp Dung lượng Lớn Bé Chất lượng đồ họa Trung bình Tốt Chồng lớp Đơn giản Phức tạp Phân tích mạng Không Dễ dàng Độ chính xác hình học Thấp Cao Topology Khó khăn Dễ dàng Phân tích không gian Đơn giản Phức tạp