BQ GIAO DUC vA DAo TAO

TRUONG DHDL NGOAI NGU - TIN HOC TP.HCM
KHOA CONG .NGH~ THONG TIN

,

..-..

J:..

.....•...

KHOA LUAN
TOT NGHIEP
•
•
)cAY DUNG CHUONG TRINH BIEN TAp
DilLm~BAND6TOPOLOGYPHUC~U
•
•
•
CHO cAc BAI ToAN PHAN TicH MANG
•
TUYEN DE HO TRO• DIEU PHOI GIAO
THONG TRONGTHANH PHO

GIANG VlEN HUONG DAN: Ths Nguy~n Minh Nam
SINH VlEN THlfC HI~N:

DB Hoang Nh~t

Nguy~n Nghi

TP.HO CHI MINH - 2004


1

Ph~n gi6i thi~u

pHAN GI<~lITHltU
Nuac ta hi~n nay vai chu truong "cong nghi~p hoa, hi~n d~i hoa" dang
ttmg buac dAy m~nh vai tro cua tin hQc trong cong tac qu~m ly. NhiSu "d\l'an

d~u tu da duQ'c th\l'c thi va d~t nhiSu kSt qua. Trong thuong m~i, h~ th6ng
thuang m~i di~n tu dang duQ'c triSn khai. Ben c~nh do, kS ho~ch phat triSn
hinh thanh mQt chinh phu di~n tu la mvc tieu nh~m tai. Va t~m quan trQng
cua GIS trong tin hQc da duQ'c cac nha lanh d~o quan tam han trong thai gian
g~n day. Th\fc tS cho th~y dng, a cac nuac tren thS giai da thanh cong trong
vi~c ung dVng GIS til quan ly vi mo cho dSn cong tac quan ly co t~m voc
qu6c gia. S\f thanh cong nay xu~t phcit til nhfrng d~c thu v6n la Uti diSm cua
GIS nhu : S\f tich hQ'Plien nganh thu~n lQ'icho vi~c diSu hanh cac m~ng luai
til giao thong, di~n tho~i, h~ th6ng cap nuac, cap di~n .... cho dSn h~ th6ng
cac cong ty, xi nghi~p, ... - day chinh la mQt ph~n ca sa cua cong tac quan ly
chinh phu di~n tu, han thS nfra GIS khong con xa l~ d6i vai con nguai nha
vao cac ling dVng tim duang va dinh vi trong cUQCs6ng h~ng ngay. Chinh til
nhfrng thS m~nh nay, cac qu6c gia phat triSn da xem GIS nhu mQt nganh mlii
nhQn va co nhfrng d~u tu dung muc.
Vi~t Nam vi~c ling dVng cong ngh~ GIS v~n con g~p nhiSu kho khan,
til ngu6n nhan l\fc co trinh dQ chua nhiSu dSn ngu6n dfr li~u cho cong ngh~
nay con h~n h~p. Cac lap chuyen nganh vS cong ngh~ GIS da duQ'c nhfi nuac

d~u tu nhung s6 lUQ'ngnguai nghien Clruv~n con kha khiem t6n. Dfr li~u hi~n
nay da s6 chi la duai d~ng mo hinh notopology hay v~n chi con thS hi~n tren
gi~y kho co thS th\!c hi~n cac bai toan phan tich m~ng tuySn cho nhfrng ung
dVng GIS.
Til do nhom tac gia phat triSn bQ bien t~p dfr li~u ban d6 di~n tu, h~
th6ng diSu ph6i tuc thai va h~ th6ng thu gom rac thanh ph6 H6 Chi Minh.
Vai bQ bien t~p dfr li~u ban d6 di~n tu nhom tac gia hy vQng gop ph~n vao
cong vi~c xay d\fng nen nhiSu ngu6n dfr li~u thuQc cac lInh V\fCkhac nhau
trong cUQcs6ng. Con d6i vai h~ th6ng diSu ph6i tuc thai va h~ th6ng thu gom
rac thanh ph6 H6 Chi Minh la mQtminh chling ra rang cho cong tac quan ly
va diSu hanh cac cong ty thong qua cong ngh~ GIS.
Nhom tac gia xin chan thanh cam an quy truang hQc, quy th~y co va d~c
bi~t la th~y NguySn Minh Nam da t~n tinh giup dO'va khich l~ trong su6t thai
gian hoan thanh th\fc t~p t6t nghi~p nay.

a


2

Ml)C Ll)C

CHUONG

1:

TONG QUAN VE H~ THONG THONG TIN DfA LY

1.1.
H~ th8ng thong tin dja Iy (GIS-Geographic Information

1.2.
Mo hinh dfr li~u clla h~ th8ng thong tin dja ly
1.2.1.
Dfr li~u dja Iy
1.2.2.
Mo hinh ban dA chAng x~p
1.3.
Thu th~p cac nguAn dfr li~u clla GIS
104.
Hi~n tr~ng ung d\lng cong ngh~ GIS t~i Vi~t Nam
1.5.
K~t lu~n
CHUONG 2:
2.1.
2.2.
2.3.

MO HiNH TOPOLOGY

,

,,,

-U

System) lit gi

CAC CONG NGH~ D . <)C S

4.1.

Vai tro clla dfr li~u trong h~ th8ng thong tin dja ly
. quye~t van
~ dAe
4 .2 .
H'u'01lg glal
4.2.1.
Gioi thi~u v~ vimg thao tac
4.2.2.
Cac chtfc nang cO'ban
4.3.
K~t lu~n
CHUaNG
5.1.
5.2.
5.3.
CHUaNG

6.1.
6.2.
6.3.

5:

•

Ht THONG DIEU PHOI TUC THCn

Y nghia th \I'c ti~n
Huo'ng giai quy~t v~n d~
K~t lu~n

6:

11
12
14

U Dl}NG

BO BIEN T~P DU LItU BAN DO DItN TU

?

11

topology)

3.1.
Gioi thi~u v~ h~ quan trj MySQL
3.1.1.
MySQL lit gi
3.1.2.
D~c diSm clla MySQL
3.2.
Gi,Oithi~u v~ COM
3.3.
Ket lu~n
CHUONG 4:

