ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
NGUYỄN SƠN
PHƯƠNG PHÁP PHÂN CỤM DỮ LIỆU
KHÔNG GIAN VÀ ỨNG DỤNG TRONG VIỆC
XÁC ĐỊNH VỊ TRÍ TỐI ƯU ĐẶT MÁY ATM LUẬN VĂN THẠC SỸ HÀ NỘI -2011
HÀ NỘI -2011
MỤC LỤC
CHƢƠNG 1. MỞ ĐẦU 1
CHƢƠNG 2. TỔNG QUAN HỆ THÔNG TIN ĐỊA LÝ VÀ KHAI PHÁ DỮ LIỆU
KHÔNG GIAN 3
2.1. Tổng quan về Hệ thông tin địa lý 3
2.1.1. Một số định nghĩa về hệ thông tin địa lý 3
2.1.2. Các thành phần của hệ thông tin địa lý 4
2.1.3. Biểu diễn dữ liệu địa lý 7
2.1.4. Phân tích và xử lý dữ liệu không gian 14
2.1.5. Ứng dụng của hệ thông tin địa lý 19
2.2. Tổng quan về khai phá dữ liệu 21
2.2.1. Khái niệm 21
2.2.2. Tiến trình khai phá dữ liệu 21
2.2.3. Các mô hình khai phá dữ liệu 23
2.2.4. Các hƣớng tiếp cận và kỹ thuật sử dụng trong khai phá dữ liệu 24
2.2.5. Các dạng dữ liệu có thể khai phá 25
2.2.6. Các ứng dụng của khai phá dữ liệu 25
2.3. Khai phá dữ liệu không gian 26
2.3.1. Các đặc trƣng của khai phá dữ liệu không gian 26
2.3.2. Kho dữ liệu không gian và các chiều dữ liệu 27
2.3.3. Một số ứng dụng của khai phá dữ liệu không gian 28
CHƢƠNG 3. PHÂN CỤM DỮ LIỆU KHÔNG GIAN 32
3.1. Khái quát về phân cụm dữ liệu 32
3.1.1. Phân cụm phân hoạch 32
3.1.2. Phân cụm phân cấp 35
3.1.3. Phân cụm dựa trên mật độ 36
3.1.4. Phân cụm dựa trên lƣới 49
3.2. Phân cụm dữ liệu không gian 50
3.2.1. Các đặc trƣng của dữ liệu không gian 50
quanh một khu vực ở Regensburg [ESKS01] 29
Hình 14: Khái quát hóa mô hình 3D của vật thể 29
Hình 15: Phân cụm dữ liệu ảnh viễn thám thu được theo sự tổ hợp tín hiệu của 5 kênh
màu của 5 ảnh viễn thám vùng ven biển California [ESKS01] 30
Hình 16: Phân tích thủy hệ tại vùng Nebraska, Hoa Kỳ [JOS11] 30
Hình 17: các địa phương có tỷ lệ người nghỉ hưu cao [ESKS01] 31
Hình 18: Minh họa thuật toán k-means 34
Hình 19: Phân cụm phân cấp 35
Hình 20: Kề mật độ trực tiếp, q là đối tượng lõi (core), p là đối tượng biên. 37
Hình 21: Kề mật độ 37
Hình 22: Kết nối theo mật độ 38
Hình 23: Minh họa đồ thị khoảng cách 4-dist đã được sắp xếp của một CSDL 41
Hình 24: Đồ thị k-dist và một phương pháp ước lượng tham số Eps 42
Hình 25: Đồ thị 4-dist của dữ liệu bản đồ “Hệ thống siêu thị” 42
Hình 26: Đồ thị 4-dist của dữ liệu bản đồ “Ngân hàng” 43
Hình 27: Các cụm phát hiện được bởi CLARANS (a) và DBSCAN (b) 43
Hình 28: Các cụm được phát hiện bởi DBRS(a), DBSCAN(b), K-Means(c),
CLARANS(d) [WAHA03]. 49
Hình 29: Phân cụm dựa theo lưới vùng 49
Hình 30: Quan hệ về hướng của các đối tượng không gian [ESKS01] 52
Hình 31: Mô hình 9-intersection [EGFRA94] 53
Hình 32: Quan hệ về tô pô của các đối tượng không gian [ESKS01] 53
Hình 33: Khoảng cận điểm 55
Hình 34: Khoảng cách cận-viễn 56
Hình 35: So sánh khoảng cách Hausdorff với khoảng cách tâm 56
Hình 36: Mối quan hệ tô pô giữa hai đa giác dựa trên đối tượng tham chiếu tuyến
tính. 60
Hình 37: Hình ảnh chồng phủ (vùng màu vàng) của các cụm “Ngân hàng” (màu xanh)
và “Siêu thị” (màu đỏ) 68
Hình 38: Kết quả phân cụm DBRS đối với dữ liệu thử nghiệm tự tạo 69
1
CHƢƠNG 1. MỞ ĐẦU
Khai phá dữ liệu không gian hay còn gọi là khai phá tri thức từ dữ liệu không
gian là một lĩnh vực có nhu cầu rất cao. Bởi lẽ dữ liệu đầu vào ở đây bao gồm một
khối lượng dữ liệu không gian khổng lồ đã được thu thập từ nhiều ứng dụng khác
nhau, từ thiết bị viễn thám đến hệ thống thông tin địa lý, từ bản đồ số, từ các hệ thống
quản lý và đánh giá môi trường, …Việc phân tích và khai thác lượng thông tin khổng
lồ này ngày càng tạo ra các thách thức và khó khăn, đòi hỏi phải có các nghiên cứu sâu
hơn để tìm ra các kỹ thuật khai phá dữ liệu hiệu quả hơn.
Trong những năm gần đây, việc nghiên cứu về khai phá dữ liệu đã có xu hướng
chuyển từ cơ sở dữ liệu quan hệ và cơ sở dữ liệu giao dịch sang cơ sở dữ liệu không
gian. Sự thay đổi này không những giúp hiểu được dữ liệu không gian mà còn giúp
khám phá được mối quan hệ giữa dữ liệu không gian và phi không gian, các mô hình
dựa trên tri thức không gian, phương pháp tối ưu câu truy vấn, tổ chức dữ liệu trong cơ
sở dữ liệu không gian, Khai phá dữ liệu không gian được sử dụng nhiều trong các hệ
thống thông tin địa lý (GIS), viễn thám, khai phá dữ liệu ảnh, ảnh y học, rô bốt dẫn
đường, … Khám phá tri thức từ dữ liệu không gian có thể được thực hiện dưới nhiều
hình thức khác nhau như sử dụng các quy tắc đặc trưng và quyết định, trích rút và mô
tả các cấu trúc hoặc cụm nổi bật, kết hợp không gian, …
Các bài toán truyền thống của một hệ thông tin địa lý có thể trả lời các câu hỏi
kiểu như:
- Những con phố nào dẫn đến Nhà hát lớn Hà Nội ?
- Những căn nhà nào nằm trong vùng quy hoạch mở rộng phố?
Khai phá dữ liệu không gian có thể giúp trả lời cho các câu hỏi dạng:
- Xu hướng của các dòng chảy, các đứt gãy địa tầng ?
- Nên bố trí các trạm tiếp sóng điện thoại di động như thế nào?
- Những vị trí nào là tối ưu để đặt các máy ATM ?
Một trong những bài toán liên quan đến dữ liệu không gian, cụ thể là dữ liệu địa
lý có ý nghĩa thực tế cao là bài toán xác định vị trí tối ưu cho việc đặt các máy ATM
3 CHƢƠNG 2. TỔNG QUAN HỆ THÔNG TIN ĐỊA LÝ VÀ KHAI PHÁ DỮ
LIỆU KHÔNG GIAN
2.1. Tổng quan về Hệ thông tin địa lý
Khái niệm Địa lý (Geography) đề cập lĩnh vực nghiên cứu mô tả Trái đất (Geo-
Earth). Ngày nay, khái niệm này và khái niệm Không gian (Space) được sử dụng thay
thế nhau trong một số trường hợp. Tuy nhiên, về mặt bản chất thì Địa lý là tập các mô
tả về không gian (hai chiều), khí quyển (ba chiều), … của Trái đất. Còn Không gian
cho phép mô tả bất kỳ cấu trúc đa chiều nào, không quan tâm đến vị trí địa lý của nó.
Như vậy có thể coi Địa lý như là một phần cấu trúc nhỏ trong tập cấu trúc Không gian.
Khi mô tả Trái đất, các nhà địa lý luôn đề cập đến quan hệ không gian (spatial
relationship) của các đối tượng trong thế giới thực. Mối quan hệ này được thể hiện
thông qua các bản đồ (map) trong đó biểu diễn đồ họa của tập các đặc trưng trừu tượng
và quan hệ không gian tương ứng trên bề mặt trái đất, ví dụ: bản đồ dân số biểu diễn
dân số tại từng vùng địa lý.
Dữ liệu bản đồ còn là loại dữ liệu có thể được số hóa. Để lưu trữ và phân tích các
số liệu thu thập được, cần có sự trợ giúp của hệ thông tin địa lý (Geographic
Information System-GIS).
2.1.1. Một số định nghĩa về hệ thông tin địa lý
Có nhiều cách diễn giải khác nhau cho từ viết tắt GIS, tuy nhiên các cách diễn
giải đó đều mô tả việc nghiên cứu các thông tin địa lý và các khía cạnh khác liên quan.
GIS cũng giống như các hệ thống thông tin khác, có khả năng nhập, tìm kiếm và
quản lý các dữ liệu lưu trữ, để từ đó đưa ra các thông tin cần thiết cho người sử dụng.
Ngoài ra, GIS còn cho phép lập bản đồ với sự trợ giúp của máy tính, giúp cho việc
biểu diễn dữ liệu bản đồ tốt hơn so với cách truyền thống. Dưới đây là một số định
nghĩa GIS hay dùng [DVD01]:
Định nghĩa của dự án The Geographer's Craft, Khoa Địa lý, Trường Đại học
Texas
phố, người dùng có thể chọn một thành phố để xem thông tin về thành phố đó như
diện tích, số dân, thu nhập bình quân, số quận/huyện của thành phố, …
2.1.2. Các thành phần của hệ thông tin địa lý
Một hệ thông tin địa lý thường bao gồm 5 thành phần:
Con người
Dữ liệu
Phần cứng
Phần mềm
Phương pháp phân tích dữ liệu Hình 1: 5 thành tố của GIS
5
Các thành phần này kết hợp với nhau nhằm tự động quản lý và phân phối thông tin
thông qua biểu diễn địa lý.
Hình 2: Mối quan hệ giữa các thành phần của GIS
Con người
Con người là thành phần quan trọng nhất, là nhân tố thưc hiện các thao tác điều
hành sự hoạt động của hệ thống GIS. Con người tham gia vào hệ thông tin địa lý với
một hoặc nhiều vai trò sau:
Người xây dựng bản đồ: sử dụng các lớp bản đồ được lấy từ nhiều nguồn khác
nhau, chỉnh sửa dữ liệu để tạo ra các bản đồ theo yêu cầu.
Người thiết kế CSDL: xây dựng các mô hình dữ liệu lôgic và vật lý.
Người phát triển: xây dựng hoặc cải tạo các phần mềm GIS để đáp ứng các nhu
cầu cụ thể.
Người dùng GIS là những người sử dụng các phần mềm GIS để giải quyết các
bài toán không gian theo mục đích của họ. Họ thường là những người được đào
tạo tốt về lĩnh vực GIS hay là các chuyên gia.
Mục đích chung của mọi hệ thông tin là khai thác, phân tích, xử lý dữ liệu để
đưa ra các thông tin phục vụ nhu cầu của con người. Các chức năng phân tích, xử lý và
trình bày dữ liệu của một hệ thông tin địa lý tối thiểu phải gồm:
Capture: thu thập dữ liệu. Dữ liệu có thể lấy từ rất nhiều nguồn, có thể là bản đồ
giấy, ảnh chụp, bản đồ số…
Store: lưu trữ. Dữ liệu có thể được lưu dưới dạng vector hay raster (sẽ đề cập ở
mục sau).
Query: truy vấn (tìm kiếm). Người dùng có thể truy vấn thông tin đồ họa hiển
thị trên bản đồ.
Analyze: phân tích. Đây là chức năng hỗ trợ việc ra quyết định của người dùng.
Display: hiển thị. Hiển thị dữ liệu địa lý và kết quả phân tích dưới những cách
thức hiểu được đối với người dùng.
Output: xuất dữ liệu. Hỗ trợ việc kết xuất dữ liệu bản đồ dưới nhiều định dạng:
giấy in, Web, ảnh, file…
7
2.1.3. Biểu diễn dữ liệu địa lý
2.1.3.1. Các thành phần của dữ liệu địa lý
Trong GIS, dữ liệu được chia làm hai loại: thành phần không gian và thành phần
phi không gian (thuộc tính). Hai loại thành phần dữ liệu này được kết hợp thông qua
một chỉ số chung để mô tả một đối tượng thực. Sự kết hợp này thể hiện đặc trưng
không gian của đối tượng, nó cho phép:
Mô tả “vị trí, hình dạng”: vị trí tham chiếu, đơn vị đo, dạng hình học của thực
thể địa lý.
Mô tả “quan hệ và tương tác” giữa các thực thể địa lý: những thửa đất nào
liền kề với khu công nghiệp ?
Mô tả “thông tin” của các đối tượng địa lý: ai là chủ sở hữu của thửa đất này,
thuộc quản lý của địa phương nào?
Thành phần không gian
Thành phần dữ liệu không gian hay thường được gọi là dữ liệu hình học hay dữ
Các đối tượng được biểu diễn bằng kiểu đường thường mang đặc điểm là có dãy
các cặp tọa độ, các đường bắt đầu và kết thúc hoặc cắt nhau bởi điểm. Ví dụ, bản đồ hệ
thống đường bộ, sông, đường biên giới hành chính, … thường được biểu diễn bởi
đường và trên đường có các điểm (vertex) để xác định vị trí và hình dáng của đường
đó.
Hình 4. Ví dụ biểu diễn đường
9 Vùng (Polygon)
Vùng được xác định bởi ranh giới của nó là đường gấp khúc, có điểm đầu trùng
với điểm cuối. Các đối tượng địa lý có diện tích và được bao quanh bởi đường thường
được biểu diễn bởi vùng.
Các đối tượng biểu diễn bởi vùng có đặc điểm là được mô tả bằng tập các đường
bao quanh vùng và điểm nhãn (label point) thuộc vùng để mô tả, xác định cho mỗi
vùng. Ví dụ, các khu vực hành chính, hình dạng các công viên, … được mô tả bởi kiểu
dữ liệu vùng. Hình 5 mô tả ví dụ cách lưu trữ một đối tượng vùng.
Hình 5. Ví dụ biểu diễn khu vực hành chính
Một đối tượng có thể biểu diễn bởi các kiểu khác nhau tùy thuộc vào tỷ lệ của
bản đồ đó. Ví dụ, đối tượng công viên có thể được biểu diễn bởi điểm trong bản đồ có
tỷ lệ nhỏ, và bởi vùng trong bản đồ có tỷ lệ lớn.
Thành phần phi không gian
Thành phần dữ liệu phi không gian hay còn gọi là dữ liệu thuộc tính, là những
diễn tả đặc tính, số lượng, mối quan hệ của các hình ảnh bản đồ với vị trí địa lý của
chúng thông qua một cơ chế thống nhất. Hệ thống GIS có cơ chế liên kết dữ liệu
không gian và phi không gian của cùng một đối tượng với nhau. Có thể nói, một trong
những chức năng đặc biệt của công nghệ GIS chính là khả năng liên kết và xử lý đồng
thời dữ liệu bản đồ và dữ liệu thuộc tính.
hình biểu diễn dữ liệu địa lý đóng vai trò quan trọng vì cách thức biểu diễn thông tin sẽ
ảnh hưởng tới khả năng thực hiện phân tích dữ liệu và khả năng hiển thị đồ họa của
một hệ thống thông tin địa lý.
Các mức trừu tượng của dữ liệu được thể hiện qua 3 mức mô hình, bao gồm [DVD01]:
- Mô hình quan niệm
- Mô hình logic
- Mô hình vật lý
Mô hình quan niệm
Đây là mức trừu tượng đầu tiên trong tiến trình biểu diễn các thực thể địa lý. Là tập
các thành phần và các quan hệ giữa chúng liên quan đến hiện tượng tự nhiên nào đó.
Mô hình này độc lập lập với hệ thống, độc lập với cấu trúc, tổ chức và quản lý dữ liệu.
Một số mô hình quan niệm thường được sử dụng trong GIS là:
Mô hình không gian trên cơ sở đối tượng:
Mô hình này tập trung vào các hiện tượng, thực thể riêng rẽ được xem xét độc
lập hay cùng với quan hệ của chúng với thực thể khác. Bất kỳ thực thể lớn hay
11
nhỏ đều được xem như một đối tượng và có thể độc lập với các thực thể láng
giềng. Đối tượng này lại có thể bao gồm các đối tượng khác và chúng cũng có
thể có quan hệ với các đối tượng khác. Ví dụ các đối tượng kiểu thửa đất và hồ
sơ là tách biệt với các đối tượng khác về không gian và thuộc tính.
Mô hình hướng đối tượng phù hợp với các thực thể do con người tạo ra
như nhà cửa, đường quốc lộ, các điểm tiện ích hay các vùng hành chính. Một số
thực thể tự nhiên như sông hồ, đảo…cũng thường được biểu diễn bằng mô hình
đối tượng do chúng cần được xử lý như các đối tượng rời rạc. Mô hình dữ liệu
kiểu vector (sẽ đề cập đến ở phần sau) là một ví dụ của mô hình không gian trên
cơ sở đối tượng.
Mô hình không gian trên cơ sở mạng:
Mô hình này có một vài khía cạnh tương đồng với mô hình hướng đối tượng,
việc cập nhật, sửa đổi dữ liệu thường gặp nhiều khó khăn.
Cấu trúc dữ liệu cung nút:
Cấu trúc dữ liệu cung nút mô tả các thực thể địa lý dưới dạng các điểm (nút) và
các đường (cung). Như vậy, có thể biểu diễn được quan hệ topo giữa các đối
tượng địa lý. Trong cấu trúc dữ liệu này, các phần đối tượng không gian kề
nhau sẽ được lưu trữ một lần, ngoài ra, các đối tượng lân cận của một đối tượng
địa lý cũng được chỉ rõ, điều này giúp dễ dàng thực hiện các phép phân tích
không gian, đồng thời cũng tối ưu được dung lượng lưu trữ dữ liệu.
Cấu trúc dữ liệu dạng cây:
Trong một số mô hình dữ liệu như mô hình raster, dữ liệu có thể được phân
hoạch thành các đối tượng nhỏ hơn với nhiều mức khác nhau để giảm thiểu
dung lượng lưu trữ và tăng tốc độ truy vấn. Ví dụ cấu trúc cây tứ phân chia một
vùng dữ liệu làm 4 phần, trong mỗi phần này lại có thể được chia tiếp thành 4
phần con.
Mô hình dữ liệu vật lý
Dữ liệu địa lý cần được lưu trữ vật lý trên máy tính theo một cách thức nhất định,
tùy theo các hệ thống thông tin địa lý cụ thể mà cách thức lưu trữ, cài đặt dữ liệu
khác nhau. Mô hình dữ liệu vật lý thường khá khác nhau đối với từng hệ thống GIS cụ
thể. Một số hệ GIS thương mại có thể kể đến như: Arc/Info, ERDAS, Geovision,
Grass, Caris, DBMS based, Ingres, Oracle, Postgres…có các cách thức lưu trữ vật lý
dữ liệu khác nhau, đồng thời cũng chia sẻ một vài khuôn dạng dữ liệu chung để có thể
dễ dàng trao đổi.
Như vậy, từ một thực thể địa lý, thông qua 3 mức mô hình biểu diễn mà được
cụ thể hóa thành dữ liệu trên máy tính và có thể có dạng thể hiện khác nhau đối với
từng hệ GIS cụ thể. Mỗi hệ thông tin địa lý đều sử dụng mô hình dữ liệu quan niệm
riêng để biểu diễn mô hình dữ liệu vật lý duy nhất. Hệ thông tin địa lý cung cấp các
phương pháp để người sử dụng làm theo các mô hình quan niệm tương tự ba lớp mô
hình mô tả trên.
vector. Nếu đối tượng quản lý được phân loại liên tục như loại đất, mức nước hay độ
cao của núi, … thì thường dùng mô hình raster. Đồng thời, nếu dữ liệu thu thập từ các
nguồn khác nhau được dùng một mô hình nào đó thì có thể chuyển đổi từ mô hình này
sang mô hình khác để phục vụ tốt cho việc xử lý của người dùng.
Mỗi mô hình có ưu điểm và nhược điểm khác nhau. Về mặt lưu trữ, việc lưu trữ
giá trị của tất cả các ô/điểm ảnh trong mô hình raster đòi hỏi không gian nhớ lớn hơn
so với việc chỉ lưu các giá trị khi cần trong mô hình vector. Cấu trúc dữ liệu lưu trữ
của raster đơn giản, trong khi vector dùng các cấu trúc phức tạp hơn. Dung lượng lưu
trữ trong mô hình raster có thể lớn hơn gấp 10 đến 100 lần so với mô hình vector. Đối
với thao tác chồng phủ (xem mục 2.1.4.4), mô hình raster cho phép thực hiện một cách
dễ dàng, trong khi mô hình vector lại phức tạp và khó khăn hơn. Về mặt hiển thị, mô
hình vector có thể hiển thị đồ họa vector giống như bản đồ truyền thống, còn mô hình
raster chỉ hiển thị ảnh nên có thể xuất hiện hình răng cưa tại đường biên của các đối
tượng tùy theo độ phân giải của tệp raster. Với dữ liệu vector, người dùng có thể bổ
sung, co dãn hoặc chiếu bản đồ, thậm chí có thể kết hợp với các tầng bản đồ khác
thuộc các nguồn khác nhau. Hiện nay, mô hình vector được sử dụng nhiều trong các hệ
thống GIS bởi các lý do trên, ngoài ra mô hình này cho phép cập nhật và duy trì đơn
giản, dễ truy vấn dữ liệu.
2.1.4. Phân tích và xử lý dữ liệu không gian
Các phép phân tích và xử lý dữ liệu không gian là một trong 5 yếu tố cấu thành nên
một hệ thông tin địa lý (xem mục 2.1.2). Mục này đề cập đến một số phép phân tích xử
lý dữ liệu cơ bản nhất của một hệ GIS. Các thao tác trên dữ liệu không gian thường
chia làm hai lớp bài toán cơ bản là các bài toán về tìm kiếm và phân tích không gian và
các bài toán về xử lý dữ liệu không gian.
Lớp bài toán tìm kiếm và phân tích không gian: bao gồm các bài toán liên quan đến
việc khai thác thông tin và tri thức từ dữ liệu không gian. Ví dụ như bài toán tìm kiếm
đối tượng trên bản đồ theo thuộc tính, bài toán phân tích đường đi, tìm đường…
Lớp bài toán xử lý dữ liệu không gian: bao gồm các bài toán thao tác trực tiếp tới
khuôn dạng, giá trị của dữ liệu không gian, làm thay đổi dữ liệu không gian. Ví dụ như
các thao tác nắn chỉnh dữ liệu, tổng quát hóa dữ liệu, chuyển đổi hệ tọa độ, chuyển đổi
Việc tìm kiếm hiện tượng trong GIS bao gồm tìm kiếm hiện tượng độc lập hoặc
tìm kiếm tổ hợp các hiện tượng.
Tìm kiếm hiện tượng độc lập là bài toán đơn giản, chỉ bao hàm tìm kiếm một
hiện tượng, thực thể mà không quan tâm đến một hiện tượng, thực thể khác. Việc tìm
kiếm đơn giản chỉ là truy nhập dữ liệu không gian dựa trên thuộc tính đã xác định
trước. Ví dụ như tìm các tỉnh, thành phố có dân số lớn hơn 2 triệu người…
Tìm kiếm tổ hợp thực thể là bài toán phức tạp hơn, nhưng lại là bài toán hấp dẫn
và là thế mạnh của GIS, việc tìm kiếm liên quan đến nhiều thực thể hay lớp thực thể,
chẳng hạn, tính diện tích đất nông nghiệp của quận Thanh Trì, Hà Nội. Bài toán này
đòi hỏi phải tổ hợp 2 lớp thực thể địa lý là lớp đất nông nghiệp của thành phố Hà Nội
và lớp ranh giới hành chính thành phố Hà Nội. Kiểu bài toán này trong GIS gọi là bài
toán chồng phủ bản đồ.
Bài toán chồng phủ bản đồ
Như trên đã đề cập, nhiều vấn đề trong GIS đòi hỏi sử dụng sự chồng xếp
của các lớp dữ liệu chuyên đề khác nhau. Chẳng hạn như chúng ta muốn biết vị trí của
các căn hộ giá rẻ nằm trong khu vực gần trường học; hay khu vực nào là các bãi thức
ăn của cá voi trùng với khu vực có tiềm năng dầu khí lớn có thể khai thác; hoặc là vị trí
các vùng đất nông nghiệp trên các khu vực đất đai bị xói mòn,… Trong ví dụ liên quan
đến đất xói mòn trên, một lớp dữ liệu đất đai có thể được sử dụng để nhận biết các khu
vực đất đai bị xói mòn, đồng thời lớp dữ liệu về hiện trạng sử dụng đất cũng được sử
dụng để nhận biết vị trí các vùng đất sử dụng cho mục đích nông nghiệp. Thông thường
thì các đường ranh giới của vùng đất bị xói mòn sẽ không trùng với các đường ranh giới
của các vùng đất nông nghiệp, do đó, dữ liệu về loại đất và sử dụng đất sẽ phải được kết
hợp lại với nhau theo một cách nào đó. Chồng phủ bản đồ chính là phương tiện hàng
đầu hỗ trợ việc thực hiện phép kết hợp dữ liệu đó.
Trong mô hình vector, các đối tượng địa lý được biểu diễn dưới dạng các
điểm, đường và vùng. Vị trí của chúng được xác định bởi các cặp tọa độ và thuộc tính
của chúng được ghi trong các bảng thuộc tính. Với từng kiểu bản đồ, người ta phân biệt
ba loại chồng phủ bản đồ vector sau:
Chồng phủ đa giác trên đa giác:
trong chồng xếp đa giác, các điểm cắt được tính toán, các nút và các liên kết được hình
thành, topo được thiết lập và cuối cùng là các bảng thuộc tính được cập nhật.
Minh họa cụ thể cho vấn đề chồng xếp bản đồ chúng ta sẽ xét tới tiến trình phủ đa
giác. Tiến trình này được minh họa bởi hình sau:
Copyright: Tài liệu đại học ©