LỜI CẢM ƠN
Trước hết, xin chân thành cảm ơn đến :
Ban Giám Hiệu Trường Đại Học Sư Phạm TP. Hồ Chí Minh. Trong suốt 4
năm học tại trường, Ban Giám Hiệu đã tạo mọi điều kiện tốt để em có thể
học tập, trau dồi thêm kiến thức cho mình.
Ban chủ nhiệm Khoa Toán – Tin Học.
Toàn thể quí thầy cô thuộc tổ bộ môn Tin, đã tận tình giảng dạy những kiến
thức chuyên môn cho em. Đó là những kiến thức nền tảng giúp em vững
bước trên con đường học tập và nghiên cứu sâu hơn về chuyên môn sau này.
Xin chân thành cảm ơn đến : Thầy Ngô Quốc Việt, người đã trực tiếp cung cấp đề
tài và hướng dẫn thực hiện đề tài này.
Và cuối cùng, xin cảm ơn đến những người bạn của tôi. Những người đã trao đổi,
đóng góp, phê bình và động viên tôi trong thời gian thực hiện đề tài này.
1
MỤC LỤC
Lời cảm ơn......................................................................................................1
Mục lục............................................................................................................2
Danh mục các hình vẽ.....................................................................................5
NỘI DUNG CỦA ĐỒ ÁN :
Chương 1 : Giới thiệu về cơ sở dữ liệu không gian..................................7
1.1 Hệ quản trị cơ sở dữ liệu...........................................................................7
1.2 Những thuật ngữ dùng trong các ứng dụng cơ sở dữ liệu không gian.....8
1.2.1 Khái niệm về hệ thống thông tin địa lý..............................................8
1.2.2 Các thuật ngữ trong các ứng dụng GIS..............................................9
1.2.2.1 Theme............................................................................................9
1.2.2.2 Map................................................................................................9
1.2.2.3 Đối tượng địa lý..........................................................................10
1.3 Các phép toán trên dữ liệu địa lý không gian.........................................10
1.3.1 Phép chiếu theme..............................................................................10
1.3.2 Phép chọn theme...............................................................................11
1.3.3 Phép hợp theme.................................................................................11
1.3.4 Phép phủ theme.................................................................................13
1.3.5 Phép lựa chọn hình học.....................................................................14
1.3.6 Phép kết hợp......................................................................................14
1.4 Hệ quản trị cơ sở dữ liệu hỗ trợ cho cơ sở dữ liệu địa lý không gian....15
1.5 Các yêu cầu đối với hệ quản trị cơ sở dữ liệu không gian.....................16
Chương 2 : Biểu diễn đối tượng không gian...........................................17
2.1 Mô hình không gian địa lý......................................................................17
2.1.1 Mô hình thực thể...............................................................................17
2.1.2 Mô hình không gian..........................................................................18
2.2 Các phương thức biểu diễn.....................................................................18
2.2.1 Phương thức Tessellation..................................................................18
2.2.2 Phương thức Vector...........................................................................20
2
2.2.3 Phương thức biểu diễn Nửa-Phẳng...................................................21
2.3 Biểu diễn hình học của tập các đối tượng..............................................21
2.3.1 Mô hình Mạng...................................................................................21
2.3.2 Mô hình TôPô...................................................................................23
Chương 3 : Mô hình Lôgic và ngôn ngữ truy vấn..................................25
3.1 Các lược đồ tham chiếu..........................................................................25
3.1.1 Các đơn vị quản lý............................................................................25
3.1.2 Mạng lưới giao thông giữa các thành phố........................................25
3.1.3 Land-Use...........................................................................................26
3.2 Các câu truy vấn mẫu..............................................................................26
3.3 Các kiểu dữ liệu không gian trừu tượng.................................................27
3.3.1 Mở rộng mô hình với các kiểu dữ liệu không gian trừu tượng........27
3.3.2 Xây dựng các kiểu dữ liệu không gian trừu tượng...........................29
3.4 Mô hình quan hệ mở rộng với ADT.......................................................31
3.4.1 Biểu diễn của lược đồ tham chiếu....................................................31
3.4.2 Truy vấn............................................................................................34
3.5 Mô hình hướng đối tượng.......................................................................38
3.5.1 Các khái niệm cơ bản trong hệ cơ sở dữ liệu hướng đối tượng.......38
3.5.2 Biểu diễn của lược đồ tham chiếu....................................................39
3.5.3 Các lớp không gian...........................................................................41
Chương 4 : Mô hình dữ liệu ràng buộc...................................................43
4.1 Mô hình dữ liêu không gian với các ràng buộc......................................43
4.2 Mô hình dữ liệu ràng buộc tuyến tính....................................................48
4.2.1 Biểu diễn dữ liệu...............................................................................48
4.2.2 Truy vấn bậc nhất..............................................................................48
Chương 5 : Các thuật toán cho đối tượng hình học...............................51
5.1 Các khái niệm cơ bản..............................................................................51
5.1.1 Thuật toán..........................................................................................51
5.1.2 Phân tích thuật toán...........................................................................52
3
5.2 Các chiến lược thuật toán hữu hiệu........................................................53
5.2.1 Thuật toán gia tăng : Ví dụ bao lồi...................................................53
5.2.2 Chiến lược chia để trị : Ví dụ nửa mặt phẳng giao nhau.................56
5.2.3 Phương thức đường quét : Ví dụ hình chữ nhật giao nhau..............58
5.3 Phân chia đa giác.....................................................................................60
5.3.1 Hình thang hóa một đa giác đơn.......................................................60
5.3.2 Tam giác hóa một đa giác đơn..........................................................61
5.4 Các thuật toán cho cơ sở dữ liệu không gian.........................................64
5.4.1 Thuật toán kiểm tra điểm trong đa giác............................................64
5.4.2 Thuật toán kiểm tra đoạn thẳng giao nhau.......................................65
5.4.3 Thuật toán kiểm tra đa giác giao nhau..............................................67
5.4.4 Thuật toán Windowing......................................................................67
5.4.5 Thuật toán Clipping..........................................................................68
Tài liệu tham khảo.........................................................................................71
4
DANH MỤC CÁC HÌNH VẼ
Hình 1 : Sự tương tác của hệ QTCSDL với người dùng và với CSDL
Hình 2 : Một bản đồ Việt Nam
Hình 3 : Minh họa phép chiếu
Hình 4 : Minh họa phép chọn
Hình 5 : Minh họa phép hợp theme : (a) Những quốc gia có dân số trên 10 triệu, (b)
Những quốc gia có dân số ít hơn 10 triệu, (c) Hợp của hai theme (a) và (b).
Hình 6 : Phủ theme : (a) theme những quốc gia phía Tây Châu Âu, (b) Những ngôn
ngữ được dùng ở Tây Âu.
Hình 7 : Window
Hình 8 : Clipping
Hình 9 : Merger
Hình 10 : Biểu diễn quan hệ giữa các quốc gia
Hình 11 : (a) Đường gấp khúc khép kín; (b) Đường gấp khúc không đơn; (c) Đường
gấp khúc không đơn điệu.
Hình 12 : (a) Đa giác đơn; (b) Đa giác không đơn; (c) Đa giác lồi; (d) Đa giác đơn
điệu.
Hình 13 : Tessellation có quy tắc : (a) chia theo lưới vuông, (b) chia theo lục giác
đều.
Hình 14 : Tessellation không có quy tắc : (a) các vùng địa chính, (b) biểu đồ
Voronoi.
Hình 15 : Biểu diễn đa giác P bằng các pixel.
Hình 16 : Biểu diễn đa giác bằng phương thức vector.
Hình 17 : Đa giác P được biểu diễn bằng các nửa mặt phẳng giới hạn bởi các đường
L1, L2, L3.
Hình 18 : Minh họa mô hình mạng.
Hình 19 : Biểu diễn của các đa giác trong mô hình Tôpô.
Hình 20 : Các đơn vị quản lí.
5
Hình 21 : Minh họa lược đồ 2.
Hình 22 : (a) Điểm, (b) Đường gấp khúc, (c) Đường gấp jgúc phức tạp, (d) Đa giác,
(e) tập đa giác, (f) hỗn hợp.
Hình 23 : (a) Hai đa giác lồi, (b) Hai đa giác không lồi, (c) Đường và đa giác, (d)
Đường và đa giác có một đoạn chung, (e) Hai đa giác kề nhau.
Hình 24 : Mô hình dữ liệu không gian của các tập điểm trong R 2 : (a) Tập điểm xác
định, (b) Tập điểm không xác định.
Hình 25 : Biểu diễn đường gấp khúc trong cơ sở dữ liệu ràng buộc.
Hình 26: Đa giác không lồi trong cơ sở dữ liệu ràng buộc.
Hình 27 : Giao của Road và Spat.
Hình 28 : Ba mức trong sơ đồ.
Hình 29 : Kết quả giao của Road và Spat.
Hình 30 : Biểu diễn kết quả của Query 2.
Hình 31 : Biểu diễn kết quả của Query 3.
Hình 32 : (a) Các tiếp tuyến từ p i , (b) Bao lồi mới.
Hình 33 : Minh họa thuật toán gia tăng bao lồi.
Hình 34 : Minh họa thuật toán nửa phẳng giao nhau.
Hình 35 : Minh họa thuật toán dùng đường quét.
Hình 36 : Hình thang hóa một đa giác đơn.
Hình 37 : Sự tách hình thang.
Hình 38 : Chia đa giác đơn thành các thành phần đơn điệu.
Hình 40 : Minh họa thuật toán điểm trong đa giác.
Hình 41 : Thuật toán đường quét.
Hình 42 : Clipping một cạnh dựa vào nửa phẳng H.
Hình 43 : Minh họa xén đa giác qua 4 bước.
6
Chương 1
GIỚI THIỆU VỀ CƠ SỞ DỮ LIỆU KHÔNG GIAN
1.1 Hệ quản trị cơ sở dữ liệu
Một cơ sở dữ liệu là một tập hợp lớn các dữ liệu có quan hệ với nhau, chứa
thông tin của một cơ quan, tổ chức nào đó được lưu trữ bên trong một môi
trường máy tính để đáp ứng nhu cầu khai thác thông tin của người sử dụng
với các mục đích khác nhau.
Cơ sở dữ liệu quan hệ là cơ sở dữ liệu có cấu trúc bao gồm các bảng dữ liệu,
mỗi bảng dữ liệu có quan hệ với bảng khác theo một trong ba loại mối quan
hệ (quan hệ một - một, quan hệ một - nhiều, quan hệ nhiều - nhiều). Chúng
có thể có quan hệ trực tiếp với nhau, cũng có thể có quan hệ gián tiếp thông
qua bảng khác. Những bảng này được định nghĩa như một đối tượng trong
cơ sở dữ liệu và chúng có quan hệ với nhau.
Một hệ quản trị cơ sở dữ liệu là một phần mềm quản lí cấu trúc cơ sở dữ liệu
và điều khiển việc xử lý dữ liệu. Tổng quát hơn, một hệ quản trị cơ sở dữ
liệu là phần mềm bao gồm một quá trình xử lý :
Định nghĩa một cơ sở dữ liệu
Xây dựng cơ sở dữ liệu
Thao tác cơ sở dữ liệu
Truy vấn dữ liệu để lấy dữ liệu cần thiết
Cập nhật cơ sở dữ liệu
Mỗi hệ quản trị cơ sở dữ liệu gồm nhiều thành phần, mỗi thành phần có chức
năng cụ thể, trong đó hai thành phần chình là bộ xử lý truy vấn và bộ quản lý
dữ liệu. Hình sau là sơ đồ đơn giản cho ta biết sự tương tác của hệ quản trị
cơ sở dữ liệu với người dùng và với cơ sở dữ liệu.
7
Trình ứng dụng
Truy vấn
Hệ quản trị
CSDL
Bộ xử lí
truy vấn
Bộ quản lí
dữ liệu
Bộ quản lí
tệp (hệ điều
hành)
CSDL
Hình 1 : Sự tương tác của hệ QTCSDL với người dùng và với CSDL
1.2 Những thuật ngữ dùng trong các ứng dụng cơ sở dữ liệu không gian
1.2.1 Khái niệm về hệ thống thông tin địa lý
Hệ thống thông tin địa lý (Geographic Information System - gọi tắt là GIS)
là một nhánh của công nghệ thông tin. Có nhiều cách khác nhau khi định
nghĩa GIS. Xét dưới góc độ hệ thống, GIS có thể được hiểu như một hệ
thống gồm các thành phần : con người, phần cứng, phần mềm, cơ sở dữ liệu
và quy trình kiến thức chuyên gia, nơi tập hợp các quy định, quy phạm, tiêu
8
chuẩn, định hướng, chủ trương ứng dụng của nhà quản lý, các kiến thức
chuyên ngành và các kiến thức về công nghệ thông tin.
1.2.2 Các thuật ngữ trong các ứng dụng GIS
1.2.2.1 Theme (chủ đề)
Trong GIS, những thông tin địa lý không gian tương ứng với một chủ
đề riêng biệt thì được hình thành trong một theme. Một theme giống như
một mối quan hệ được định nghĩa trong mô hình quan hệ, nó gồm một lược
đồ với những mô tả. Những con sông, những thành phố, những quốc gia,…
là những ví dụ về theme.
1.2.2.2 Map (bản đồ)
Khi một theme được biểu thị trên giấy hoặc trên màn hình máy tính
thì những gì mà chúng ta thấy gọi là một bản đồ (map) với những màu sắc, tỉ
lệ, những sự kiện,…Bản đồ địa hình, bản đồ xe lửa, bản đồ thời tiết là những
mẫu bản đồ mà chúng ta hay thấy.
Hình 2 : Một bản đồ Việt Nam
9
1.2.2.2 Đối tượng địa lý (Geographic Objects)
Một đối tượng địa lý là một thực thể ở thế giới thực bao gồm hai
thành phần :
Thành phần mô tả : Đối tượng được mô tả bằng việc thu thập
các thuộc tính về nó. Chẳng hạn, tên và dân số của một thành
phố là những mô tả về nó. Những thuộc tính của đối tượng
được xem là thành phần mô tả chính.
Thành phần không gian : Được hình thành từ hai yếu tố hình
học và địa hình. Ví dụ một thành phố được biểu diễn như một
đa giác trong không gian hai chiều.
1.3 Các phép toán trên dữ liệu địa lý không gian
Cho hai theme : (1) Countries, với các thuộc tính là tên, thủ đô, dân số và một
thành phần không gian là geo. (2) Languages, với thuộc tính là ngôn ngữ và
một thuộc tính không gian là geo. Hai theme được mô tả bằng các lược đồ sau :
Countries (tên, thủ đô, dân số, geo : vùng)
Languages (language, geo : vùng)
Ta có các phép toán sau (lấy ví dụ từ hai theme trên) :
1.3.1 Phép chiếu theme (Theme Projection)
Phép chiếu theme, kí hiệu theme x {A1,…,An} theme, trong đó {A1,
…,An} là tập con các thuộc tính của theme, cho kết quả là một theme với
những mô tả được hình thành từ tập thuộc tính {A1,…,An} và thành phần
không gian đã được chuyển đổi.
Hình 3 : Minh họa phép chiếu
10
Gọi geo là thành phần không gian và T là kí hiệu của lược đồ theme, thì
phép chiếu theme được kí hiệu là :
A1... An , geo
(T)
1.3.2 Phép chọn theme (Theme Selection)
Phép chọn theme (theme x p A theme), trong đó p A là một thuộc tính
i
i
trên tập thuộc tính mô tả của theme. Phép chọn theme kí hiệu là
p Ai
(T).
Hình 4 : Minh họa phép chọn
1.3.3 Phép hợp theme (Theme Union)
Hợp của hai theme (theme x theme theme) là hợp của các đối tượng địa
lý có lược đồ quan hệ giống nhau. T 1 và T 2 là kí hiệu của hai theme thì
hợp của chúng là T 1 T 2 .
11
Hình 5 : Minh họa phép hợp theme : (a) Những quốc gia có dân số trên 10 triệu, (b)
Những quốc gia có dân số ít hơn 10 triệu, (c) Hợp của hai theme (a) và (b).
12
1.3.4 Phép phủ theme (Theme Overlay)
Phủ của 2 theme (theme x theme theme) là phép toán phổ biến trong các
ứng dụng GIS. Phép toán này cho một theme mới từ việc trộn các theme cũ,
đối tượng địa lý mới được tạo ra. Mô tả về đối tượng mới được kết hợp từ
các mô tả của 2 theme ban đầu. Kí hiệu G là phép phủ không gian, T 1 và
T 2 là hai theme, thì phép phủ theme được kí hiệu là T 1 G T 2 .
Hình 6 : Phủ theme : (a) theme những quốc gia phía Tây Châu Âu, (b)
Những ngôn ngữ được dùng ở Tây Âu.
13
1.3.5 Phép lựa chọn hình học (Geometric Selection)
Dùng Window query : Cho theme kết quả là vùng được lấy từ Window và
các vùng thuộc vùng được chọn.
Hình 7 : Window
Dùng Clipping : Cho theme kết quả chỉ trong vùng Window.
Hình 8 : Clipping
1.3.6
Phép kết hợp (Merger)
Kí hiệu (theme x condition theme). Là sự kết hợp từ các theme giống
nhau với một điều kiện được cho bởi người dùng để tạo ra một theme mới.
Hình 9 : Merger
14
1.4 Hệ quản trị cơ sở dữ liệu hỗ trợ cho cơ sở dữ liệu địa lý không gian
Hệ quản trị cơ sở dữ liệu quan hệ :
Những đặc trưng chính :
Các theme được trình bày bằng các bảng quan hệ. Một đối tượng địa
lí là một bộ (một dòng) của quan hệ, mỗi cột là một thuộc tính.
Các thuộc tính có kiểu chữ số (chuỗi và số).
Có ngôn ngữ truy vấn SQL.
Xét theme Country với các thuộc tính được cho trong bảng quan hệ sau cùng
với các bảng liên quan với Country :
Country
Name
Capital
Populatio
Id-boundary
Germany
Berlin
n
78.5
B1
France
Paris
58
B2
…
…
…
…
Boundary
Id-boundary Id-contour
B1
C1
Contour
B2
C2
B2
C3
B3
C4
B3
C5
…
…
Id-countour
C1
Point-num
2
Id-point
P1
C1
1
P2
C1
3
P3
C1
…
…
Id-point
P1
X
452
Y
1000
C2
1
P4
P2
365
875
C2
2
P5
P3
386
985
C2
…
…
P4
296
825
…
…
…
P5
589
189
…
…
…
Point
15
Hình 10 : Biểu diễn quan hệ giữa các quốc gia
Để truy vấn câu “Return the contours of France” sử dụng ngôn ngữ SQL, ta làm
như sau :
Select
Boundary.id-contour,x,y
From
Country,Boundary,Contour,Point
Where
Name = ’France’
And
Country.id-boundary = Boundary.id-boundary
And
Boundary.id-contour = Contour.id-contour
And
Contour.id-point = Point.id-contour
Order by
Boundary.id-contour,point-num
1.5 Các yêu cầu đối với hệ quản trị cơ sở dữ liệu không gian
Dữ liệu biểu diễn dưới dạng logic phải được chuyển sang dạng hình học
để tạo ra sự đơn giản và thân thuộc đối với người dùng.
Ngôn ngữ truy vấn phải chứa đựng những phương thức mới, chứa đựng
nhiều phép toán phù hợp với thao tác đối tượng hình học.
Có sự trình bày vật lý hiệu quả dữ liệu không gian.
Việc truy cập dữ liệu hiệu quả là cần thiết đối với cơ sở dữ liệu không
gian cũng như các cơ sở dữ liệu cổ điển. B-cây không còn thích hợp cho
việc truy cập dữ liệu không gian. Do đó chúng ta cần những cấu trúc dữ
liệu mới để chỉ số hóa cho cơ sở dữ liệu không gian.
Một số giải thuật không thể sử dụng trong cơ sở dữ liệu địa lý không
gian, như giải thuật nối. Vì vậy, chúng ta cần có một số giải thuật mới.
16
Chương 2
BIỂU DIỄN ĐỐI TƯỢNG KHÔNG GIAN
2.1 Mô hình không gian địa lý
2.1.1 Mô hình thực thể (Entity-Based Model)
Khái niệm thực thể :
Khái niệm thực thể là khái niệm trừu tượng, không có một định nghĩa hình
thức cho nó. Ta coi thực thể là một sự vật tồn tại và phân biệt được. Ví dụ
con người, xe đạp, các đối tượng địa lý,… là những thực thể. Thuộc tính
phân biệt được là thuộc tính cơ bản trong khái niệm thực thể.
Đối tượng của mô hình thực thể :
Điểm : Điểm được sử dụng để biểu diễn vị trí của thực thể mà không
phụ thuộc vào hình dạng của nó. Ví dụ như thành phố, nhà thờ,… là
những thực thể có thể được xem như là một điểm trên bản đồ.
Đối tượng tuyến tính : Loại hình học cơ bản mà ta xét là đường gấp
khúc (polyline). Một đường gấp khúc là một tập hợp các đoạn thẳng
nối với nhau, mỗi điểm nối là đỉnh chung của hai đoạn, trừ hai điểm
ngoài cùng là chỉ thuộc về một đoạn. ta có các loại đường gấp khúc
sau :
Đường gấp khúc khép kín là đường gấp khúc có hai điểm ngoài cùng
trùng nhau.
Đường gấp khúc đơn là đường gấp khúc không có hai đoạn không
liên tiếp giao nhau.
Đường gấp khúc là đơn điệu đối với đường L nếu mỗi đường L’ trực
giao với L gặp đường gấp khúc tại tối đa một điểm.
17
Hình 11 : (a) Đường gấp khúc khép kín; (b) Đường gấp khúc không
đơn; (c) Đường gấp khúc không đơn điệu.
Đối tượng bề mặt (surfacic objects) : Dùng để biểu diễn thực thể có
diện tích lớn. Đa giác là loại hình chính ta nghiên cứu. Một đa giác là
một miền được bao bởi một đường gấp khúc khép kín. Ta có các loại
đa giác sau :
Đa giác là đơn nếu đường biên của nó là một đường gấp khúc đơn.
Đa giác P là đa giác lồi nếu hai điểm bất kì A, B thuộc P thì đoạn AB
cũng nằm trong P.
Đa giác đơn điệu là giác đơn mà đường biên của nó có thể tách ra
thành hai đường gấp khúc đơn điệu. Tính đơn điệu của đa giác thường
đối với trục tọa độ.
Hình 12 : (a) Đa giác đơn; (b) Đa giác không đơn; (c) Đa giác lồi; (d)
Đa giác đơn điệu.
2.1.2 Mô hình không gian (Space-Based Model)
Trong mô hình này, mỗi điểm trong không gian được gắn với một hoặc nhiều
giá trị thuộc tính, được định nghĩa như là một hàm số liên tục với x và y. Ví
dụ, độ cao so với mực nước biển là một hàm định nghĩa trên x và y, mà kết
quả là giá trị của biến h đối với bất kì điểm nào trong không gian hai chiều.
2.2 Các phương thức biểu diễn
2.2.1 Phương thức Tessellation
Phương thức này phân chia một mặt thành các phần nhỏ. Có hai cách chia
trong phương thức này :
18
Phương thức Tessellation có quy tắc : Các đơn vị được chia (các phần
nhỏ) là các đa giác giống nhau và bằng nhau.
Hình 13 : Tessellation có quy tắc : (a) chia theo lưới vuông, (b) chia theo
lục giác đều.
Phương thức Tessellation không có quy tắc : các đơn vị được chia là
các đa giác có kích thước khác nhau.
Hình 14 : Tessellation không có quy tắc : (a) các vùng địa chính, (b) biểu
đồ Voronoi.
Biểu diễn dữ liệu trong mô hình thực thể bằng phương thức Tessellation
Một đối tượng không gian trong không gian hai chiều được biểu diễn bằng
một tập các pixel trên máy tính, trong đó một điểm của đối tượng được xem
như là một pixel. Vị trí của điểm là một cặp tọa độ nguyên. Trong phương
thức Tessellation, thay vì sử dụng cặp tọa độ (x,y), chúng ta thay mỗi đơn vị
được chia bằng một số nguyên. Một đường gấp khúc, một đa giác hoặc một
miền (region) được biểu diễn bởi một số pixel xác định.
Trong hình sau, đa giác P được biểu diễn bằng danh sách các pixel :
<5, 12, 13, 14, 17, 18, 19, 20, 21, 22, 26, 27, 28, 29, 30, 31, 35, 36, 37, 38>
19
Hình 15 : Biểu diễn đa giác P bằng các pixel.
2.2.2 Phương thức Vector
Trong phương thức vector, một điểm được biểu diễn bằng cặp tọa độ của nó.
Đối tượng tuyến tính và đối tượng bề mặt thì được biểu diễn bằng cấu trúc
của cách biểu diễn điểm như danh sách, tập hợp, mảng.
Biểu diễn dữ liệu trong mô hình thực thể bằng phương thức vector :
Đường gấp khúc được biểu diễn bằng một danh sách các điểm
, trong đó p i là đỉnh, cặp (p i ,p i 1 ) với i; tập hợp bằng {}. Ta có cấu trúc
biểu diễn của điểm, đường gấp khúc, đa giác và miền như sau :
Point : [x: real, y: real]
Polyline : < point >
Polygon : < point >
Region : { polygon }
Hình sau minh họa cách biểu diễn của một đa giác trong phương thức
vector, được mô tả bằng một danh sách thứ tự của các cặp tọa độ như sau
< [4,4], [6,1], [3,0], [0,2], [2,2] >
20