5
5

5
6
8
9
10

vA cAu TRUC VPF

Mo hinh Topology
C~u truc Topo winged-edge(winged-edge
K~t Iu~n

CHUONG 3:

5

HE THONG QUAN L Y THU GOM RAc THANH PHO
H 0" CHI, MINH

Huong giai quy~t v~n d~
H~ th8ng di~u ph8i qua trinh thu gom rac 0' thitnh ph6 HA Chi Minh
Cac ",ng d\lng th\fc ti~n clla biti toan TSP

16

:

16
16
16

17
21
23
23
24
.
24
29
52
53
53
54
66

67
67
79
79


CHUONG
7.1.
7.2.
7.3.

7:

Xu th~ hi~n t~i
Cae ki~n true phat tri~n 6'ng dl}ng tren m~ng
K~t lu~n


CHUaNG
8.1.
8.2.

UNG Dl)NG vA THl/C THI H-'::THONG TREN M.;.NG

KET LU~N vA HUaNG

8:

K~t lu~n
Hu'ong phat tri~n
.......................................................................................................................

PHl) Ll)C
1.

2.
2.1.
2.2.
2.3.
2.4.

PHAT TRIEN

C~u true chi ml}e R- Tree
Cae K~t qua d~t dU'Cle
A b?an d"0 d'AI~n Cu
BQA b'Alen C~p d-U'rI~U

~ Xl,
01 tae
H ~ th~ong d'"leu p h~'
H~ thBng gom rae thanh phB
Th •.•.
e thi u'ng dl}ng tren Web
A

80
80
80
81
82
82
82
83
83
84
. 84
. 94
96
97


4

Ph~n mQt

PHANM<)T:


cAe KHAI NI~M co BAN


Chuang 1: T5ng quan

vS h~ th6ng

CHUONG 1:

TONG QUAN

thong tin dia

ly

5

VE Ht THONG THONG TIN DJA L Y

1.1. He thBng thong tin dia Iy (GIS-Geographic Information System) lit gi ?
H~ th6ng thong tin dia ly (Geographical Information System - GIS) hi
S1JkSt hQP gifra cong ngh~ bim d6 s6 hoa v6i cong ngh~ quim tri cO'sa dfr li~u
cho phep vi~c troy xu~t, xu ly th6ng ke rnQt kh6i lUQ11gl6n thong tin kh6ng
16, da d~ng nhanh chong va r~t tr1Jc quan ..... Cong ngh~ GIS v6i kha nang
phan tich khong gian rnQt cach chinh xac, nhanh chong da duQ'c tmg d\lllg
trong r~t nhiSu nganh khac nhau ph\lc V\lcho vi~c quim ly vI mo.
H~ th6ng thong tin dia ly dong vai tra nhu rnQt ky thu~t t6 hQP. H~ th6ng
thong tin dia ly da tiSn hoa bai S1Jlien kSt rnQt s6 cac ky thu~t t6 hQP reri r~c
van thanh rnQt t6ng thS han la S1JcQng cac thanh phftn cua chung l~i.


Ban

dB

NQi suy

Vi~n tham
Phan tich khong

Hinh 1: H? th6ng thong tin aia If vai Slf tich h9P cac ngcmh khoa h9C khac
nhau.

1.2.Mo hinh dU'lieu ella he thBng thong tin dia Iy :
1.2.1. Du' lieu dia Iy :
Do S1Jtich hQP lien nganh nen h~ th6ng thong tin dia ly lam vi~c v6i
nhiSu ngu6n thong tin khac nhau nhu: b:!m d6, anh hang khong, anh viSn
tharn ... H~ th6ng thong tin la rnQt h~ th6ng thu th~p, lUll trfr va diSu hanh cac
thong tin du6i d~ng gi~y, anh, s6 vS cac hi~n tUQ11gt1J nhien trong thS gi6i
th1Jc. Trong Co'sa dfr li~u duQ'c c~u thanh til thong tin, cac thong tin thuerng
khong su d\lng duQ'c tr1Jc tiSp rna phai thong qua rnQt h~ th6ng cac cong C\l


Chuang 1: T6ng quan v~ h~ th6ng thong tin dia

ly

6

troy xu~t, tai t~o l~i d6i tuqng thS gi6i thvc rna nguai dung quan tam. MQt d6i
tUQ'ng duQ'c lUll trfr trong co So' dfr li~u du6i d~ng cac thvc thS hinh hQc,

nguai dung se phai tai t~o l~i d6i tuqng ~y thong qua cac dfr li~u hinh hQc
nay.
Nhu v~y dfr li~u la r~t da d~ng, chung co mang tinh khong gian, thai gian,
duQ'CgQi la dfr li~u dja ly.
Dinh nghia: Dfr li~u dja ly la cac dfr li~u s6 mo ta cac d6i tuqng trong thS

gi6i thvc.
Dfr li~u dja ly duQ'ct6 chilc thanh hai nhom thong tin chinh, do la:
1/ Nhom thong tin vS phan b6 khong gian.
2/ Nhom thong tin vS thuQc tinh cua d6i tUQ'ng.
1.2.2. Mo hinh ban dA chAng x~p:
MQt trong nhu'ng phuong phap chung nh~t cua t6 chilc dfr li~u dja ly la t6
chilc theo ban d6 va cac lap thong tin. M6i lap thong tin la mQt biSu diSn cua
dfr li~u theo mQt mvc tieu nh~t djnh, do v~y no thuang la mQt ho~c mQt vai
d~mg cua thong tin. Vi dV dS nghien Clru ngu6n tai nguyen thien nhien, dja
ch~t, cac diSu ki~n v~t ly lap du6id~t, Slr dVng d~t, kenh r~ch
Nguai ta
tach chung thanh cac lap.
86i v6i bai toan quy ho~ch thanh ph6, cac thong tin co thS la dfr li~u vS
duang ph6, cong trinh cong cQng, giao thong, phan vung .... Cac thong tin nay
duQ'c l~y tu ban d6, anh hang khong, anh vu trv va duQ'Cch6ng xSp len nhau
dS duQ'c ban d6 t6ng quat. Cach t6 chilc theo lap nay la hQ'Ply nSu chung ta
dang lam vi~c v6i cac d6i tuqng trai bS rQng. Tuy nhien phuong phap nay co
thS khong celn thiSt nfra nSu chung k:hac theo dQ cao hay theo thai gian.


