-
0012029
0012086
H
TRẮC NGỌC ĐĂNG
BÙI THẾ TÀI
K
H
TN
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
KHOA CÔNG NGHỆ THÔNG TIN
BỘ MÔN CÔNG NGHỆ PHẦN MỀM
Đ
Đề tài:
K
H
O
A
C
N
TT
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
KHOA CÔNG NGHỆ THÔNG TIN
BỘ MÔN CÔNG NGHỆ PHẦN MỀM
Đ
Đề tài:
C
N
TT
–
KẾT HỢP CHUẨN OPENGIS VÀ HỆ QUẢN TRỊ CƠ
SỞ DỮ LIỆU ĐỂ GIẢI QUYẾT MỘT SỐ BÀI TOÁN
TỐI ƯU TRÊN MẠNG GIAO THÔNG THÀNH PHỐ.
K
H
O
A
LUẬN VĂN CỬ NHÂN TIN HỌC
GVHD : Th.Sĩ NGUYỄN MINH NAM
NIÊN KHOÁ 2000 - 2004
-2-
em trong suốt thời gian thực hiện luận văn tốt nghiệp này.
Cuối cùng, chúng tôi xin cám ơn tất cả các bạn học đã giúp chúng tôi giải
quyết những vướng mắc nho nhỏ trong quá trình làm việc.
K
H
O
A
Xin cảm ơn tất cả.
-Trắc Ngọc Đăng – Bùi Thế Tài
-3-
Viết thuê luận văn thạc sĩ
[email protected] - 0972.162.399
MỤC LỤC
LỜI CẢM ƠN ...........................................................................................................1
LỜI MỞ ĐẦU...........................................................................................................2
K
H
TN
CHƯƠNG 1: TỔNG QUAN VỀ GIS
1.1. Hệ thống thông tin địa lý là gì?..........................................................................4
1.2. Mô hình dữ liệu của hệ thống thông tin địa lý...................................................5
K
H
O
A
3.4. Thuật giải Lin-Kernighan cải tiến (2002) ........................................................87
3.5. Các thủ thuật cải tiến thuật giải L-K trong quá trình cài đặt .........................108
3.6. Các cấu trúc dữ liệu quan trọng của thuật giải Lin-Kernighan......................110
3.7. Kết chương.....................................................................................................112
THUYẾT MINH CHƯƠNG TRÌNH THỬ NGHIỆM.........................................113
KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ............................................................119
PHỤ LỤC..............................................................................................................121
A. BÀI TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT GIỮA 2 ĐIỂM .......................122
B. BÀI TOÁN XỬ LÝ ĐIỀU PHỐI CẤP THỜI (EMERGENCY).....................123
-4-
Viết thuê luận văn thạc sĩ
[email protected] - 0972.162.399
C. GIỚI THIỆU VỀ NÚT ẢO. .......................................................................................124
K
H
O
A
TN
quý nay lại càng quý hơn.
Thực tế đã cho chúng ta thấy, có những việc đòi hỏi rất nghiêm khắc
về thời gian, mà nếu không đáp ứng được có thể sẽ có một hậu quả nghiêm
trọng, ảnh hưởng đến tính mạng con người cho đến tiêu hao về của cải vật
chất. Ví dụ như: các hoạt động phòng cháy chữa cháy, cảnh sát phản ứng
H
nhanh 113, đề xuất một lộ trình thích hợp cho một lần phân phối sản phẩm
Đ
từ công ty mẹ đến các đại lý, lập lịch cho một thiết bị vận hành...Nhưng làm
sao để ta biết phải điều phối các hoạt động đó thế nào thì hợp lý nhất; làm
–
sao ta có được một lộ trình tối ưu với rất nhiều điểm phải đến trong một
C
N
TT
khoảng thời gian tương đối ngắn mà ta không phải đợi dài cổ tính, toán suy
nghĩ cho mệt óc. Đây rõ ràng là các vấn đề nan giải.
H
Đ
CHƯƠNG 1
K
H
O
A
C
N
TT
–
TỔNG QUAN VỀ GIS
-7-
Viết thuê luận văn thạc sĩ
[email protected] - 0972.162.399
1.1 Hệ thống thông tin điạ lý (GIS – Geographic Information
System) là gì ?
Hệ thống thông tin điạ lý (Geographical Information System – GIS) là sự
kết hợp giữa công nghệ bản đồ số hoá với công nghệ quản trị cơ sở dữ liệu cho
GIS
K
H
O
A
CAD
Ảnh
Viễn thám
Phân tích không
Hình 1.1 : Hệ thống thông tin điạ lý với sự tích hợp các ngành khoa học khác
nhau.
-8-
Viết thuê luận văn thạc sĩ
[email protected] - 0972.162.399
1.2 Mô hình dữ liệu của hệ thống thông tin điạ lý :
1.2.1 Dữ liệu điạ lý:
Do sự tích hợp liên ngành nên hệ thống thông tin điạ lý làm việc với nhiều
nguồn thông tin khác nhau như: bản đồ, ảnh hàng không, ảnh viễn thám... Hệ
K
Định nghĩa: Dữ liệu địa lý là các dữ liệu số mô tả các đối tượng trong thế
Dữ liệu điạ lý được tổ chức thành hai nhóm thông tin chính, đó là:
1/ Nhóm thông tin về phân bố không gian.
K
H
O
A
2/ Nhóm thông tin về thuộc tính của đối tượng.
1.2.2 Mô hình bản đồ chồng xếp:
Một trong những phương pháp chung nhất của tổ chức dữ liệu điạ lý là tổ
chức theo bản đồ và các lớp thông tin. Mỗi lớp thông tin là một biểu diễn của dữ
liệu theo một mục tiêu nhất định, do vậy nó thường là một hoặc một vài dạng của
thông tin. Ví dụ để nghiên cứu nguồn tài nguyên thiên nhiên, điạ chất, các điều
kiện vật lý lớp dưới đất, sử dụng đất, kênh rạnh……Người ta tách chúng thành các
lớp.
-9-
Viết thuê luận văn thạc sĩ
[email protected] - 0972.162.399
Đối với bài toán quy hoạch thành phố, các thông tin có thể là dữ liệu về
đường phố, công trình công cộng, giao thông, phân vùng….Các thông tin này
A
Không giống như các dạng dữ liệu thông dụng khác, dữ liệu điạ lý phức tạp
hơn, nó bao gồm các thông tin về điạ lý, các quan hệ topo và các thuộc tính phi
không gian. Mọi dữ liệu điạ lý có thể được mô hình với ba thành phần khác nhau
theo quan niệm topology – điểm, đường, vùng.Bất kì một đối tượng tự nhiên nào
đều có thể được biểu diễn bằng một trong bao đối tượng này kèm theo chúng là
những thông tin đặc thù riêng.
Mô hình dữ liệu điạ lý bao gồm bốn thành phần sau:
1. Thành phần khoá.
2. Định vị.
- 10 -
Viết thuê luận văn thạc sĩ
[email protected] - 0972.162.399
3. Thành phần phi không gian.
4. Thành phần không gian.
Khoá : là mã số duy nhất cho thực thể để phân biệt thực thể này với thực thể
khác.
K
H
TN
Định vị: Chỉ ra vị trí của thực thể.
Hình1.3: minh hoạ về các thực thể được thể hiện trên bản đồ
Mô hình Raster : Dữ liệu Raster được phân biệt bằng đơn vị pixel, đó là
hình ảnh đơn vị nhỏ nhất phản ánh đối tượng trong không gian.
Cấu trúc dữ liệu ratser 2-D được xem như là một ma trận các ô lưới đặc trưng cho
một ô vuông bề mặt đất. Độ phân giải của dữ liệu raster phụ thuộc vào kích thước
của những ô lưới này.
- 11 -
Viết thuê luận văn thạc sĩ
[email protected] - 0972.162.399
K
H
TN
Hình 1.4 :minh hoạ dữ liệu raster, ta có một ma trận với các giá trị khác nhau.
Trong đó nước có giá trị 1, rừng là 2 và đất nông nghiệp là 3
1.3 Thu thập các nguồn dữ liệu của GIS:
H
Có nhiều kỹ thuật để thu thập thông tin cho các nguồn dữ liệu. Nó thường
được thu thập từ việc đo đạc trực tiếp trên những vùng địa trắc khác nhau. Tuy
nguồn sẽ được trãi bề mặt ngang, một con trỏ sẽ xác định tọa độ các điểm tạo nên
hình dạng bản đồ, sau quá trình số hoá, thuộc tính của các đối tượng mới được
thêm vào. Phương pháp này đòi hỏi nhiều thời gian và nguồn dữ liệu có được từ
kỹ thuật này dưới hình thức Vectơ.
Phương pháp vectơ hoá :
- 12 -
Viết thuê luận văn thạc sĩ
[email protected] - 0972.162.399
Một vài hệ thống máy tính chuyên nghiệp có thể chuyển đổi dữ liệu Raster
sang dạng dữ liệu Vectơ. Phương pháp này cho tốc độ nhanh do tính tự động
nhưng lại kém chính xác hơn so với việc số hoá thủ công.
Các kỹ thuật trên đều dựa vào nguồn dữ liệu bản đồ giấy có sẵn. Trên thực tế,
K
H
TN
người ta còn dựa vào các ngành lĩnh vực khác như : viễn thám, GPS, phân tích ảnh
… để thu thập nguồn dữ liệu cho GIS.
1.4 Hiện trạng ứng dụng công nghệ GIS tại Việt Nam :
Hiện nay công nghệ thông tin phát triển rất mạnh mẽ, nhiều công nghệ tiên
tiến trước đây chỉ có ở các nước phát triển thì hiện nay đã có mặt ở Việt Nam. Đối
Công nghệ GIS với những lợi thế của nó đã mang lại phương pháp quản lý
hiệu quả hơn, mọi sự vật, đối tượng, từ những thông tin không gian đến những
thông tin phi không gian tất cả đều được quản lý một cách thống nhất trên cùng hệ
thống. Mọi truy xuất đều thể hiện trực quan hơn trên bản đồ số thay cho những
dòng văn bản đơn thuần. Chính vì thế GIS ngày một trở nên quen thuộc hơn cho
người dùng, nó được ứng dụng trong nhiều lĩnh việc từ đơn giản đến phức tạp và
chi phí đòi hỏi đầu tư ngày một thấp hơn. Có thề nói rằng GIS ngày một tự khả
định tầm quan trọng, được các nước phát triển xem như một mũi nhọn trong lĩnh
công nghệ thông tin và được đưa vào chương trình giảng dạy.
- 13 -
Viết thuê luận văn thạc sĩ
[email protected] - 0972.162.399
K
H
TN
H
Đ
–
CHƯƠNG 2
dạng số (kĩ thuật số) trên 30 năm nay.
Xử lý thông tin địa lý “geoprocessing” : là bất kì việc tính toán dạng kĩ
thuật số nào sử dụng geodata, lập mô hình, phiên dịch và sử dụng thông tin Trái
H
Đất gồm hệ thống thông tin địa lý (GI), hệ thống thông tin đất đai (LIS), việc xử lý
Đ
ảnh và tạo ảnh Trái đất, việc chứa geodata trong tất cả các loại cơ sở dữ liệu,
những phương thức khảo sát dạng kĩ thuật số, sự định hướng, khí tượng học, địa
–
chấn học,v v..
:
C
N
TT
“Interoperable geoprocessing” chỉ khả năng của một hệ thống kĩ thuật số để
- Tùy thích trao đổi tất cả các loại thông tin không gian về Trái đất
,về các đối tượng và hiện tượng ở trên ,bên trên và dưới bề mặt Trái đất .
- Chạy các phần mềm có khả năng thao tác các thông tin như vậy
K
H
TN
- Một mô hình chung để thực hiện những truy nhập, quản lý, thao
tác, trình bày, và chia sẻ geodata giữa những cộng đồng thông tin .
- Một bộ khung để sử dụng mô hình Open Geodata và mô hình dich
vụ Open GIS để giải quyết vấn đề khả năng không hoạt đông kết hợp không chỉ về
mặt kĩ thuật mà cả về mặt tổ chức.
Các nhà phát triển xây dựng những hệ thống có giao diện thích ứng
H
OpenGIS Specification sẽ tạo ra những phần mềm trung (middleware), phần mềm
Đ
bộ phận (componentware) và những ứng dụng có thể kiểm soát một phạm vi rộng
các kiểu geodata và các hàm geoprocessing. Người sử dụng các hệ thống này có
–
thể chia sẻ một không gian dữ liệu tiềm năng rộng lớn qua mạng, dù dữ liệu được
C
N
TT
• Sửa đổi những ứng dụng theo nhu cầu người dùng cụ thể, tích hợp phi
không gian và không gian.
• Chọn một môi trường phát triển.
• Cung cấp những ứng dụng trên những nền tảng đa dạng.
K
H
TN
• Sử dụng lại mã geoprocessing
Nhà quản lý thông tin linh hoạt hơn đối với:
• Truy cập và / hoặc phân phối geodata
• Cung cấp những khả năng geoprocessing tới những khách hàng
• Tích hợp Dữ liệu địa lý và sự xử lý vào một kiến trúc tính toán liên hợp
• Chọn những nền thích hợp - kiểu máy tính cá nhân, kiểu máy chủ, và kiểu
H
nền tính toán phân tán ( CORBA, OLE / COM, DCE, ….)
Đ
• Phù hợp với người dùng với những công cụ geoprocessing đúng (và được
địng cỡ đúng)
–
dụng những phương pháp lập trình truyền thông hay / và trên cơ sở đối
tượng.
- 17 -
Viết thuê luận văn thạc sĩ
[email protected] - 0972.162.399
2.2.2.2. Những dịch vụ OpenGIS ( OpenGIS Services ): tập hợp
những dịch vụ được cần để :
- Truy nhập và xử lý những kiểu định nghĩa đồ họa địa lý trong Mô
hình Geodata Mở.
K
H
TN
- Cung cấp những khả năng để chia sẻ geodata bên trong những cộng
đồng người dùng mà sử dụng một tập hợp chung những định nghĩa đặc tính
địa lý và biên dịch giữa những cộng đồng khác nhau những người sử dụng
những tập hợp định nghĩa đặc tính địa lý khác nhau.
2.2.2.3. Một mô hình những cộng đồng thông tin (Information
OpenGIS trong một sơ đồ để thiết lập :
H
Communities Model ) : Dùng Mô hình Geodata Mở và những dịch vụ
đó ngành công nghiệp phần mềm có thể xây dựng những thành phần phần mềm và
ứng dụng geoprocessing có tính :
Interoperable (Hoạt động liên hợp)- OpenGIS Specification cung cấp
những giao diện chuẩn đối với geodata và những dịch vụ geoprocessing. Những
giao diện này hỗ trợ trong những hệ thống độc lập và các mạng) : sự truy cập
- 18 -
Viết thuê luận văn thạc sĩ
[email protected] - 0972.162.399
geodata, những thao tác geoprocessing khách/chủ phân tán, thao tác geoprocessing
ngang hàng phân tán.
Supportive of Information Communities (Sự khuyến khích của những
cộng đồng thông tin ) - OpenGIS Specification tối ưu hóa việc chia sẻ dữ liệu bên
K
H
TN
trong một cộng đồng những người dùng và những nhà sản xuất chia sẻ một từ điển
đặc tính địa lý chung và giữa những tập hợp những người dùng và những nhà sản
xuất mà những từ điển đặc tính địa lý của họ không trùng.
Ubiquitous (Thường gặp) - OpenGIS Specification cung cấp những
phương tiện cho tất cả các ứng dụng công nghệ thông tin để sẵn sàng khai thác
những dịch vụ OpenGIS qua những giao diện và những giao thức chuẩn.
H
chung và những tài nguyên dữ liệu dùng chung. Công nghệ OpenGIS có thể dễ
dàng được kết hợp với công nghệ thông tin khác.
Scalable (Biến đổi được) – Phần mềm trên nền OpenGIS Specification th-
ường gồm có những thành phần phần mềm geoprocessing "cắm vµ chạy" mà có
thể được cấu hình cho bất kì ứng dụng geoprocessing nào hoặc môi trường tính
toán chuẩn, bất chấp kích thước cơ sở dữ liệu.
- 19 -
Viết thuê luận văn thạc sĩ
[email protected] - 0972.162.399
Extensible (Dể mở rộng) - OpenGIS Specification có thể đồng hóa những
phần mềm geoprocessing và kiểu geodata mới, và có thể điều tiết những công
nghệ mới mà OpenGIS Specification phụ thuộc trên đó , như những nền tính toán
phân tán, khi chúng trở thành sẵn có.
K
H
TN
Compatible (Tương thích) - OpenGIS Specification giữ gìn sự đầu tư của
những người dùng trong dữ liệu và phần mềm thừa kế bởi việc cung cấp những
phương tiện để hoà nhập liền khối, trong một kiểu cách trong suốt đối với người
dùng, phần mềm geoprocessing và geodata hiện có cùng công nghệ thông tin liên
O
A
Management Group(OMG), Object Linking and Embedding/Common Object
Model (OLE/COM) của Microsoft; Distributed Computing Environment (DCE)
của Open Software Foundation (OSF); Java của SunSoft và những nhóm khác.
OpenGIS Abstract Specification : Bộ phận của OpenGIS
Specification được tạo ra bởi Ủy ban kỹ thuật OGC để cung cấp sự mô tả ở mức
cao tính năng hoạt động được cung cấp bên trong OpenGIS Implementation
Specification. Mục đích của Abstract Specification là tạo ra và lập tài liệu một mô
hình khái niệm đủ để cho phép tạo ra Implementation Specification.
- 20 -
Viết thuê luận văn thạc sĩ
[email protected] - 0972.162.399
OpenGIS Implementation Specification : Những Implementation
Specification là những đặc tả nền tảng công nghệ rõ ràng cho sự cài đặt những
giao diện lập trình ứng dụng phần mềm chuẩn công nghiệp. Đó là những đặc tả
phần mềm chi tiết để cài đặt các bộ phận của OpenGIS Abstract Specification trên
K
H
TN
diện, hành vi, giới hạn,..Các lược đồ, phân tích trường hợp sử dụng (use-case
analysis), các mô hình từ ngữ hay đồ họa có cấu trúc được sử dụng để giúp cho
K
H
O
A
việc hiểu rõ những thông điệp.
- Mô hình thứ hai, cốt lõi của Abstract Specification, là Mô hình trừu
tượng (Abstract Model ) định nghĩa hệ thống phần mềm cuối cùng theo một lối cài
đặt trung lập. Abstract Model là sự mô tả phần mềm cần phải làm việc ra sao. Mô
hình trừu tượng đại diện một thỏa hiệp giữa các mô hình của những môi trường cài
đặt dự định nhắm tới. Các mô hình từ ngữ hay đồ họa có cấu trúc cũng được
khuyến khích sử dụng cho việc giải thích các sơ đồ khái niệm. Nó xác định các
lớp, lớp con được quan tâm, định danh và mô tả mối quan hệ giữa chúng, và mô tả
trừu tượng các giao diện được cài đặt trong phần mềm.
- 21 -
Viết thuê luận văn thạc sĩ
[email protected] - 0972.162.399
2.3.1. The OpenGIS Essential Model :
TT
bản đồ và GIS (Hệ thống thông tin địa lý), trong đó chúng ta lựa chọn
các thứ cụ thể trong thế giới khái niệm để biểu diễn theo một cách có
tính chất tượng trưng và trừu tượng trong những bản đồ và geodata.
Dimensional World (Thế giới có kích thước).
Đây là thế giới
Geospatial sau khi nó đã được đo đạc để có sự chính xác về vị trí và
hình học.
K
H
O
A
Project World (Thế giới đề án). Là một mảnh được chọn của thế giới
geospatial hữu hướng – cho ví dụ, những lớp thuộc chủ đề nhất định bên
trong một GIS – mà được lập cấu trúc ngữ nghĩa và nói cách khác cho
một mục đích, nghề nghiệp, qui định, hoặc miền công nghiệp đặc thù.
OpenGIS Points (Điểm OpenGIS). Làm sao những điểm được định
nghĩa, tổng quát và cho một Project World đặc biệt, theo một cách mà
tất cả các hệ thống phần mềm có thể liên quan đến.
- 22 -
A
C
N
TT
–
Đ
tính năng OpenGIS.
Hình 2.1: 9 lớp khái niệm
Trong 9 cấp độ trên , cấp độ Project world là quan trọng nhất cho mục đích
của OpenGIS Abstract Specification. Mô tả của Project World là đặc biệt quan
trọng vì nó giới thiệu khái niệm của Geospatial Information Community mà sự
- 23 -
Viết thuê luận văn thạc sĩ
[email protected] - 0972.162.399
chia sẻ những thông tin không gian địa lý diễn ra trong đó ỏ một mức tự nhiên,
không khó khăn gì vế mặt ngữ nghĩa .
2.3.1.1. Các khái niệm :
Open Geodata Model : Mỗi hệ thống geoprocessing đều có một mô
Features and Feature Collections ( Tính năng và Tập hợp tính năng
): Là cấp độ cuối cùng của Essential Model.
9 Một Feature Collection là đơn vị cơ bản, nguyên tử của quan hệ
geospatial trong một môi trường hệ thống máy tính nối mạng, là
K
H
O
A
đơn vị thương mại trong một giao dịch chia sẻ thông tin
geospatial, khoản mục geospatial nhỏ nhất mà được trao đổi qua
sự quản lý của quan hệ geospatial, là đối tượng nguyên thuỷ của
thao tác và sự khai thác bên trong một môi trường xử lý phần
mềm geospatial. Một Feature Collections có thể chứa một
Feature đơn lẻ hay nhiều Feature .
9 Feature (đặc tính,tính năng) là đơn vị cơ bản của thông tin
geospatial số, có thể được định nghĩa đệ quy, như vậy có thể là
sự biến đổi đáng kể trong hạt các đặc tính. Ví dụ : phụ thuộc vào
- 24 -
Viết thuê luận văn thạc sĩ
[email protected] - 0972.162.399
ứng dụng hoặc sự quan tâm của người thu thập thông tin, bất kỳ
C
N
TT
không đầy đủ ý nghĩa trong một ngữ cảnh geoprocessing trừ phi
chúng được biểu diễn dướí dạng một mô hình cố định chúng vào
thời gian và đặt chúng trong mối liên hệ với bề mặt của Trái đất.
Những hệ thống tham chiếu không gian định nghĩa làm sao những
tọa độ được thể hiện bên trong dạng hình học của một đặc tính.
Features and Coverages (Những đặc tính và phạm vi che phủ):
K
H
O
A
Những yếu tố địa lý chia thành hai phạm trù rộng, là những thực thể
và hiện tượng :
- Những thực thể là những đối tượng rời có thể nhện ra được,
có những ranh giới được xác định tương đối rõ hoặc phạm vi không gian. Ví dụ :
những tòa nhà, dòng sông, ...
- Hiện tượng thay đổi qua không gian và không có phạm vi
cụ thể. Ví dụ : nhiệt độ, thành phần đất …. Một giá trị hoặc sự mô tả của một hiện
tượng chỉ có ý nghĩa tại một điểm cụ thể trong không gian ( và có thể cả thời gian
). Ví dụ : Hiện tượng được gọi là nhiẹt độ chỉ có giá trị cụ thể tại vị trí xác định.
Copyright: Tài liệu đại học ©