C U TRÚC D LI U RASTER VÀ VECTOR
Ữ Ệ
Ấ
1 C U TRÚC RASTER 1 ................................................................................................. Ấ 2 3 ................................................................................................ Ấ C U TRÚC VECTOR C u trúc Spaghetti 2.1 4 ............................................................................................... ấ 2.2 C u trúc Topology 5 .............................................................................................. ấ 6 C ĐI M C A C U TRÚC VECTOR VÀ RASTER ............................. U NH 3 Ủ Ư
ƯỢ
Ấ
Ể
Các đ i t ý khi đ c bi u di n trên máy tính đ c bi ố ượ ng đ a l ị ượ ể ễ ượ t đ n ế ế ở 2 d ng: ạ
c u trúc d li u raster và c u trúc d li u vector. ấ ữ ệ ữ ệ ấ
1 C U TRÚC RASTER
Ấ
Khái ni mệ
Mô hình raster bi u di n không gian nh là m t ma tr n s nguyên, m i giá tr s ư ậ ố ị ố ể ễ ộ ỗ
ủ ố nguyên đ i di n cho m t thu c tính, v trí c a s nguyên chính là v trí c a đ i ị ủ ố ệ ạ ộ ộ ị
ngượ t
Thí d : ụ
Hình 1: Mô hình d li u raster và vector ữ ệ
Hình 2: Mô hình d li u raster và vector ữ ệ
ng ng v i m t ô nào đó trong th i th c: m i pixel s t ỗ ẽ ươ ự ứ ớ ộ ế ế ớ Liên h v i th gi ệ ớ i th c. gi ự ớ
Trong c u trúc raster: ấ
ượ ế c bi u di n b ng nh ng pixel có cùng giá tr f(x,y) liên ti p ữ ể ễ ằ ị - Đ ng đ ườ nhau.
- Vùng đ c xác đ nh thành m t m ng g m nhi u pixel có cùng giá tr ồ ề ạ ộ ị ị ượ thu c tính f(x,y). ộ
Hình 3: C u trúc d li u raster
ữ ệ
ấ
C u trúc l u tr raster c b n: ữ ơ ả ư ấ
- C u trúc l u mã chi ti t (exhaustive enumeration) ư ấ ế
- C u trúc l u mã run length (run-length encoding). ư ấ
t c g n v i giá tr duy ư ể i đ ướ ượ ắ ớ ị ế , m i m t đi m l ộ c nén g n. Đ i v i c u trúc l u mã chi ti nh t, vì v y d li u không đ ượ ậ ữ ệ ố ớ ấ ấ ỗ ọ
ư ậ ấ ứ ữ ộ ị ữ ệ ả ư ộ ữ ầ ừ i ch a đ ng giá tr đó. u mã ch y dài C u trúc l có ý nghĩa nh là m t k thu t nén d li u n u raster ạ ư ế ộ ỹ ch a các nhóm đi m l riêng i có cùng m t giá tr . Khi đó thay vì ph i l u tr ể ướ i, c u trúc này l u tr theo t ng thành ph n có m t giá tr duy cho t ng đi m l ấ ướ ể ừ ị ng đi m l nh t và s l ể ố ượ ư ứ ự ướ ấ ị
t
Hình : Minh h a c u trúc mã chi ti ọ ấ
ế
Hình 4: Minh h a c u trúc mã run length
ọ ấ
2 C U TRÚC VECTOR
Ấ
Khái ni mệ
Các đ i t ng không gian khi bi u di n c t ố ượ ễ ở ấ c u trúc d li u vector đ ữ ệ ể ượ ổ ứ ch c
i d ng đi m (point), đ ng (line) và vùng (polygon) (xem hình 2 trang 2), và d ướ ạ ể ườ
đ ượ c bi u di n trên m t h th ng t a đ nào đó. Đ i v i các đ i t ọ ộ ệ ố ố ớ ố ượ ể ễ ộ ể ng bi u
di n trên m t ph ng, m i đ i t ỗ ố ượ ễ ặ ẳ ng đi m đ ể ượ c bi u di n b i m t c p t a đ ở ộ ặ ọ ể ễ ộ
(x, y); đ i t ng đ ng đ c xác đ nh b i m t chu i liên ti p các đi m (vertex), ố ượ ườ ượ ế ể ở ộ ỗ ị
đo n th ng đ ạ ẳ ượ ố ể c n i gi a các đi m (vertex) hay còn g i là c nh (segment), đi m ữ ể ạ ọ
ng g i là các nút (node); đ i t ng vùng b t đ u và đi m k t thúc c a m t đ ế ắ ầ ộ ườ ủ ể ố ượ ọ
đ c xác đ nh b i các đ ng khép kín. ượ ở ị ườ
Hình 5: Minh h a đ i t
ng đ
ng g m có các nút, đi m, c nh
ọ ố ượ
ườ
ồ
ể
ạ
c bi t đ n trong c u trúc d li u vector là c u trúc Hai lo i c u trúc đ ạ ấ ượ ế ế ữ ệ ấ ấ
Spaghetti và c u trúc Topology. C u trúc Spaghetti ra đ i tr c và đ ờ ướ ấ ấ ượ ử ụ c s d ng
cho đ n ngày nay m t s các ph n m m GIS nh : ph n m m Arcview GIS, ế ở ộ ố ư ề ề ầ ầ
ữ ệ ArcGIS, MapInfo,… C u trúc Topology ra đ i trên n n t ng c a mô hình d li u ề ả ủ ấ ờ
cung – nút (Arc - Node).
2.1
C u trúc Spaghetti
ấ
Trong c u trúc d li u Spaghetti, đ n v c s là các c p t a đ trên m t không ị ơ ở ặ ọ ữ ệ ấ ơ ộ ộ
gian đ a lý xác đ nh. Do đó, m i đ i t ỗ ố ượ ị ị ng đi m đ ể ượ ộ ặ ọ c xác đ nh b ng m t c p t a ằ ị
ng đ ng đ đ (x, y); m i đ i t ộ ỗ ố ượ ườ ượ ặ ọ c bi u di n b ng m t chu i nh ng c p t a ữ ể ễ ằ ộ ỗ
ng vùng đ đ (xộ i, yi); m i đ i t ỗ ố ượ ượ c bi u di n b ng m t chu i nh ng c p to ộ ữ ể ễ ằ ặ ỗ ạ
đ (xộ j, yj) v i đi m đ u và đi m cu i trùng nhau. ể ể ầ ớ ố
Thí d :ụ
Hình 6: Minh h a d li u Spaghetti
ọ ữ ệ
Đ c tr ng ư ặ V trí ị
Đi m Aể Đi m Bể Cung AB Vùng a Vùng b (xA, yA) (xB, yB) (xA, yA), (xB, yB) (xA, yA), (xa1, ya1), …, (xa5, ya5) , (xB, yB), (xA, yA) (xA, yA), (xb1, yb1), (xb2, yb2), (xb3, yb3) , (xB, yB), (xA, yA)
B ng 1: B ng mô t
đ c tr ng c a c u trúc Spaghetti
ả
ả
ả ặ
ủ ấ
ư
Đ c đi m: C u trúc Spaghetti không ghi nh n đ c tr ng k nhau c a hai vùng k ư ủ ề ể ậ ặ ặ ấ ề
nhau, nghĩa là t ạ i hai vùng k nhau s có hai c nh chung k nhau, c nh chung ạ ề ẽ ề ạ
thí d trên vùng a và vùng b có c a hai vùng k nhau là hai c nh đ c l p nhau. ủ ộ ậ ề ạ Ở ụ
chung c nh AB. ạ
2.2
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). C u trúc này ấ ượ ọ ấ ấ
đ c xây d ng trên mô hình cung – nút, trong đó cung là ph n t c s . Vi c xác ượ ầ ử ơ ở ự ệ
không gian d a trên các đ nh nghĩa sau: đ nh các ph n t ị ầ ử ự ị
- M i cung đ c xác đ nh b i 2 nút, các ph n t ỗ ượ ầ ử ở ữ ể gi a 2 nút là các đi m ở ị
đi u khi n (vertex), các đi m này xác đ nh hình d ng c a cung. ủ ể ể ề ạ ị
- Các cung giao nhau t i các nút, k t thúc m t cung là nút. ạ ế ộ
- Vùng là t p h p các cung khép kín, trong tr ng h p vùng trong vùng thì ậ ợ ườ ợ
t gi a cung bên trong và cung bên ngoài. ph i có s phân bi ự ả ệ ữ
Trong c u trúc Topology, các đ i t ng không gian đ c mô t ố ượ ấ ượ ả ả trong b n b ng ố
ả d li u: b ng t a đ cung, b ng topology cung, b ng topology nút và b ng ữ ệ ả ả ả ọ ộ
topology vùng. Gi a các b ng này có quan h v i nhau thông qua cung. T đây, ta ệ ớ ữ ừ ả
có th phân tích các quan h c a các đ i t ệ ủ ố ượ ể ộ ệ ọ ng không gian trên cùng m t h t a
đ .ộ
Thí d :ụ
Hình 7: Minh h a d li u Topology
ọ ữ ệ
Topology Vùng
Vùng
A B Vùng ngoài vùng a và b
Cung AB, AaB AB, AbB Vùng ngoài
B ng 2: B ng topology vùng
ả
ả
Cung
Vùng trái
Topology Cung Nút cu iố
Nút đ uầ
Vùng ph iả
AB AaB AbB
A A A
B B B
a Vùng ngoài b
b a Vùng ngoài
B ng 3: B ng topology cung
ả
ả
Topology nút
Nút
A B Cung AB, AaB AB, AbB
B ng 4: B ng topology nút
ả
ả
D li u t a đ cung ữ ệ ọ ộ
Nút đ uầ Cung Đ nh vertex (x,y) ỉ Nút cu i (x,y) ố
AB AaB AbB (x,y) A A A a1, a2, a3, a4, a5 b1, b2, b3 B B B
B ng 5: B ng d li u t a đ cung
ữ ệ ọ ộ
ả
ả
3
U NH
C ĐI M C A C U TRÚC VECTOR VÀ RASTER
Ư
ƯỢ
Ủ
Ấ
Ể
STT 1
ấ ấ ữ
ả ồ ự
VECTOR ứ ạ ồ
ả ơn raster ự
2
ơ
3
RASTER C u trúc d li u đ n gi n ơ ữ ệ Các thao tác ch p b n đ th c hi n ệ ả ậ d dàng và đ n gi n ả ễ Bài toán mô hình th c hi n d dàng ự
ệ ễ ự
ọ ữ ệ ộ ớ
4
D li u c ng k nh ữ ệ ồ ề
ả ơ ệ ệ ự ệ ậ
5
ể ể ự c. Bài toán m ng khó th c ạ ượ M i quan h topo khó có th th ố hi n đ ệ hi nệ
ệ ử ụ ớ ữ ệ ạ ợ ớ
6
ữ ệ Thích h p v i vi c s d ng d li u ợ vi n thám ễ C u trúc d liêu ph c t p h Các phép ch p b n đ khó th c hi n ệ ậ đư cợ Bài toán mô hình khó th c hi n ệ D li u g n (chi m ít b nh ) h n ơ ế mô hình raster Cho phép mã hóa topo hi u qu h n và vì v y cho phép th c hi n các phép liên quan đ n các thông tin topo (nh ư ế trong phân tích m ng)ạ ự Thích h p v i d li u đo đ c tr c ti pế