Chuang 1: T6ng quan v~ h~ th6ng thong tin dia

ly


7

mnh 2: M6 hinh du: li?u wjt If;.
M6i lap thong tin lC;lico rno hinh c~u truc chi tiSt han. VS nguyen ly lap
thong tin la t?P hgp cac dfr li~u dia ly vS rnQt khia cC;lnhnao do cua d6i tUQl1g
dia ly th\1"ctS. Do do no se rnang c~u truc chung cho lOC;lidfr li~u do.
Khong gi6ng nhu cac dC;lngdfr li~u thong d\mg khac, dfr li~u dia ly phuc
tC;lPhan, no bao g6rn cac thong tin vS dia ly, cac quan h~ topo va cac thuQc
. tinh phi khong gian. MQi dfr li~u dia ly co th@ duQ'c rno hinh v6'i ba thanh
ph~n khac nhau theo quan ni~rn topology - di@rn, duong, vung.B~t ki rnQt d6i
tUQ'ng t\1"nhien nao dSu co th@ duQ'c bi@u diSn b~ng rnQt trong ba d6i tUQl1g
nay kern theo chung la nhfrng thong tin d~c thu rieng.
Mo hinh dfr li~u dia ly bao g6rn b6n thanh ph~n sau:
1. Thanh ph~n khoa.
2. Dinh vi.
3. Thanh ph~n phi khong gian.
4. Thanh ph~n khong gian.
Khoa : la rna s6 duy nh~t cho th\1"cth@d@phan bi~t th\1"cth@nay v6'i th\1"c
th@khac.
Dinh vi: Chi ra vi tri cua th\1"cth@.
Thanh ph~n phi khong gian: La nhfrng thuQC tinh rieng cho timg th\1"cth@
nhu ty l~, khoang cach, dinh danh ....
Thanh ph~n khong gian : Cac d6i tUQ'ng t\1"nhien ben ngoai duQ'c chuy@n
vao may tinh d@quan ly theo hai cach sau :
1. Raster.
2. VectO'.


Chuang 1: T6ng quan v~ M th6ng thong tin dia I;'


8

M6 hinh vecta : Thuemg duqc biSu diSn duai d,;mg diSrn, duong va
vung . Vi tri khong gian cua mQt th\fc thS duqc xac dinh boi rnQt h~ t<;>adQ
th6ng nhfit to~mc~u. MQt th\fc thS duqc xac diOOboi c~p tQa dQ (X,Y) va cac
thuQc tinh khac OOu: kiSu diSrn, mau, hiOOd?ng .

X

Di&w.: Dei t~g cO kich th1i&~ng dang ki tr&lbk dO.

I

Th~ tIi ditm

o

TAm ditm

•

NUt

em v1mg

Hinh 3: Minh h9a v~ cac thlfc thd aU(Jcthd hi?n tren him ad.
M6 hinh Raster: Dfr li~u Raster duqc phan bi~t b~ng dan vi pixel, d6 la
hinh anh dan vi 006 nhfit phan anh d6i tUQ'llgtrong khong gian.
cfiu truc dfr li~u raster 2-D duqc xern nhu la rnQt rna tr~n cac 0 luai d~c trung
cho rnQt 0 vuong bS rn~t dfit. DQ phan giai cua dfr li~u raster ph\! thuQc van

kich thuac cua OOfrng0 luai nay.

~NUfu

IlZJ
\'tiD

Rtrnll
Dtt ~ns

ns~

333322111
333332211
113333221
111333222
111113322
111113331
222212333
322222222
332222111

Hinh 4: Minh h9a dit fi?u raster, ta co rn(Jtrna tnjn vai cac gia tr; khac nhau.
Trang ao nuac co gia tr; 1, rung fa 2 va de}tn6ng nghi?p fa 3.
I.3.Thu thap eae DguBD dfr lieu eua GIS:
C6 nhiSu ky thu~t dS thu th~p thong tin cho cac ngu6n dfr li~u. N6
thucmg duqc thu th~p til vi~c do d?c tr\fc tiSp tren nhfrng vung dia tr~c khac
nhau. Tuy nhien, rnQt s6 Ian dfr li~u c6 thS duqc chuySn d6i til ban d6 gifiy
sang hiOOthuc luu trfr cua ban d6 di~n tir. C6 hai phuang phap thuemg duqc
sir d\!ng d6 la :



Chuang 1: T6ng quan v~ h~ th6ng thong tin dja

ly

9

Phuong phap quet (scanning):
Day la ky thu~t thong dVng rna l?i it t6n kern, co thS dugc th\1'c hi~n
tren cac may tinh ca nhan hay cua cong ty. May quet se luu tm l?i cac hinh
anh cua ban d6 gifty duai hinh thuc s6 va hiSn thi chung tra l?i man hinh.
Vi~c quet hinh anh tu ban d6 gifty tuong d6i don gian va nhanh chong, tuy
nhien phuong phap nay l?i khong thS cung cftp thuQc tinh cua cac d6i tugng
t\1'nhien nhu dia chi cua mQt toa nha hay ngay thanh l~p cua mQt san v~n
dQng nao do. Dt! li~u co dugc tu nhfrng phuong phap nay thuang duai d?ng
. raster cho kich thuac rftt Ian.
Phuong phap s6 hoa:
Ky thu~t nay doi hoi phai cung cftp cac thiSt bi chuyen nganh. Ban d6
ngu6n se dugc trai bS m~t ngang, mQt con tro se xac dinh tQa dQ cac diSm t?O
nen hinh d?ng ban d6, sau qua trinh s6 hoa, thuQc tinh cua cac d6i tugng mai
dugc them vao. Phuong phap nay doi hoi nhiSu thai gian va ngu6n dt! 1i~u co
dugc tu ky thu~t nay duai hinh thuc Vecto.
Phuong phap vecto hoa :
MQt vai h~ th6ng may tinh chuyen nghi~p co thS chuySn d6i dt! 1i~u
Raster sang d?ng dt! 1i~uVecto. Phuong phap nay cho t6c dQ nhanh do tinh t\1'
dQng nhung l?i kern chinh xac hon so vai vi~c s6 hoa thu congo
Cac ky thu~t tren dSu d\1'avao ngu6n dt! 1i~uban d6 gifty co s~n. Tren th\1'ctS,
nguai ta con d\1'avao cac nganh linh V\1'Ckhac nhu : viSn tham, GPS, phan
tich anh ... dS thu th~p ngu6n dt! 1i~ucho GIS.

lA.Hien trang u.ng dung cong ilghe GIS tai Viet Nam :
Hi~n nay cong ngh~ thong tin phat triSn rftt m?nh me, nhiSu cong ngh~
tien tiSn truac day chi co a cac nuac phat triSn thi hi~n nay dil co m~t a Vi~t
Nam. D6i vai san ph~m cong ngh~ thong tin chuyen nghi~p nhu h~ th6ng
thong tin dia 1y, tuy 1a cac nha cung cftp 1uon c6 g~ng dua ra cac san ph~m dS
dung, ti~n 19i nhung th\1'ctS v~n co khoang cach git!a cac nha chuyen mon va
cac san ph~m cong ngh~ noi tren .. d Vi~t Nam h~ th6ng thong tin dia 1y trng
dVng chu ySu cho cac linh V\1'Cs6 hoa. Sau giai do?n s6 hoa nguai ta c~n dSn
h~ th6ng thong tin dia 1y a cac chuc nang phan tich khac dS giai quySt cho
nhu-ng bai toan ung dVng.
NhiSu cong ty nuac ngoai dil xam nh~p vao thi truang Vi~t Nam trong
lInh V\1'Cnay. Tuy nhien, gia cac san ph~m ph~n mSm cua hQ rftt cao t?O mQt
khoang cach ngay cang xa cho vi~c ung dVng GIS vao cUQcs6ng h~ng ngay.


Chuang 1: T6ng quan

vS h~ th6ng

thong tin dia 1;'

10

i

I
I

1.5.K~t luan:
Cong ngh~ GIS vai nhfrng 19i th@cua no da: mang l~i phuang phap quan

ly hi~u qua han, m9i sv v~t, d6i tugng, til nhfrng thong tin khong gian d@n
nhfrng thong tin phi khong gian t~t ca dSu dugc quan ly mQt cach th6ng nh~t
tren cung h~ th6ng. M9i truy xu~t dSu thS hi~n trvc quan han tren ban db s6
thay cho nhfrng dong van ban dan thu~n. Chinh vi th@GIS ngay mQt tro nen
quen thuQc han cho nguai dung, no dugc ung dVng trong nhiSu lInh vi~c til
dan gian d@nphuc t~p va chi phi doi hoi d~u tu ngay mQt th~p han. Co thS
noi r~ng GIS ngay mQt tv kh~ng djnh t~m quan tr9ng, dugc cac nuac phcit
triSn xem nhu mQt mlii nh9n trong lInh V\fC cong ngh~ thong tin va dugc dua
vao chuang trinh giang d~y.


Chuang 2: M6 hinh topology

CHUONG2:

va du true VPF

MO HiNH

TOPOLOGY

11

vA cAu

TRUC VPF

2.1.MB hinh Topology:
NSu nhu bim d6 dia hinh rna ta nhung vi tri v~t ly va hinh d~ng Clla cac
d6i tUQ'ng tv nhien thi rna hinh topology thS hi~n cac quan h~ giua cac d6i

tUQ'ngdo. Xet vi d\l trong ban d6 dia ly Clla cang vien Hyde a nuoc Anh thS
hi~n chinh xac hinh dang Clla cang vien va nhfrng thvc thS khac (h6 nuoc
Serpentine) ben trong no.

HinhA

HinhB

lflnh 5: Minh h9a rna hinh Topology.
Tuy nhien trong rna hinh Topology (Hinh B) diSu nay khang quan trQng.
Voi rna hinh nay rnu6n cho ta th~y d6i tugng h6 nuoc Serpentine n~rn ben
trong cang vien, thS hi~n rn6i quan h~ vS vi tri giua cang vien Hyde va h6
nuoc Serpentine.
Duoi d~ng rna hinh topology may tinh co kha nang phan tich rn6i quan
h~ giua nhung d6i tUQ'ngkhac nhau. NSu co sv sai xot vS du 1i~u, GIS khang
thS thvc thi qua trinh phan tich rn~ng tuySn dS giai quySt nhfrng v~n dS lien
quan dSn dia ly.
Hai khia c~nh quan tn;mg trong rna hinh t6 chuc du li~u topo do la nut,
c~nh lien kSt (link-node) va vung (pologon).
Khcii niern v~ nut va canh lien kit:
Trong h~ th6ng thang tin dia ly cac d6i tUQ'ngduemg th~ng (Lines) con
duQ'c gQi la c~nh lien kSt (links) duQ'ct~o til nhung diSrn (Vertex) va nhung
nut(node) t~i hai d~u rnut Clla c~nh.


Chuang 2: M6 hinh topology

va du true VPF

12


Vertices

/

Hinh 6: Minh h9a

4

Khcii niem

\

vJ nut va cgnh.

vJ vimg (polygon):

La mQt vung khang gian dong duQ'c chi ra boi gi6i h~n cua t~p hQ'P cac
c~nh va diSm rna co m6i quan h~ dSn tinh ch~t dia ly c~u t~o nen no.

Hinh 7: Minh h9a

vJ vimg.

Phan tich m~ng tuySn la mQt tiSn trinh th\Ic thi cac phep tmin hQc tren cac
lap d6i tuqng nut va c~nh dS tim ra duang di, tinh kho~mg cach hay thai gian
cho mQt yeu cfiu mlo do. Hinh thuc dan gian nh~t cua phan tich m~ng tuySn
do la chQn hai diSm b~t ki tren h~ th6ng m~ng va xac dinh lQ trinh ng~n nh~t
gifra hai diSm nay.


2.2.C~u true Topo winged-edge(winged-edge

topology)

Winged-edge topology la mQt phfin r~t quan trQng cua rna hinh dfr li~u
VPF. Chuc nang cua c~u truc nay co thS t~o nen mQt m~ng cac do~n th~ng va
cac Face dia hinh hQc. Dr nhien cac thanh phfin cua Winged-Edge topology
khang gi khac han 3 d6i tuqng chinh cua dinh d~ng VPF la Node, Edge va
Face. Tuy nhien, tac gia cling xin nh~c l~i 0 muc chi tiSt han :


Chuang 2:

Me hinh

topology

va c~u truc VPF

13

eThong tin vS Node: m6i Edge chua mQt StartNode va mQt EndNode,
thong tin nay giup ta dinh huang duQ'c chiSu cua Edge 1a til StartNode dSn
EndNode, dTnhien 1achiSu s6 hQc.
e Thong tin vS Edge: RightEdge va LeftEdge n6i mQt Edge dSn cac qmh
kS cua no (vi v~y m6i co thu~t ngfr 1a Winged-Edge). RightEdge 1a qmh ta
g~p dfru tien khi ta di nguQ'c chiSu kim dfmg h6 (chiSu (+)) t~i EndNode, cling
tuO'ng tv nhu thS LeftEdge 1a c~nh dfru tien ta g~p khi di nguQ'c chiSu duang
t~i StartNode.


Left Face

RlghtFace
•
__

Node
)

Edge
Chl~u quay

mnh 8: Cae thanh ph/m eua Winged-edge.
eThong tin vS Face: v6i cftu truc topo cftp 3 thi m6i Edge chua mQt
LeftFace va RightFace. LeftFace va RightFace duQ'c xac dinh 1ad6i di~n nhau
co ba 1a Edge, cac thong tin nay cho phep mQt Edge xac dinh duQ'c cac Face
chua no .
•:. Giai thu~t Winged-Edge
a.Xac dinh Face nao cfrn duQ'c ve va vao bang Ring dS tim cac- vong
(Ring) tuO'ng ung cho Face se duQ'cve.
b.Xac dinh StartEdge trong bang Ring
c.Di theo LeftEdge dS tim LeftFace va RightEdge dS tim RightFace. Vi
d\l: vi Face 3 1a LeftFace cua Edge 12 nen ta dQc m~u tin vS LeftEdge do tuc


Chuang 2:Mo hinh topology

va du true VPF

14


Edge 11, Edge 11 dfin ra Edge 10, 10 -)- 9, 9 -)- 8, 8 -)- 7,7 -)- 6, 6 -)- 5, va
cu6i cung 5 -)- 12.
d.Edge 12 chinh la StartEdge, do do ta hoan d.t rnQt Face.
A

8

9

LEGEND

2

Face

G.

Node

1

Edge

LEFT_EDGE

RIGHT_FAC

LEFT_FACE


RIGHT EDG

E
F
G
G
D

2

1

2

2

1

3

1

2

1

4

2


1

2

2

3

3
1

12

D

C

1

3

7

5

C

B

1


3

8

6

8

B

A

1

3

9

7

9

A

1

3

10


8

10

K

L
L

3

1

9

11

11

K

J

1

3

12


10

12

J

H

1

3

4

11

13

I

I

4

1

13

13


ID

START NOD

1
3

D
E
F

4

H

5

H

6
7

2

END NODE

Coordinates

6


Not
Shown

5

Hinh 9: Winged-Edge.
Hinh tren minh h9a cho giai thu~t Winged-Edge : tu dfr li~u da duqc rna
hoa giai thu~t Winged-Edge hi@nthi ban dB theo dung dinh d~ng VPF.
2.3.K~t luan:
Mo hinh t6 chuc dfr li~u topology v6i c~u truc quan ly tuong d6i phuc
t~p, song l~i rnang l~i nhiSu thu~n lqi trong vi~c ph an tich rn~ng tuySn. Co th@
noi r~ng rno hinh nay r~t c~n thiSt trong cac ung d\lllg GIS, do tinh ch~t tich
hqp da nganh trong trng d\lllg GIS nen cac thong tin dfr li~u la vo cung phuc
t~p va da d~ng va ta se kho th@nao ki@msoat duqc chung nSu dfr li~u nay


Chuang 2:

Me hinh

topology

va du true VPF

15

khong d?t chu~n Topo. Cac d6i tUQ11gnut, c?nh, vung dugc qufm ly dt ch?t
che chinh vi thS vi~c thao tac chinh sua tren mo hinh nay la r~t phuc t?P va
doi hoi phai dugc th\l'c hi~n mQt cach d6ng bQ dS khong lam pha va c~u truc
Topology ban dfiu, qua trinh thao tac tren chung se dugc nhom tac gia trinh

bay chi tiSt han trong phfin bien t~p dii li~u ban d6 di~n tu.


16

Chuong 3: Cae eong ngh~ dmle sir d\mg

CHUONG3:

cAc

CONG NGHt BUQC

sir Dl)NG

3.1.GiOi thieu v~ he gmin tri MySOL:
3.1.1. MySOL lit gi:
MySQL la mQt h~ qUlin tri co sa dfr li~u nho g<;m:
Co sa dfr li~u la mQt t?P hQ'P cac dfr li~u co cung cfiu truc. Vi d\l danh
sach cac hoa don mua hang, thong tin v@sach trong thu vi~n .... US truy xufit
va xu ly dfr li~u ta c~n mQt h~ qmin tri co sa dfr li~u OOu: SQL Server, Oracle
hay MySQL. Co thS thfiy r~ng MySQL rfit 000 g<;m, chiSm vung nh6 it
(khoimg 27 MB) va co thS ch?y tren cac moi truang cua cac h~ di@u hanh
khac nhau.
MySQL la mQt h~ quan tri co sa dfr li~u quan h~:
MQt co sa dfr li~u quan h~ la mQt t?P hQ'P nhi@u bang trong do dfr li~u
duQ'c 1uu trfr rna khong phai d~t chung mQt ch6 nh~m tang t6c dQ va dS quan
ly, MySQL h6 trQ' chuAn ANSI SQL (Structure Query Language).
MySQL la ph~n m@m rna ngu6n rna:
MQi nguai Slr d\lng d@u co thS download MySQL

dia chi

dS su d\lng va phat triSn h~ quan tri nay. MySQL co
nhi@u phien ban h6 trQ' cho cac h~ di@u haOO OOu: OS/2, Red Hat, Windows,
MacOS, ...

a

3.1.2. Bilc di~m cua MySOL:
MySQL la mQt h~ quan tri da lu6ng, kiSn truc thich hQ'P cho moi
truang da nguai su d\lng OOu Web.
Cung cfip mQt thu vi~n API kh6ng 16 nhu : C, C++, Java, Perl, PHP.
H6 trQ' nhi@u ham co ban cua SQL.
Cung c~p mQt t?P hQ'P OOi@ukiSu dfr li~u khac OOau nhu: Float,
Double, Char, Varchar, Text, Blob, Date, Time, ...
H6 trQ' cac toan tu trong m~nh d@Select va di@u ki~n Where.
H6 trQ' Left Outer Joins.
H6 trQ' cac bi daOO cho cac bang va cQt.
Ten ham khong duQ'c trung v6i ten bang hay cQt.
Cac file co sa dfr li~u Slr d\lng cac bang B- Tree v6i c~u truc Index va
duQ'c truy xu~t tu~n tv thong qua ISAM (Indexed Sequential Access Methodphuong thuc truy xu~t chi s6 tu~n tV) cho t6c dQ nhaOO va dQ tin C?y cao.


ChU011g 3: Cac cong ngh~ duQ'c Slr d1,1ng

17

SO' IO'a chon cac he guan tri cho .rng dung:

Cac ung dVng GIS dang co xu huang phat triSn theo huang rna

(OpenGIS), da nguai dung nen cac Ung dVng xay d\l11gtren nSn may dan
. khong con thich hqp nfra, thay vao do la cac Ung dVng xay dVng tren cac h~
th6ng m~ng. Vi~c ch<;mIva Co' So' dfr li~u dS h6 trq da nguai dung la phu hqp
han ca. Cac DBMS hi~n t~i tren thi truang dSu co thS dap Ung duqc yeu c~u
tren nen vi~c chQn Iva DBMS nao tuy thuQc vao yeu c~u vS tinh bao m~t cao
hay kha nang tai chinh ...
.
D6i vai bQ bien t~p dfr li~u ban d6 di~n tu chi danh cho nguai quan tri
hay nguai xay dVng ngu6n dfr li~u cho GIS, c~n nhiSu ham thu vi~n SQL va
h6 trq cac cfiu truc truy vfin 16ng. Vi v~y sv Iva chQn SQL la Co' So' phu hqp
cho nhu c~u cua ung dVng. Trong khi MySQL vai tinh gQn nh~, dan gian, dS
Slr dVng, t6c dQ nhanh, dS dang cai d?t, d?c bi~t MySQL hi~n dang la DBMS
miSn phi vai cac phi en ban ch~y tren nhiSu h~ diSu hanh khac nhau co h6 trq
rna ngu6n rna. Cach tiSp c~n theo xu huang MySQL nay con co uu diSm la
tich hqp luon ca dfr li~u khong gian va dfr li~u thuQc tinh cua GIS trong mQt
h~ th6ng th6ng nhfit dS ti~n quan ly. M?t khac MySQL rfit phu hqp vai cac
may co cfiu hinh khong m~nh I~m, kha nang bao m~t t6t. Day la tieu chuAn rfit
phu hqp cho cac cong ty t~c xi v6n mu6n xay d\l11gcac ung dVng qufm ly va
. diSu ph6i gQn nh~ va phu hqp vai tui tiSn.

I

I

I

3.2.GiOi thieu v~ COM:
COM (Component Object Model) Ia mQt d?c ta cac giao di~n (inte.rface)
cho vi~c dung I~i cac thanh ph~n Ung dVng. MQt giao di~n COM thi khong
phv thuQc vao ngon ngfr I~p trinh, cac ngon ngfr l~p trinh dSu co thS thvc thi

duqc COM.
MQt thanh ph~n cua COM duqc gQi Ia server va chuang trinh su dVng COM
duqc gQi la client. DS su dVng duqc mQt COM, client phai t~o ra mQt thvc thS
(instance) tham chiSu dSn d6i tuqng COM. COM chua d\l11gcac phuang thuc
trong khi do mQt thanh ph~n (component) co thS co cac thuQc tinh (property)
nhung chung duqc truy xufit thong qua cac phuang thuc trong giao di~n.
MQt COM dan gian nhfit duqc biSt dSn Ia IUnknown. Cac COM khac phai h6
trq t6i thiSu Ia IUnknown vi no cho phep client nh~n d~ng cac thanh ph~n
giao di~n khac. MQt IUnknown chua d\l11g3 phuang thuc sau:


Chuang 3: Cac cong ngh~ dugc Slr dVng

AddRefO

ReleaseO

18

ac ta
T~a ve ~Qt con tro den mQt giao di~n
neu no ton t:;ti.
Doi tUQl1gCOM chi a se nhieu client
khac nhau. Phuong thuc mlY dung dS
Hin s6luQ'n tham chiSu.
Giam so lUQ'ngtham chieu cho mQt
giao di~n. Khi gia tri dSm (count)
bftng 0, nghia la khong co mQt client
nao tham chiSu dSn no.


Client va COM server duQ'c thi tren cac ngon ngfr l~p trinh khac nhau, th~m
chi client va server co thS duQ'c ch:;tytren cac may tinh khac nhau, vi v~y cac
phuong thuc giao di~n khong duQ'ctruy xu&ttql'C tiSp rna phai gian tiSp thong
qua bang con tro ham.

MQt con tro giao di~n chua dVng dia chi cua bang dia chi ham, bang dia chi
nay duQ'c g9i la virtual function table (hay vtable), hay noi cach khac con tro
giao di~n la kiSu con tro dSn con tro, thuang la void **.
MQt COM co thS dinh nghTa cac kiSu dfr li~u rieng, chung dQc l~p vai ngon
. ngfr l~p trinh C++ hay cac ngon ngfr l~p trinh khac va cac kiSu dfr li~u nay


Chuang 3: Cac cong ngh~ duQ'c su dl,lng

19

duQ'c anh x~ dSn kiSu dfr li~u cua ngon ngfr l~p triOO xac dinh. Vi v~y cac
tham s6 truySn dSn COM chi co thS la cac kiSu rna COM h6 trQ'.
Dispatch Interface
Dispatch Interface la mQt giao di~n d\fa tren giao di~n chuAn la IDispatch kS
thua cac ham tu IUnknown, va them van cac phuong thuc khac cho thu~n ti~n
trong vi~c gQi nhfrng phuong thuc giao di~n khac. IDispatch them van
phuong th(rc InvokeO 000 van no ta co thS gQi cac phuong thuc khac phl,l
thuQc tham s6 truySn vao. Tham s6 la mQt gia tri kiSu integer 32 bit duQ'c gQi
la DispID dung dS xac diOOphuong thuc. Gia tri nay nh~n duQ'c thong qua
ham GetIDsOfNames.

ActiveX Control
MQt ActiveX control la mQt d6i tUQ11gCOM rna th\fC thi giao di~n
IUnknown va duQ'cdang ky van server du6i d~ng dll ho~c file .exe. Client cua

ActiveX control duQ'c gQi la mQt container. ActiveX control duQ'c d~t (]


20

Chucmg 3: Cac cong ngM dugc Slr d\mg

ActiveX cotrol container. Vi dV Microsoft Chart ActiveX control duO'c dat
trong ActiveX Control Test Container nhu hinh ben du6i:

'OOR"O
50

o

hart:
MSChart:
MSChart:
MSChart:
MSChart:
MSChart:
MSChart:
MSChart:
MSChart:
MSChart:
MSChart;
MSChart:
MSChart:
MSChart:
MSChart:

MSChart:
MSChart:

50

R1 R2 R3

R4 RS-

•

Mouse ave
utton-O}{Shif
MouseMove
{Button-O}{Shif
MouseMove
{Button-O}{Shif
MouseMove
{Button-O}{Shif
MouseDown
{Button-l}{Shif
ChartSeleeted
{MouseFlags
MouseUp
{8utton-l}{ShiftClick
DblClick
.
ChartActivated
{MouseFlag
MouseUp

{Button-l}{ShiftMouseMove
{Button-O}{Shif
MouseHove
{Button-O}{Shif
MouseHove
{Button-O}{Shif
MouseMove
{Button-O}{Shift•
MouseMove
{8utton-O}{Shift-O}{X-201}{Y-23}
DonePainting

-

MQt ActiveX control thuemg cung c~p giao di~n ngmJi su dVng. Khi
chung ta d~n mQt ung dVng phan tan, co mQt ly do giai thich t~i sao nhfrng
thanh phAn COM thong thuang khong hiSn thi cac giao di~n nguai dung. M~t
khac, cac ActiveX control thuemg di doi v6i container dS th\fc thi cac giao
di~n nguai dung.
Ki~n truc ActiveX control r~t phuc t~p. MQt ActiveX control d~c trung
thl,l'cthi han mQt bQ COM interfaces, mQt s6 trong do chua han 20 phuang
thuc. Th~m chi nhin bS ngoai dan gian nhu nhung mQt ActiveX control vao
trong mQt dialog box cling phuc t~p han nhiSu nguai tuemg.
chua mQt
ActiveX control, dialog box phai la mQt ActiveX control container va cac
container phai th\l'c thi mQt s6 COM interface cua chinh chung.

us

May m~n thay, MFC thl,l'chi~n r~t t6t vi~c bQc cac ActiveX control va

cac control container. Trong AppWizard, khi duQ'c chQn, mQt dialog ngay l~p
tuc tra thanh mQt container. Ta khong cAn vi~t mQt dong code nao cho vi~c
nay vi MFC cung c~p t~t ca cac cO'sa h~ tAng (infrastructure) cAn thi~t. T~t ca
vi~c ta phai lam la override cac ham ao va them cac phAn ti'r giup trinh diSu
khiSn cua ta khac v6i nhfrng cai khac.


Chuang 3: Cac cong ngM duQ'c sir d\lng

21

3.3.K~t luan:
Co thS th~y s\f l\fa chQn cac h~ qmin tri nao la tily thuQc vao nhu c~u
phM triSn lmg dvng va cac diSu ki~n khach quan khac. Nhung nhin chung,
MySQL v6i nhfrng Uti diSm cua no va ngay cang dugc phM triSn hoan thi~n
han, trong hi~n t~i cling nhu tuang lai se tra thanh mQt h~ qwin tri m~nh phil
hgp v6i nhiSu nhu c~u khac nhau. Hi~n nay MySQL v6i phien ban 5 da h6 trg
OpenGIS day la diSm thu~n 19i cho cac ung dVng trong linh V\fCnay. Trong
khi do COM la mQt hinh thuc mang tlnh cong ngh~ cho phep vi~c kha thi cac
thanh ph~n ung dVng tren cac ngon ngu l~p trinh khac nhau. Trong dS tai
COM dugc thiSt kS cho vi~c dua ban d6 di~n tu sang d~ng Web va co thS
dugc triSn khai tren m~ng Internet.


22

ph~n hai

pHAN HAl:


cAe H~ THONG DA TRIEN KHAI


Chuang

.

..

BO BIEN TAp nULIEU

CHUaNG 4:

.

BAN DO DIEN TV'

4.1. Vai tro ella dfr lieu trong he thBng thong tin dia IV:
Trong cong ngh~ GIS, dfr li~u gifr vai tro cvc ki quan tn;mg, no la nhan
t6 c~u thanh m9i chuang trinh ung dlfng va sv t6n t~i cua mQt trng dlfng GIS
phlf thuQc vao kha nang dap ung nhfrng nhu c~u thong tin cua nguai su dlfng,
cac thong tin nay dugc thay d6i thuang xuyen trong thvc tS va c~n phai nhanh
chong tra thanh dfr li~u Clfth@trong nhfrng ung dlfng GIS. Theo QD 93/2002,
kS ho~ch trong nam 2003 nha nuac se d~u tu 450 ty d6ng cho nganh tin hQc
va 50% s6 do danh cho vi~c xay dVng nen ngu6n dfr li~u. UBND TPHCM
d~u tu 80 ty d6ng d@xay dVng dv an SAGOGIS- la mQt h~ th6ng tich hgp cac
phan h~ nganh khac nhau- va nhfrng buac ban d~u c~n phai thvc hi~n la xay
dVng mai va t~n dlfng t6i da ngu6n dfr li~u s~n co.
Ben c~nh do vi~c khai thac ngu6n dfr li~u Topology hi~u qua, gop ph~n giai
quySt dugc nhiSu v~n dS giao thong do thi vao thai di@mhi~n nay nhu hi~n

tr~mg diSu ph6i h~ th6ng xe buyt, xe t~c xi. Tuy nhien diSu nay chi th~t sv
hi~u qua khi ngu6n dfr li~u la t6t va theo chu&n Topology, la d~ng chu&n dugc
su dlfng cho vi~c phan tich m~mgtuySn trong cac h~ th6ng GIS. Cac ngu6n dfr
li~u hi~n co tu nhfrng nha dia chinh thuang chinh xac nhung chu ySu vfin duai
d:;mgnotopology, diSu nay gay nhfrng kho khan r~t Ian cho vi~c phat tri@ncac
cong ngh~ GIS Vi~t Nam.
Tu vai tro quan tr9ng cua ngu6n dfr li~u dfin dSn nhu c~u c~n co mQt bQ
bien t~p dfr li~u topology nh~m phlfC V\l cho vi~c xay dVng mai dfr li~u dSn
vi~c chinh sua dfr li~u s~n co d@chuy@n vS d~ng chu&n Topology. Hi~n nay
tren thS giai co nhiSu ph~n mSm cho vi~c bien t~p va xay dvng dfr li~u nhu :
INTERGRAPH, ArcGIS, MAPINFO, ... Tuy nhien vi~c tri@nkhai su d\lng cac
ph~n mSm nay la kho do nhu c~u vS gia ca va muc dQ phuc t~p cua cac ung
dlfng. Chinh vi v~y nhom tac gia dfi dS xu~t va xay dVng thu nghi~m ph~n
mSm Topology Editor nh~m dap ung nhfrng nhu c~u tren.
MQt bQ bien t~p dfr li~u topology noi chung hay ph~n rnSm Topology Editor
n6i rieng c~n phai dap ung dugc nhfrng yeu c~u sau:
+ MQt la, tinh trvc quan trong qua trinh thao tac vai ngu6n dfr li~u.
+ Hai la, t6c dQ truy xu~t, c~p nh~t dfr li~u nhanh chong va dQ.chinh
xac cao, cac chuc nang phai dS dang su d\lng.
Cac tinh ch~t nay dugc h6 trg thong qua nhfrng thS m~nh cua cong ngh~ GIS,
giup nguai bien t~p co cai nhin trvc quan han trong qua trinh thao tac vai
ngu6n dfr li~u.

a

",

23

4: B<) bien t~p dfr li~u bfm d6 di~n tu



24

Chuang 4: B(>bien t~p dfr li~u ban d6 di~n til

. guyeAt van
A
.,."
4 .2 .H'U'O'ngglal
ue:
4.2.1. GiOi thieu v~ vung thao tac :
Vung thao tac la nai rna nguai co du vai tro co thS thao tac duQ'c cac d6i
tUQ'ng.Cac d6i tUQ'llgngoai vung thao tac se khong duQ'cthay d6i.
ChiOO nha vung thao tac giup h~ th6ng co thS phan quySn d6i vai cac
nguai Slr d\lng khac nhau. Han thS nfra, chuc nang nay t;;tOkha nang thao tac
tren cac d6i tUQ'llgduQ'cchiOOxac, OOanhchong va an toan han.
?

•

r'-'-'-'-'-'-'-'-'-'-'-'-'-'-'-'-'-'-'-'-'-'I
I

Vung Edit

lflnh 10: Minh h9a vimg thao taco
U'ng dung cay R-tree
Trong khi thao tac dfr li~u, nguai dung thuang xuyen tuang tac vai cac d6i
tUQ'ngtren ban db thong qua cai OOintqrc quan cua minh, dS may tiOOco thS

nhaOO chong thgc hi~n duQ'c diSu nay OOomtac gia dff lIng d\lng c~u truc dfr
li~u cay R-tree (se duQ'c giai thi~u chi tiSt trong chuang 8) cho vi~c dinh vi
cac d6i tUQ'llgduang, diSm va vung.
C~u truc cay R- Tree quan ly cac khung hinh chfr nh~t chua cac d6i tUQ'llghinh
hQc. Qua trinh kich ho;;ttcac d6i tUQ'llgtren ban db s6 duQ'cthgc hi~n nhu sau:
+ T;;tomQt hinh chfr nh~t ClientRect tuang ung vai vung Client.
+ Tim t~t ca cac hinh chfr nh~t rna giao vai ClientRect ta duQ'c t~p
(r1 ,r2 ... ,m).
+ T;;tidiSm kich ho;;ttnhanh chong phlit sinh mQt khung hinh chfr nh~t R
vai kich thuac vua duo
+ L~n luqt xac diOOnhaOO cac hiOOchfr nh~t trong t~p (rl,r2, ... ,rn) rna
giao vai R.
+ U'ng vai cac hinh chfr OO~ttim ra a buac tren tuy theo d6i tUQ'ngc~n
kich ho;;ttrna ta thgc hi~n cac buac sau :