MỘT SỐ VẤN ĐỀ TỐI ƯU HÓA VÀ NÂNG CAO HIỆU QUẢ TRONG XỬ LÝ THÔNG TIN HÌNH ẢNH
DƯƠNG ANH ĐỨC
Trang nhan đề
Mục lục
Chương_1: Mở đầu.
Chương_2: Tạo lập và lưu trữ dữ liệu ảnh vector.
Chương_3: Phép biến đổi Randon & Hough trong xác định đối tượng trên ảnh.
Chương_4: Xác định đường cong trên ảnh.
Chương_5: Kết luận.
Tài liệu tham khảo
M\lC l\lc
ChliOfi81.Md d~u 1
1.1. Yell du thtfc t6va ly do thtfc hic$nd~ tai : l
1.2. M1,1ctieu d~ tai " 2
1.3. So luQcv~ cac k6t qua nghien CUlltrongva ngoai nuoc " 3
CtlVONG2. T~o l~p va 11mtru du li~u anh vector 8
2.1. Thi6t k6 dli lic$u :.8
2.1.1. Winged-edge topology: " 9
2.1.2. Cac dip topology trong co sa dli lic$u ll
2.1.3. Qui uoc chung cho cac bang dli lic$u 15
2.1.4. M6 ta cac d6i tuQngco sa 16
2.1.5. Chi m1,1ckh6ng gian (spatial index) 23
2.1.6. MQtvi d1,1v~ vic$et~o cay chi m1,1ckh6ng gian 26
2.2. T~o dli lic$uant vector 34
2.2.1. Vector boa ant bitmap 34
2.2.2. TIm ph~n giao eua hai da giac ba't ky 43
2.3. Tom t~t 56
ChUOfi83. Phep bie'n d6i Radon & Hough trong xac dinh d6i tu'<;1ngtren anh
58
3.1. Phep bi6n d6i Radon 59
3.1.1. Phep bi6n d6i Radon (p,1') 59
3.1.2. Cac thuQctinh lien quan vic$cla'y mftu 60
3.1.3. Phep bi6n d6i Radon roi qc eua mQtduong thing 62
3.1.4. So sanh cac phuong phap nQisuy khac nhau 64
3.1.5. Bi6n d6i Radon roi r~c cua mQtdi€m 68
3.1.6. Tom t~t 70
3.2. Phep bi6n d6i Radon chu§:n 70
3.2.1. Phep bi6n d6i Radon (p, 8) eua duong thing 70
3.2.2. Cac thuQctint lien quan d6n vic$ela'ymftu 71
3:2.3. Phep bi6n d6i Radon (p, 8) roi r~c eua nhi~u duong thing 73
3.2.4. Phep bi6n d6i Radon (p, 8) roi r~e cua cae di€m 78
3.2.5. Tom t~t 80
3.3. Phep bi6n d6i Hough (p, -r) 81
3.3.1. Phat hic$nduong thing sli'd1,1ngphep bi6n d6i Hough 85
3.3.2. ChQnltfa tham s61a'y mftu cho phep bi6n d6i Hough (p, -r) 89
3.4. Phep bi6n d6i Hough (p, 8 ) 92
3.4.1. ChQnltfa tham s61a'y mftu cho phep bi6n d6i Hough (p, 8) 93
3.4.2. So sanh gilia cae ehi6n luQct6i u'uhoa 94
3.4.3. Cac thu~t roan tva Hough 97
3.5. Tom t~t 99
Chu'cn84. Xac dinh duong cong tn~n anh 101
4.1. Phep bi6n c16iRadon t6ng quat 102
4.1.1. Phep bie'n c16iRadon t6ng quat d<.lllglien t~c 103
4.1.2. Phep bie'n c16iRadon t6ng quat d~ng rGi r~c 104
4.2. Anh x(,lc1i6manh ."""""""""""""""""""""""""""""""""""""""""'" 106
4.3. La'y mftu kh6ng gian tham scL 110
4.4. Lam mGkh6ng gian tham s6 111
4.5. Thu~t roan FCD (Fast Curve Detection) 113
4.6. Xac c1inhcac c16ituQngd~ng hlnh troll 115
4.7. Xac c1inhcac c16ituQngd~ng Ellipse 118
4.7.1. Huang tie'p c~n 118
4.7.2. Thu~t roan tva Hough xac c1inhellipse qua bQ3 c1i6m 120
4.7.3. MQtthu~t roan khac xac c1inhellipse 123
4.8. Va'n c1~phep bie'n c16iRadon vai anh IOn 134
4.9, Kha nang song song hoa phep bie'n c16iRadon 136
4.9.1. Thu~t roan song song hoa dli lit%uthu~n n.iy (Data-Parallel RT) 138
4.9.2. Thu~t roan ke't hQpsong song hoa dli lit%uva xU'l.1(DTRT) 139
4.9.3. Thu~t roan song song hoa xU'1.1rich cvc(ATRT) 140
4.9.4. Thu~t roan song song hoa xU'1.1rich cvc vai bQnha tllt%(MATHT) .141
4.10. Nang cao hit%uqua b~ng logic mG 142
4.11. Vector hoa ban c16dung Radon va Hough 143
4.11.1. Xac c1inhpeak "c1~m"nha't 145
4.11.2. Xac c1inhta't ca c1o(,lnth~ng co tham s6 (PI, 81)trong kh6ng gian anh 146
4.11.3. C~p nh~t kh6ng gian anh va kh6ng gian tham s6 149
4.12. Tom t~t 149
Ph\ll\lCA Ham delta Dirac
Ph\ll\lc 1) MQt s6 va'n d~ v~ phep biSn d6i Radon
1
111
'A ?
TAI LI~U THAM KHA0
DANH SACH cAc CONG TRINH DA DANG
xxv
xxx
50 trang |
Chia sẻ: maiphuongtl | Lượt xem: 1813 | Lượt tải: 0
Bạn đang xem trước 20 trang tài liệu Luận án Một số vấn đề tối ưu hóa và nâng cao hiệu quả trong xử lý thông tin hình ảnh, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
haccacthongtin lien quailde'nm6iquail
ht$giil'acacphfintii'trenanh.Vi dl,1,mQtdo~nth£ngla c~nhcuadagiacnao,k~
voi hlnhnao, Khi khaosatdil'lit$uvoi cacm6iquailht$naytagQidil'lit$unay
la dil'lit$uvoi thongtintopology([58],[40]).
D~baadamtinhchu~nboavatlnhm~mdeo,d~thichnghi,saukhikhaosatra't
nhi~uformatdil'lit$u,chungtoi quye'tdinhdl;(atrenn~ntangm~u cosodil'lit$u
VectorProductFormat(VPF)doBQQu6cphongMy duaradSthie'tke'cosodil'
lit$uthongtinhlnhanhdungtrongcacht$th6ngcuamlnh.Cacn~ntangcoban
cuaVPF du<;1ctrlnhbaya cacphfinsau[40].
92.1.1. Winged-edgetopology
Ta'tca cachlnhanhd~uduQct'.1Ora tti'cacd6i tuQnghlnhhQCcdsa.Cacd6i
tuQngcdsdnaythuongbaog6m:ditim(node),do'.1nth~nghayddngiangQiIa
duong(line),dongvanban(text).ThongtinhlnhhQccuamQtditimduQccling
ca'pbdi2thanhph~nto'.1dQ(x,y).ThongtinhlnhhQccuado'.1nth~ng,duongga'p
khucva m~t(mi~n,vung)duQcclingca'pbdi mQtday cac ditim.Thongtin
topologyl'.1idinhnghlathemca'utruckhac,trongca'utrucnay,cacd:6ituQng
khonggiancolienh~qual'.1ivoinhau.Vi d\lnhu,mQtm~tk~voimQtclinghay
k~voimQtm~tkhac,mQtdinhk~voimQtcling....
E
I. M~ttrai
c
G Clingphai
Mi;itphai .
J
H . Dinh
- Cung
~ NguQchi~ukill d6ngh6
Hinh2.1- M6 hinhwinged-edgetopology
Cac m6i quailh~topologyse t'.1Ocd sd dti ta co thtikhai thacthongtintrenanh
ra'tthu<%nti~n,nhungvi~ct6 chilc, lu'utn1'va C<%Pnh<%tcac thongtin nay l'.1i
thuongphilc t'.1Pva co chi phi cao.Vi d\l, mQtdo'.1nth~ngco thtik~voi nhi~u
do'.1nth~ngkhac.Vi~cmotadanhsachta'tcacaedo'.1nth~ngk~naynSukhong
hQp1:9set6nra'tnhi~uchiphi.Mo hlnhWinged-edgetopologydagiaiquySt6t
va'nd~nay.
10
2.1.1.1. Khainit%mwinged-edge
Winged-edgetopologyla m~tph~nthie'tye'ucuamohlnhdu lit%uVPF. Chilc
nangchinhcuawinged-edgetopologyla clingca'pm6iquanht%topologycua
m~nghtaicacdiSm,cacduongvacacm~t.Khi noide'nthongtintopology,tase
gQicacduongIa caccling.Hlnh2.1mota so bQcachbiSu di~nthongtin
topologycuamohlnhWinged-edge.Nhutasetha'y,cachtie'pc~ncuamohlnh
Winged-edgechophepbiSudi~ncacthongtin topologyd~ydunhungkhong
qua philc t~p.
2.1.1.2. Cacthanhph~ncuawinged-edge
Winged-edgetopologyd~trQngtamvaocaccling.VOim6icling,cacthongtin
topologydu</cmotabdi3 thanhph~ndSclingca'ptinhlienke'tgiuacacdlnh,
clingvam~tvaiclingnay.Tuytheoca'ptopologycacthongtinnaycothSdu</c
motakhacnhau.Nhudu</cthShit%ntrongHlnh2.1,cacthongtindlnh,clingva
m~tlien quanchom6iclingdu</cdinhnghiamQtcachtomHitnhusau[19],[20]:
. Thongtin dinhlienquan:M6i clingsechilamQttruongdlnhd~uvamQt
truongdlnhcu6i.Thongtintopologynaydu</cdungdSdinhnghiahuang
cuacling(ne'uc~n).
. Thongtin cunglien quan:cacclingtrai va phain6i mQtclingvai cac
clingk~no. Clingphaila clingd~utienn6i vao dlnhcu6itheochi~u
ngu</chi~ukimd6ngh6.Clingtdi Ia clingd~utienn6i vaodinhd~u
theochi~ungu</cchi~ukimd6ngh6.
. Thongtin m~tlien quan(chidu</cap dlJngchotopologyca'p3):m6i
clingsecom~traivam~tphai.M~ttraivam~tphaidu</cdinhnghiachi
b~nghuangcuaclingtuytheovi trituongd6icuam~tsovaicling.Thong
tinnaychophepmQtclingbie'tdu</ccacm~tk~vaino.
11
Theocachbi6udi~nnay,d6 hilI duthongtintopologycuamQtnodehaymQt
cling,tachiphaihilI trumQtclingd~utienk~voinodevaclingd~u,clingcu6i
k~voiclingdangxet.Tti d6,l~ntheochi~uhilItnl,tac6th6hoantoantruyxutt
cacthongtinconl:;tikhongmtykh6khan.
2.1.2. Cac captopologytrongcdsll dillifU
Bang2.1.M6 ta t6ngquatcaeca'ptopology
Do co sddu li~uduQcthie'tke'theod:;tngtopologynensod6 cacd6i tuQngcosd
trongco sd du li~uphl,lthuQcvao ctp dQtopologytu'ongung.Ta c6 th6dinh
nghla3ctp topologyd6motamucdQbi6udi~nquailh~giuacacd6ituQng.£)6
r:)1,-
.
~
.
,-:~-l~-:-
.
I r~.
.
.
;:"I>:~
l
ItJn.I'\rI. '- ,~n '_I'
I
T
$!4~" '\\)~
"~1 '1/'
I
-
O-~(H! ~9'~ "1.J.U ,- I
Nodeth\fc Cacclingchigiao
3 ITopology th vanode nhaut'.tinode.Cac
hotn lienke't, mtkh6ngch6nglp
totn. cling, lennhau,tt d cac
mt. mt phubettOlllbe). 0
£>6thi Nodeth\fe Cacclingvanode
phltng th, nodelien khiduQcchieulen
2 I (Planar ke'tva mt phltngcaccling
graph) Cling. chigiaonhaut'.ti
node.
I
Node th\fe
£>?6thi I th!, ode lien I Cacclingc6th giao1 I tong quat ket va nhau.
Cling.
I
Tp hQpcacnode
KhongI Caenode
thvcth vacaccling.
0 I tapa th\feth, Cacclingchic6
cling. danhsachcactQade)
makh6ngc6dinh
0
du va dinhcu6i
12
dongian,tadanhs6cacctp topologytu0 (khongchli'athongtin topo)de'n3
(ctptopologycaonhtt).
2.1.2.1. Mo tachitie'tungctp topology
Hlnh2.2motaquailh~giuacacd6ituQngtrongCSDL khongchli'acacthongtin
topology:
Node Ghichu:
[
(
Bangcosa
CQthlnhhQc
+
Chua
mob 2.2.Topologyca'p0
(j ctp dQtopologynay,tachi quailHimde'nSvhi~nthima khongquailtamde'n
svlienquailtopogiuacacd6ituQngtrenanh.Dodo,cacnodevaclingchiduQc
bi~udi€n thongquacacto<:1dQ.
Vi~cc:%pnh:%tva b6 sungthongtin clingnhuchiphihi~nthicacduli~ulo<:1inay
rtt thtp. Bu l<:1i,cac thongtin co th~nit trichtu chungkhongnhi~u.Topology
ctp0 phuhQpvoi cacduli~un~n,mangthu~ntuytinhhi~nthi,it nhuc~utruy
vtn. Du li~ulo<:1inayxutthi~ntrongnhi€u li'ngdl;mgdongian,khongchuyen
sau.
(j ctp 1va2,cacthongtinv€ m6iquailh~topogiuacacclingvanodeseduQc
quailtam.Mo hlnhWinged-edgeduQcapd1;mgd day.Nhudfftrlnhbayd tren,
tachi c~nIttuclingd~u,clingcu6id6ivoi mQtclingva clingd~ud6ivoi mQt
nodela dud~truyxuttcacthongtinconl<:1i.
Hinh 2.3mo taquail h~ giua cac d6i tuQngtrongCSDL chli'acac thongtin
topologyctp 1va2:
13
Cling ~ ""/ Cu~g""'" GaU >
~ungphai >
>~ungtrai
~Oded[U>~
~Ode cu6i~ ,.
Node
lien k€t
( TQaGQ )
I Node Ithu'cth€
~
) ( TQaGQ)(Cac tQaGQ
mob 2.3.Topologydip 1va2.
ffinh2.4mo taquail ht$giua cae d6i tu<;1ngtrongCSDL ehlia cae thongtin
topologyeffpeaonhfft(effp3).
Caedu lit$ulo~inay rfftthongd1;lngtrongcaeling d1;lngth1;l'et€ nhum~nggiao
thong,m~ngeffpdit$n,dit$ntho~i,cffpnude,m~ngmaytinh,...Do quailht$tapa,
vit$ehuyhaythemmQtcling(haymQtnode)sekeotheomQtlo~ts1;l'e?pnh?t
caecling,nodelienquan.
I I Bangcdsa
C ) CQthlnhhQc CQt Topology
+
Chua
Quanh Topology
14
Ring M~t
~
~
~
~ungtnii>
I~Oded'U>~
~ '
Node
lienke't
C TQadQ )
(CactQadQ )
Hioh2.4.Topologyca'p3.
d c1pnay,ngoaicacthongtintoponhuCJc1p 1va 2,thongtin v~ffi?t,ringciing
seduQchtutrll.
t I BangcdsO I I Bang
( ) CQthlnhhQc CQtTopology
+
Chua QuanM Topology
15
Nhii'nglingdvngv€ qUailly d:1tdai,caelingdvngCAD, ...see~nde'ncaedii'
li<$ulo~inay.Caedii'li<$unayclinge:1pd~yduthongtinnh:1tnhtingchiphilu'u
trii'va duytri chungthtiongr:1teao.
Khi quye'tdinhsa dvngdii'li<$uthuQee:1ptopologynaG,taphai din eli VaGnhu
du th1,fete'vabaneh:1teualingdvngd~tranhlangphiva baadamthongtin.
Ph~ntie'prheamotabi~udi~n(d€ nghDevth~euacaee:1utruedii'li<$udung
trongCSDLanh.
2.1.3. Quiuucchungchocaebangdilli~u
Sailday,d~thu~nti<$nehovi<$etrinhbay,tase sadvngmQts6qui tidekhi mota
caeki~udii'li<$u.
Cae ki~u dii'li<$udti<;jevie'ttilt nhti sail:
Bang2.2.Quitioecaeki hi~uehocaekiiu dii li~u
Qui tideki hi<$uehocaedi€u ki<$ntuyehQnhaybiltbuQe:
Bang2.3.Quitioeki hi~udi~uki~nehocaeTrtiong
STT Code Mo ta
1
2
3
0
M
Mn
Tily chQn
Ba:tbuQc
Ba:tbuQcrho ca'
STT Kiiu Mota
1 T,n TextcodQdfiinrhotrudc
2 T,* TextcodQdftituyY
3 F ShortFloatingPoint
4 R Double
5 I Integer
6 B,n Mangkiu double
7 B,* Mangkiu doublecodQdli tily<;
8 D Date/Time
9 NULL GiatIi ceSdinhNULL (kh6ngxetde'n)
16
2.1.4. Mo ta cacdol tlt(lngcdsd
2.1.4.1. Node
Cacnodela cac d6i tu'c;5ngcd sa khongco kich thu'ocdu'c;5cmo ta dS hill tn1'cac
vi trl quail trQng.Khong co ba'tky 2 nodenao co tQadQhoantoantrungnhau.
Co2lo?i node:nodethl;tcth€ (entitynode)vanodelienke't(connectednode).
2.1.4.1.1. Nodethlfcth6(entitynode)
Nodethl;tcthSdu'c;5CdungdSthShil$ncacd6i tu'c;5ngdQcl~p,khongcokich thu'oc
(khongquail tamde'nkich thu'oc)trongthe'gioi thl;tc.Cac nodethl;tcth€ khong
n~mtrencaccling.Thu'ongthlcacnodethl;tcthSchliadl;tngbell trongmQt1u'c;5ng
thongtinphikhonggianhUllichcholingd\lng.
-tub gidi<1jacbmb
. tbanb pb6'
FACE
ENTITY NODE
CONNECTED
NODE
TEXT
EDGE
HInh2.5Band6ranhgioihfmhchinhVi~tNam
Bangduli~umotaca'utruccuad6itu'c;5ngENTITY_NODE cothSdunglamcd
sachocac d6i tu'c;5ngla cacdia danh,khachs?n, chc;5,tru'onghQc,...trongm?ng
giaothong,band6caclo?i,cacvi triquailtrQngtrenthanthSngu'oi,....
Bangnodethl;tcthSg6m2 Tru'ong:mQtkhoachinh(ID) va tQadQcuanode.
Tru'ongFIRST_EDGE co giatri NULL du'c;5CthemvaodSbaodamtinhtu'dng
17
thichvoi d6i tu<Jngnode lien k6t. Truong CONTAINING_FACE chi du<JcslY
dl,mgd6i voi topologyca'p3 d~duytrl quanht$topologyvoi m~tchuanodenay.
Bang2.4.Nodeth1fcth~
1
2
3
4
Ten Kiiu dfi'li~u M6 ta
ID
CONTAINING_FACE
FIRST_EDGE
COORDINATE
I
I
NULL
B
Index
Facemaoi~mnay n~mtrong
TQaoQ
2.1.4.1.2. Nodelien ke't(connectednode)
Caenodelien k6t loon loon n~mt~icaedffucua caecungva co lien k6t
topologyvoi d6i tu<Jngcungtuongung.N6u co nhi~ucunggiaonhaut~imQt
nodelienk6t.Nodenaychihtutrfi'thongtincuamQtcungvanhovaoca'utrue
winged-edgetopologychungtacoth~quan1:9ta'tcacaecungconl~i.
Bang2.5.Nodeli~nk~t
Tuongtl,tnhu d6i tu<Jngnodethl,tcth~,bangnodelien k6t cling g6m2 truong
chinh:khoa chinhva tQadQcua node.TruongCONTAINING_FACE co gia tri
NULL d~baodamsl,ttuongthichvoi node.thl,tcth~.TruongFIRST_EDGE la
khoango~idu<Jcyellcffuchotopologyca'p1vacaeca'pcaohoDd~duytrtm6i
quailht$topologyvoicaecungcochuanodenay.Dayla cungdu<Jcxemla cung
dfiutieDk~voinode.Ta coth~la'yt~ph<Jpcaecungk~voinodelienk6tb~ng
eachlffntheoquailht$topologycuaFIRST_EDGE naychod6nkhi cungdffutieD
xua'thit$nl~i. .
STT Ten Kiiu dfi'Iiu M6 ta OplMan
1 ill I Index M
2 CONTAINING FACE NULL 0
3 FIRST EDGE I Arcid Ml-3
4 COORDINATE B TQaoQ M
18
2.1.4.2. Cling
CacclingduQcxacdinhbdi cacnoded cacd~ucuacling.Saud6cacclingt<;lO
nencaem~t(d6ivaitopologycffp3).Ngoaitrudngnoded~uvanodecu6i,bang
cacclingconc6cacthongtinclingtrai,clingphai,m~trai,m~tphaid~h6trQ
caccffptopologycaohan.Huangcuaclingla huangtunoded~ude'nnodecu6i.
Bangdi1li~umotacffutruccuad6i tuQngEDGE dungchocacclingdudngtrong
h~th6ngcacdudnggiaothong.
Bang2.6.Kiiu dli li~uEDGE fiG tii cung
Bangd6i tuQngclingbaog6m8 trudngb~tbuQcphVthuQcvao cffpdQtopology.
Trudng ID chua chi mvc dong va la kh6a chinh. Trudng node d~u
(START_NODE)va nodecu6i(END_NODE) Ia cackh6ango<;lilien ke'tvai
nodelien ke'tva Ia trudngb~tbuQcd6i vai topologycffp 1-3.M~t trai
(LEFT_FACE) vam~tphai(RIGHT_FACE)la cackh6ango<;lilienke'tvaibang
cacm~t,va cactrudngnay la b~tbuQcchotopologycffp3.TuangtVclingtrai
STT Ten Kiiu di1 Moh! Op/Man
Iiu
1 ID I Index M
2 START NODE I Startnodeid MI-3
3 END NODE I Endnodeid MI-3
4 RIGHT FACE I Idmt ph,H M3
5 LEFT FACE I Id mt tnii M3
6 RIGHT_EDGE I C'.lnhdftutieneua MI-3
START_NODEtheonguQc
chiu kimd5ngh5
7 LEFT_EDGE I C'.lnhdftutieneua MI-3
START_NODEtheongU<;fc
chiu kimd5ngh5
8 . COORDINATES B,* DanhsaehcaetQadQeuacae M
ControlpointseuaARC (k ca
startnodevaendnode)
19
(LEFT_EDGE) va clingphai(RIGHT_EDGE) la cackhoango~ilien ke'tvai
bangcacclingva la truongb~tbuOcchotopologyc1p1-3.TruongcactQadO
cuaclingnayla b~tbuOc.Va d~d~dangtrongvit%cve cacclingduong,truong
danhsachcactQadOcobaog6mcanoded~uvanodecu6i.Do v~ydOdait6i
thi~ucuadanhsachcactQadOcuaclingla 2.
. Thongtin v~nodelien quan:la cackhoango~ide'nbangnodelienke't
vaduQcyetic~ud6ivai topologyc1p1vacacc1pcaobond~duytrlcac
quanht%topogiuanodelienke'tva cling.Noded~uchirad~ucuacling,
vaquanht%giuanoded~uvanodecu6ichidinhhuangcuacling.
. Thongtin cunglien quan:clingtraiva phaiduQcyetic~uchocacc1p
topology1,2va 3thie'tl~pst;(lienke'tgiuanovacacclingIanc~ntrong
c1utrucwinged-edgetopology.Ne'uchungtas~pxe'pcacclingg?Pnhau
t~inodecu6itheothlitt;(nguQchi€u kimd6ngh6thlclingphaicuacling
dangxetsela clingd~utieng?Pphaiva tuongtt;(clingtraila clingd~u
tientrongs6cacclingxungquanhnoded~u.
. Thongtinm~tlienquan:khicothongtinv€ m?tthltruongLEFT_FACE
va RIGHT_FACE duQcthemvao bangcac cling.Dt;(avaohuangcua
clingtacoth~themvaocactruongthongtinv€ m?t.
2.1.4.3. M?t
M?t duQcdinhnghlanhula mOtvungm?tphingduQcbaoquanhbdimOthay
nhi€u cling.T1tcacacm?tduQcdinhnghlabdimOthaynhi€u ring(vang).M6i
ringla mOtdagiacdonkhongtt;(c~t.T~phQpcacringt~onenbiencuam?t.
M6i ringduQcgallchomOtmas6ID va duQcmotathongquamOtthamchie'u
de'nclingd~utiencuaring.Cacclingcanl~icuaringduQcxacdinhb~ngcach
di chuy~ndQctheocacclinglientie'ptheomOtchi€u naodo saochom?tluon
20
luonn~mv~mQtphiasovoi caeclingnayehode'nkhi quayI<;1iclingd.1u.Ta'tea
caem~tchi coduynha'tmQtringbaangoai(outerring).MQtm~tcokhi conhi~u
ringbelltrong(innerring)d6th6hi~ncaevungthuQev~caem~tkhae.Caering
trongva ringbaangoaila khonggiaonhau.sO'lt1'<;5ngcaeringtrangeuam~t
khongbi gioi h<;1n.MQt ring n~mtrongmQtring khae ma ring nay du<;5Cehua
trong1 m~t(vi d\l mQteai h6 trendaoma daonay n~mtrongmQteaih6 khae
Ionbon)khongcoquanh~topologyvoi m~tbenngoai(eaih6 IOn).DO'itu<;5ng
m~tdu<;5eeaid~tnhusan:
Bangcaemijt:bangthongtinm~tg6m2truongbeltbuQetrongdotruongill la
khoaehinhva truongRING_PTR trode'nringbaangoaitrongbangring.Trang
bangcaem~ttacoID=l du<;5edanhriengehom~tngoaieung,chuata'teacae
dO'itU<;5ngtrenanh.Bienchungeuam~tngoaieungvacaem~tkhaet<;10nencae
ringtrongehom~t ngoaieungnay.
Bang2.7.M~t
Bangcaering:bangringehuamQthamehie'ude'nbangclingehotungringeua
m~t.Dongd.1utientrongbangcaeringehom6im~tla ringbaangoaicuam~t
do.Caeringbaangoaidu<;5edinhhuangtheoehi~ukimd6ngh6.M6i ringben
trongco mQtthamehie'ude'nclingd.1utieneuaringdo.Bangcaeringduytrl
mQtmO'iquailh~thutl!ehocaedongeuano.M:lu tind.1utientrongbangring
cuamQtm~tmoi IuonIuonIa ringbaangoaieuam~tdo.Va caem:lutintie'p
theovoi ID euam~tco giatq b~ngvoi ID nayla caeringbell trongeuam~t
nay.
Bangsanmotaea'utrueeuabangcaering.
STT Ten Kiiu dii'Iiu Mota OplMan
1 ID I Index M3
2 RING PTR I Ringid M3
21
Bang2.8.Ring
Caering hentrong
Slf t<;\othanhcacringbaangoaiva bentrongdu'<;1Cquanly bdi caclu~tcua
winged-edgetopology.Themvaodo,VI cacclingkhongdu'<;1cxemn~mtrong
mQtm~tnaodo ma cacclingd ben trongmQtm~tse du'<;1Cxemnhu'la caccling
thuQcring bentrongm~tdo.Cac hinhsauday matamQts6 tru'ongh<;1pd~cbit%t
cuacacringbentrongvaringbaangoai:
mnh2.6.M~ts65dlil1cthi hi~nbllngmQtringddntrongbangcaering.
Tronghinhtrenkhongcoringbentrongcuam~t5matfftcacacclingd~umata
la 1ringduynhfftrongbangcacring.
mnh2.7.M~t5ddl1cthi hi~nbili 2ringtrongbangcaering
Hai m~tbentrongd hinhtrenva clinglienke'tt<;\onenmQtringbentrongva
du'<;1Cmata la mQtringtrongbangcacring.
STT Ten .. Kiu dii'Iiu Mot3 Op/Man
1 ID I Index M3
2 FACE ID I Faceid M3
3 START EDGE I Edgeid M3
22
mnh2.8.Mi)t 5du<j'eth~hi~nb~ng2ringtrongbangcaering
Ringthlihaitrongbangcacringchidinhclingn6ibentrongm(it5.
2.1.4.4. Van ban(text)
VanbanduQcdli d(itnh~mchophepth~hi~ncactencuavung,tencuanode
thl;(cth~,...trenanh(chingh(;ln:HoChiMinhCity).Bangd6i tuQngcosaVan
bang6m3truong:khoachinh(ID),chu6iki tl;(vachu6icactade>matheodo
dongvanbanseduQchi~nthi.Tuynhienngoaira coth~co themcactruong
ph\!chobitt cacthongtinv€ mall sitc,fontchu,kich thuacchu,...
Chu6itade>dungd~dinhhuangchodongvanbanphaico it nha't2 c(iptade>.
Cacki tl;(trongdongvanbanduQcdinhhuangdctheoduongdinhhuangnay.
Bang2.9.Vanban
2.1.4.5. Hlnhchunh~tbaaphunhonha't(MBR)
Bang2.10.mob ehilnh~tbaophiinhi)nhiltMBR
STT Ten Kiiu dO'liu Mota OplMan
1 ID I Index M
2 STRING T,* Textstring M
3 SHAPE LINE B,* Caeto GQ M
STT Ten Kiiu dO'liu Mota OplMan
1 ill I Index M
2 XMIN R TQaGQxnhonhit M
3 YMIN R TQaGQynhonhit M
4 XMAX R TQaGQx IOnnhit M
5 YMAX R TQaGQy IOnnhit M
23
HinhchITnh~tbaaphilnhonhfftduejcxaydt!ngchom6id6i tuejngcdsacling
haym~t.Voi hlnhchITnh~tbaaphilnhonhfftchocacd6ituejngcdsa,vi<%cHm
ki€m haytruyvffncacd6i tuejngsenhanhch6nghdn.
2.1.5. ChimlJckhonggian(spatialindex)
2.1.5.1. Gioi thi<%u
Cactruyvffnkhonggian13.truyvffnmanguoisa dl,lngchidinht~imQtvi tri nao
d6 tren anh va hoi v~mQtthongtin nao d6. U€ trii Wi cho Cali truyvffnnay
chungtac6th€ phaiduy<%ttfftcacacdongtrongbangcacclingd€ Hmxemdong
phuhejpvoi truyvffnduara d€ thongbaa n€u khongc6 mQtcd ch€ t6 chilcdIT
li<%uthichhejp.Chi ml,lckhonggianduejcxay dt!ngd€ giuptangnhanhquatrlnh
Hmki€m thongtin.N6 chophepchungtakhongphai duy<%tquatfftca cacmill
tind€ Hmra thongtin thichhejp.
Ml,lcdich cua chi ml,lCkhonggianla d€ cai thi<%nt6c dQtruyxufftmQtt~pcac
dongnao d6 tu bangcd sa.Voi st!h6 trejcua chi ml,lckhonggian,chungta c6
th€ Hmra d6i tuejngphuhejpmQtcachnhanhch6ngd€ traloi choCalitruyvffn.
2.1.5.2. Xay dt!ngcaychiml,lckhonggian
Cae bu'oeth1jehi~n:
. Chuinboatfftcacacd6ituejngv~t9adQnguyentrongkhoang[0,255]dotQa
dQcuabangchiml,lckhonggianduejctinhdt!atren1byted€ ti€t ki<%mkhong
gianlu'utrITnhungdQchinhxactrongquatrlnhHmki€m vftnkhongbi anh
huangIOn.Do v~ycactQadQkhi duejclu'utrongbangchiml,lckhonggian
duejctinhtheocongthilcsau:
Tinhmin,maxla tQadQnhonhfftvaIonnhfftcuatfftcacactQadQlienquail
d€n cacd6ituejngcfinchuy€nd6i.
24
D6i voi c~p(Xmin,Ymin)cuaMBR tala'yph~nnguyen:
[
Coordinate~mill x 255
]max-mm
(2.1)
D6i voi c~p(xmax,Ymax)tala'yph~nnguyen:
[
Coordinate~mill x 255
]
+1
max-ITlln (2.2)
Chzij: Ntu gia tri cuacongthuc(2.2)la 256,gall l<,lithanh255
/'" '\
Cell 1
Cell 3
0 /'" '" '\
Cell 15 Cell 14 Cell 13 Cell 12 Cell 11 Cell 10 Cell 9 Cell 8
moh 2.9.Mo hlohdiy chimQckhooggiao
25
. Dinh gia tri cuakich thu'ocbucket:Ia solu'<;1ngtoi dacacdoi tu'<;1ngn~mtrong
1cell (d€ nghi:bucket=8)
. Cell band<1u1ahinhvuong256x256(0..255)
. Ne'ucell co solu'<;1ngcacdoi tu'<;1ngvu'<;1tquabucketthi cell du'<;1ctie'pwc chia
ra
QuiHieehianhlisau:
+ Luan phien chia cell thanh2 ph<1ntheochi€u dQCva chi€u ngang(nhu'
Hinh 2.9).
+ Nhungdoi tu'<;1ngnaogiaovoi du'ongphanchiase du'<;1C1u'uacell chao
+ Cac doi tu'<;1ngkhacdu'<;1cphanphoi vao cell traihay cell phaituytheovi
tri cuano voi 2 ph<1ndii du'<;1Cchia:trai ho~ctrense vao cell trai conphai
ho~cdu'oisevaocellphai(xemHinh2.9phiatren).
. T6 chilc caccell t<;todu'<;1cthanhcaynhiphantill kie'mvoi m6i0 1amQtnode
trencay,hai nhanhtraiphai tu'dngling voi caccell thuQcph<1nbell traiho~c
phai(trenho~cdu'oi)cuacelldangxet.
Voi ca'utruc ChIml.;lckhonggian nhu'tren, chi phi till kie'mse vao khoang
O(1og2n),voi n 1at6ngsodoi tu'<;1ngtrenanh.
Doi voi m6i lo<;tidoi tu'<;1ngcdsa nhu'node,cling,du'ongchungta co thSxay
dlfngffiQtfile ChIml.;lckhonggianchochung.Voi slf t6nt<;ticuafile ChIml.;lc
khonggian,vit$ctruyva'nsenhanhchonghdnnhi€u.
Chziv: M~cdti chungtadinhra bucket-size=8 nhu'ngviin t6nt<;tinhi€u cell co
solu'8Ia dovi tricacdoitu'<;1ngnayn~mngaytren
26
du'ongphancachkhichiacellthanhcacca"pdQnhobon.Va dayclingchinhla
mQtnhu'<;1Cdi€m cuacaychIml;!ckhonggian.
2.1.6. Mf)t vi d,!vi vifCtfJ-Ociiychi m,!ckhonggian
B€ de hlnh dungbon,taxet mQtvi dl;!Cl;!th€. Gia sll'co mQtdanhsachcacd6i
tu'<;1ngvdi cactQadQMBR cuachungchotrongbangdu'diday:
Bang2.11.BangMBR euacaedoltu'qngdin ehuy€nd6i
Ch~ngh~n,taco c~pmillvamaxtu'onglingla (-5,50)va (0,55).Khi do,sau
khidu'<;1capd\lngcongthlic:
=
[
Xmin+5 x 255
]
;
Xmin 0+5
-
[
Ymin- 50x 255
]Ymin- 55- 50
PrimitiveIds Xl (deg) YI (deg) X2(deg) Y2(deg)
2 -5.00 54.63 -3.57 55.00
3 -5.00 52.00 -2.74 55.00
4 -5.00 54.91 -4.99 54.94
5 -5.00 54.76 -4.99 54.77
6 -4.80 54.06 -4.31 54.42
7 -3.28 54.05 -3.17 54.15
8 -0.71 53.54 0 53.74
9 -0.57 53.68 -0.53 53.69
10 -4.60 53.13 -4.05 53.43
11 -4.71 53.24 -4.56 53.33
12 -4.80 52.75 -4.78 52.77
13 -5.00 50.53 -2.35 51.82
14 -4.71 51.63 -4.68 51.65
15 -4.68 51.16 -4.65 51.20
16 -1.03 50.78 -0.95 50.84
17 -1.59 50.58 -1.08 50.77
18 -1.99 50.69 -1.96 50.70
19 -5.00 50.16 -4.99 50.17
27
-
[
Xmax +5x255
]
+1 ;
Xmax- 0+5
-
[
Ymax - 50x 255
]
+1
Ymax- 55- 50
tadu'<;febangcaeMBR dfi du'<;feehuy~nd6i phuh<;fpvoi ht%tQadQeuabangchi
five kh6nggian:
Bang2.12.BangMBR cuacaedoltu'Q'ngsaukhidu'Q'cchuyind6i
Cae d6i tu'<;fngtrongbang tren du'<;fev l<:litren ht%tQadQnguyen [O..255xO..255]
nhu'sau:
PrimitiveID Xl..... YI Xz Yz
2 0 236 74 255
3 0 102 116 255
4 0 250 1 252
5 0 242 1 244
6 10 207 36 226
7 87 206 94 212
8 218 180 255 191
9 225 187 228 189
10 20 159 49 175
11 14 165 23 170
12 9 140 12 142
13 0 27 136 93
14 14 83 17 85
15 16 59 18 62
16 202- 39 207 43
17 173 29 200 40
18 153 35 155 36
19 0 8 1 9
28
0 32 64 96 128 160 192 224 255
192
128
mob 2.10.Vi tri caeMBR cuacaed6itu«1ngtrongkhungtQadQnguyen255x255
Do s6 luQngd6i tuQnghi~nt~i=18>buckeCsizenencacd6i tuQngtrense
duQcphanchianhusail:
29
0 32 64 96 128 160 192 224 255
128
mob 2.13. Chia cell dQc va ngang
Chia caccell thanhcaccellconIffn hi<;ittheochi~udQCva ngangnhuhinhve
tren.M6i Iffnchia,chungtasexemxets61u<;ingcacd6itu<;ingtrongcellchad@
coquye"tdinhtie"ptvcchiahaykhong.Saildatila Iffnchiadffulien,vai duong
phanchiala duongdQcketulIenxu6ngduai.
30
0 32 64 96 128 160 192 224 255
128
192
mnh 2.11. Chi a ceIlliin diiu tU~n
Trong Iffn chia cell dffutien,d6i tuQng13n~md ca:tngangdudngphanchia
thingdungdovay d6i tuQng13phiiithuQccell 1 (cellg6c).Con l~icacd6i
tuQng8,9,16,17va 18duQcduaxu6ngcell2vaconl~icacd6ituQng2,3,4,5,
6,7,10,11,12,14,15va 19duQcduaxu6ngcell3.
Nhungdo so'luQngcac d6i tuQngtrongcell 3 > 8 (bucket)nen cell 3 dU<;fCchia
xu6ngca'pnho bon. Trang qua trlnhchia cell 3 d6i tU<;fng13 n~mtren dudng
31
phanchianenduQcgiul<:1ia cell3.Dov~ytada:co cacd6ituQngtrongcell 1,
cell2vacell3nhuhlnhvesau:
0 32 64 96 128 160 192 224 255
255
mob 2.12. CellI
32
0 32 64 96 128 160 192 224 255
64
255
224
192
160
128
96
32
0
Cell 3 Cell 2
Hinh2.13.CacdolttiQngdtiQcphftnchiavaocell2vacell3
Saukhi phanchial~n2, taco cell 4, cell 5 r6ng,va khi do cell 6 co cacd6i
tu<;Jng:2,4,5,6,7, 10,11,12;conl'.licell 7 co cacd6i tu<;Jng14,15va 19.
Caccell 4, cell 5, cell 6, vacell 7 du<;Jcmatitnhuhlnhsau:
33
128
. Cell7 Cell5
(r6ng)
32
19~
0
mnh2.14.Liin chiacellthli 2.
Saukhiphanchiacell xongtaco:
. CellI: 13 . Cell 4&5:r6ng
. Cell 2:8,9,16,17,18 . Cell 6:2,4,5,6,7, 10,11,12
. Cell3:3 . Cell 7: 14,15,19
0 32 64 96 128 160 192 224 255
i I I
CD
224
0--
192---1 Cell6 I Cell 4
(r6ng)
34
2.2. Tq,odilli~uanhvector
Cacduli~uhinhanhc6th6du'<;5Cthuth~ptunhi~ungu6nkhacnhau.C6th6d6
labucanhduQcquetvaotumayquet,la bucanhchvpbdimayanhs6,hayanh
duQct(;lotntctie'ptrongmaytinhthongquamQtcongcvph~nm~mnaod6.Tru
nhunganht(;lOtn!ctie'ptrangmaytinh,das6cacngu6nduli~uanhla duli~u
d(;lngbitmap.Cacduli~unaygiauthongtinnhungthuongc6klchthuocr1tIOn
var1tkh6truyv1nthongtinhamchuatrenanh.Vi v~y,nhuc~ut(;lOl~pvalUll
trucacduli~uanhd(;lngvectorla r1tIon.
Nhudatrinhbayd tren,mQttrongcacmvctieucualu~nannayla nghienCUll
cacthu~troanhi~uquat(;lOl~pduli~uanhvectorvoi cacthongtin topology.
Trangmvcnay,chungtoisetrinhbayv~mQts6ke'tquanghienCUlllienquail
cte'nv1nd~vilaneu.
2.2.1. Vectorhodanh bitmap
Quatrinht(;lOl~panhvectortu anhbitmapla mQtquatrinhg6mnhi~ucong
do(;ln,ba:td~ututi~nxli'lyd6lo(;libobotthongtinkhongc~nthie't,de'nnhiphan
hoaanh (c6 lUll l(;licacthongtin c~nthie'tv~mall sa:c,tinhch1tcac d6i tuQng
trenanh), lam manhduongbien hay trichbien (tuy nhu c~u),vectorhoa,c~p
nh~thongtinthuQctinhcacd6i tuQng,h~uxli'ly, ...
Trangph~nnay,d@dongianhoavanh1nm(;lnhtrQngtam,chungWisechiquail
tamde'nhaicongdo(;lnla lammanhva vectorhoa.Ta giasli'dingd~uvaola
mQtanhnhiphan.Cacdi6mn~nc6giatri0,concacdi6mthuQc acd6ituQng
?
c6 gia tri 1.d day,chungtachuye'uquailtamde'nvi~cvectorhoacacduong
biencuacacd6i tuQng,phathi~ncacdi@mgiaonhau(dayla mQttrangcac
thongtinr1tquailtrQngtrangquatrinhxay dl;ingthongtin topologyd buocsail).
35
Trangchuang3,chungtoised~c~pde'nmQthuangtie'pc~nkhaccuabaitocin
vectorhoa.
Thu~toanvectorhoaanhg6mcacbuacchinhsail:
Blluc1: Lammanhdvongbien
Blluc2: EJanhMu caegiaodiemvacaediemdaumOt.
Blluc3:Vectorhoa
Sailday,chungta se xemxetcacdi€m quailtrQngcuacacbuactrangthu~t
toan.
2.2.1.1. Lammanhduangbienvadanhda'ucacgiaodi€m
Bai toanlammanhduangbiendU<;5Cra'tnhi~unhatoanhQcclingnhutinhQc
nghienCUll.Da co mQts6thu~toann6i tie'nggiaiquye'tbai toannay.Trang
congtrlnh cua minh, chungWi da dlJ.'atren thu~ntoan Zhang- Suen d€ giai
quye'tbai toancuaminh.Ly dochQnthu~toannayla no ra'tthu~ntit$nchovit$c
ti~nxU'ly cacthongtinco ichlienquailde'nca'utructapa.HanmIa,quaphan
tichky thu~toan,trangquatrlnhlamminh, taco th€ ke'th<;5pvit$cdanhda'u
caedi€m coti~mniingla nodesailnay,clingnhucaithit$ndangk€ ke'tquacua
thu~ttoang6c.
d day,chungWt.sekhongtrlnhbayVaGchitie'tthu~toanlammanh[59],ma
chIbanv~caedi€m ma'uch6tcuaquatrlnhnay.Nhuda bie't,d€ lammanh
duangbientheothu~toanZhang- Suen,nguaitadungcaelQccU'as63x3cho
tru'<;5tquatoanbQanh.T(;lim6idi€m (bien),taphaiquye'tdinhxemcoxoadi€m
nayhaykhongtheoquidc nhusail:
Tittztllngcdban:
Vit$cgiaiquye'tcoxoahaykhongxoa1pixelsechIphVthuQcVaG8pixelIan
c~nvaino.
36
Bonquytdedi quyttdjllhxoahaykhollgxoa1pixel
Quyt~c1:
Pixelp co th€ du<;jcxoane'u1<Ng(P)<7 vdi Ng(P)la so'Hinc~n8 cuap.
Di~uki~nNg(P)>1dambaadi€m d~umutcuad6itu<;jngkhongbi xoa,khong
bibaamono
Di~u ki~n Ng(p)<7dam baa d6i tu<;jngkhong bi d\lc 16 (trong trudngh<;jp
Ng(P)=8)ho~cbaamOllquamuc(trongtrudngh<;jpNg(P)=7).
Quyt~c2:
Pixelp co th€ du<;jcxoane'uchi so'de'm(countingindexhay crossingindex- CI)
cuanob~ng1.
Dinhnghla:Chiso'de'mla so'ngare tupixeldangxet.
Thu~ttoantlmcrossingindex:
Duyetheeehieukimdonghoho~eng!1C;Jeehieukimdongho,gQin If!Iandoidau(tUeIf!soIandoi
giatrj 1 H 0).KhidoCI =n/2
Nhu v~y:CI(P) E {a,1,2,3,4}
Vi d\l:
[ili§ [fEJ1 P
1 1 1
CI=O CI=1 CI=2
§fE [cl1j [£Id
1 1 1 1
CI=2 CI= 3 CI=4
37
ChIc6th€ x6apixelntu CI =1d€ khongphavo tinhlienthongcuad6itu</ng
bandfiu.
Nh~nxet:Ntu chIdungquyt~c1va2 voichi@uquettutrenxu6ngduoivatu
traiquaphaithlkhungxudngchuad vi trimongmu6n.Ngu</cl<,lintu thayd6i
chi@u-quettuduoileutrenvatuphaisangtraithlktt quaclingv~nchuad vi tri
mongmu6nvan6ichungktt quacuahaicachlamnayla khacnhau.
Zhang& SueDdffgiai quyttb~ngcachthvchic$n2 pha:
. Quettheochi@ututrenxu6ngduoi;tutraisangphai.
. Quettheochi@utuduoileutren,tuphaisangtrai.
Quy Hie 3:
~
Trangphathlinha"t,anhsedu</cquettu trenxu6ngduoiva tu traisangphai.
mQtpixel c6th€ du</cx6achIntu thoaca2 di@ukic$n
. C6 itnha't1trongcacIanc~n1,3,5la pixeln@n.
. C6 itnha't1trongcacIancfin3,5,7 la pixeln@n.
Quyt~e4:
H~H
Trangphathli nha't,anhsedu</cquettu duoileu trenva tu phaisangtrai.1
pixelc6 th€ du</cx6achIntu thoaca2 di@ukic$n
. C6itnha't1trongcacIanc~n1,3,7 la pixeln@n.
. C6itnha't1trongcacIancfin1,5,7 la pixeln@n.
Thu~toaDdungntusaullfinduyc$td6itu</ngkhongbi thayd6i.
38
Ne'uchI dungcaclQcnay,chungtaseg~pmQts6 tru'ongh<;jpke'tquakh6ngnhu'
ykhi quail tamde'ngiaodiSm.Trang vi~ct~odli li~uvector,co hai lo~idiSm
quailtrQng:dfiumlii cuamQtc~nh(nodek6 voi mQtc~nhduynhfft)va giao
di6mcuanhi6uhdnhaic~nh.CacdiSmnaycothSd~ctrungb~ngtinhchfftsail
(xemHlnh2.15vaHlnh2.16):
. BiSmdfiumut:comQtlanggi6ngduynhfftla diSmbien.
. GiaodiSm:diSmconhi6uhdn2langgi6ngla diSmbien
~~~~~~~~
mnh2.15.CaetrlionghQ'pg~pdiim dftumut
~~~~~~~~
mnh2.16.M(Jt s6vidQv~caegiaodiim
Voi thu~tto<lng6c,taseg~pmQts6viph~mcactinhchfftrentrongdli li~usail
khi lammanhnhu'tronghlnhdu'oiday:
~ ~~~~~~
mnh2.17.M(Jt s6trlionghQ'pthu~ttoaDg6ekhongxii'Iy t6t
Ta seke'th<;jpthemmQtbu'och~uxli'19sailkhi lammanhdSlo~ibocaediSmvi
ph~mva daubdffucaediSmdfiumlitclingnhu'caegiaodiSm.
2.2.1.2. Vectorboa
Sailbu'oclammanhdu'ongbien,trenanhchIconl~i3 lo~idi6m:(1)n6n,(2)cac
giaodiSm,va (3) caediSmbien. Vi~c vectorboa se du'<;jcth1;1'chi~nlfin lu'<;jttu
mQtgiaodiSmchode'nkhi g~pmQtgiaodiSmkhac.Bo~nn6i haigiaodiSmnay
du'<;jcgia dinhla mQtdu'onggffpkhuc.Vi dl;!sailseminhho~thu~toan:
39
Gia sli'doC;lndn vectorhoala doC;lngtp khucnhutrongHlnh 2.18.Tli anhg6cta
co th€ lty duQccac pixel thuQcdoC;lncin vectorhoa b~ngcachliD tUmQtdiu
milt(ho~cgiaodi€m) chode'nkhi g~pmQtgiaodi€m (ho~cmQtdiu milt)khac.
Duongdn vectorhoaL
""
""
""
""
""
""
"" Duongvectorgiadiilhband~uLo
Hinh2.18.Duongdin vectorboasovOiduonggiadjnh.
Ban diu, ta gia dinhduonggtp khuc cin vectorhoa leimQtdoC;lnth~ng(Hlnh
2.18).Xac dinhsai s6theocongthuc:
Id(x, y,Lo)
a= (yo,Y)=L
ILol
trongd6d(x,y,Lo)la khoangcachtli di€m (x,y)de'nduongLa.Ne'ua nh6hon
nguongE,doC;lngiadinhseduQcchQnlamduongvectorhoa.TruonghQpnguQc
IC;li,ta chQndi€m xa nhtt M d€ chia doC;lncin vectorhoa ra lam 2 doC;ln.Ta se
vectorhoahaidoC;lnayriengre chode'nkhi hoanttt congvit$c
Duongdn vectorhoa
". ....
\ ""
\. ""
\ ........
Duongvectorgiadinhband~u
....
Hinh2.19.Xac djnhditfmxanhilt
40
Trangvi dVcuachungta,sailkhi xacdinhdi~mxa nha't(Hlnh2.19),tachia
do(;lnband§u thanhhaido(;ln,trongd6do<;lnd§ukh6ngc:1nxettie"p.Ap dvng
tie"pqui trlnh tren cho do<;lnsail ta dU<;5c:
Ph~ndn xernxettie'p
---------------
Duongvectorgiadtnh
Hinh2.20.PMn do~nbandftuthanhhaiphftn
Sailkhi phanchia,cac do<;lnh~ndU<;5ctrungvdi do(;lngia dinh (sai s6 nhobon
E).De"ndaythu~toanvectorboake"thuc.
-------------
Duongvectorgiadtnh
Hinh2.21.Ke'tquavectorboa
Ta co thu~toansail: /
Thu~ttoaD2.1:Vectorboaanh
Buac1: ChQnmQtnode(daumOthaygiaodiem)chl1axiJly P1.
Buac2: Lantheocacdiembien,ghinh~nI~iVaGdanhsachL chodenkhig~pnodeP2khac.
Buac3: ChQndl1angP1P2lamdl1ongiadinhbandau.
Buac4: Xacdinha vadiemxanha'tM.
Buac5: Neua<E chQnP1P2lam kef qua.
Ngl1t;jcI~ichiaP1P2lamhaiphanP1MvaMP2.XiJly P1MvaMP2nhLfdalamvdjP1P2.
Buac6: GhinMn cacthongtintopodlnhc~nh.
Buac7: Neuconnodechl1axiJly thlquayI~jBl1dc1.
41
Nh:;inxet:
Thu~tmin2.1seho~tdQngra't6tne'ucaeduongtrenlmhc~nvectorhoakhong
quaphuct~p.Tuynhien,trongtruonghQpt6ngquat,thu~toannaykhongcho
ke'tquachinhxac(xemHinh 2.22).
Tuynhien,ne'udli li~uc~nvectorhoala caedli li~uband6 (giaothong,dia
chinh,giaithua,...)haybanve ky thu~thlthu~toannayselamvi~cra'thi~u
quaVI tlnhcha'tcuacaed6i tuQngduongtrencaelo~idli li~unay.
------
mnh2.22.TruonghQpthu~to!ln2.1khOnglamvil$ct6t
BS lamvi~cvoicaedli li~ut6ngquathall,chungtoida:xaydV'ngthu~ttoan2.2
nhusau:
Thu~ito!ln2.2:Vectorboaanhcaibien
Buoc1: ChQnmQtnode(daumOthaygiaodi~m)ehuaxvIy P1.
. Buoc2: Ghinh~nP1la nodedangxet.i =O.LuuP1vaoL[i++].
Buoc3: ChQnM la di~mbienkeP1ehuaxet.
NeuehQnduQethldanhdauM daxet.P =M.
NguQel<;Ii:ehuy~nsangBuoe8.
Buoc4:ChQnP2ladi~mkeP.
Buoc5: NeuP2la mQtnodethl
L[i++]=P2.LuuL vaofileketquit
C~pnh~tcaethongtintapadlnh- e<;lnhlienquan.'"
Quayl<;IiBuoe2.
Buoc6: Neud(M,P1P2)<d(P,P1P2)thlM =P;//C~pnh~tM M luonladi~mxado<;lnP1P2nha't.
Buoc7: Neukhoangeachd(M,P1P2)>€ thl:
L[i++]=M; P1=M; M =P; P =P2.
Quayl<;IiBuoe4.
Buoc8: NeuconnodeehliaxvIythlquayl<;IiBlioe1.
42
Thu~tocin2.1eungnhuThu~ttocin2.2ehophepchungtavectorhocit:1tea cae
duongbien k€ voi it nh:1tfiN node.Tuy nhien,co thSxay ra trudnghQptrong
anhd~uV?lOco caekhuyen(ring)nhutronghlnh.Saukhi ap d\lngthu~troan
vectorboacaediSmbienconl~itrenanheh~ech~nsethuQcmQtkhuyennao
do.TrangtrudnghQpnay,taphaicocacxli'19rieng.eachlamddngiannh:1tla
chQnmQtdiSmb:1tky thuQckhuyennaylamnoder6i apd\lngthu~troantren
voimN chuthit%uchlnhehophuhQp.
Blnh 2.23.Truonghllpthu~tmin2.1khonglamvi<;ct6t
SaukhivectorboahoanehlnhroanbQanh.MQtvit%e~nphailamla phaixae
dinhcacm~trungnhunhG'ngthongtintopoeuano.Tht;fechfftcuabairoanla
Hmcaevungbigioih~nbdicaedudngkhepkint~obdicacdudngvectordfftlm
duQc.Do caethongtintopodlnh- c~nhdffduQcc~pnh~td~ydud buoetruoe,
taco thSxaedinhroanbQcaem~tva nhG'ngthongtin lien quailhoanroanW
dQng.
43
2.2.2. TimphOngiaoclla hai dagiacbittky
TImgiaohaidagiacIa mQttrongnhfi'ngb~titoanco sd cuahinhhQctinhtoanva
co nhi~uling dt,mgtrongcac Uinhvvc khac nhaucua d6 ho(;lmay tinh, CAD,
GIS, Bai toannaycothSdU<;5CxemxetdudihaigocdQkhacnhau:
. ChIxetcacdagiac16i,ho~c
. Co it nhfftmQtdagiackhong16i(cothS16m,cothSchuacac16vdinhi~u
mucdQ).
Caethu~toanthuQcd(;lngd~utien da dU<;5Cbie'tde'nnhi~uva tuongd6i dS cai
o~t.M~tkhac,vfin con thie'ucac thu~ttoannhanh,m(;lnhgiup giai quye'tbai
roantimgiaocuahaidagiact6ngquat.Ngaycatrongcacph~nm~mCAD, GIS
m(;lnhtavfincothStimthffy16ikhithvchi~ncacthaotic Io(;linay.Nhi~utic gia
oad~nghiphuongan chiacac da giacc~nxli'19thanhcacda giac16icon
(phuongphapthongdt,mgnhfftIa chiathanhcactamgiac [3]ho~ccachinh
thang)r6i xli'19cacmanhnayriengbi~t.Tuynhien,trongcaclingdt,mgthvcte'
chingh(;lntrongIanhvvctdicdia,GIS, y tudngnayduangnhukhongphilh<;5p
I~mdoHnhdad(;lngva phuct(;lpcuadfi'Ii~u.VI v~y,chungtoi dax<1ydvngmQt
thu~toandu nhanhdS giai quye'tbai toanHmgiao hai da giac vdi cac rang
buQcsail:dfi'Ii~uvaGphaiIa cacdagiacbfftky dU<;5cdinhnghlat6t,nghlaIa
khongchffpnh~ncacdagiactv cAt,cacdinhcuadagiacdu<;5cchotheochi~u
ngU<;5cchi~ukimd6ngh6,nghlaIa khidi dQctheoduangbiendagiactheotrlnh
tvtudinhd~ude'ndinhcu6i,ph~nbelltrongdagiacIuondphiaraytrai.
Trudetien,tahayth6ngnhfftmQtsO'thu~tngfi'[39],[41]:
. MQt loop biSu diSn bien cua mQtda giac baa g6mmQtchu6icac c(;lnhda
giacdinhhuangkhepkin.M6i dagiaccodungmQtloop.
44
. MQtring bi~udi€n mQt16trongdagiac.C6 th~c6 nhi~u16hoi;ickhongc6 16
naGtrongmQtdagiac.Cacringc6th~l6ngnhaubaanhieucfiptuyy.
. MQtsweeplinela duongth~ngsongsongVGitn,lctung.
. MQtscanlineIa duongth~ngsongsongVGitn,lchoanh.
2.2.2.1. So luQcv~thu~troan
Thu~troan cua chungWi d1.fatren y tudngband~ucua thu~troanWeiler-
Atherton.Thu~troannayxacdinhph~ngiaohaidagiackhongt1.fc~tbfitkybaa
g6m3buGCchinh[30]:
1. TIm cacgiaodi~mgiuacacq.nhcua2 dagiac.MQtthu~troanlingdl;mg
sweeplinedffduQcchungWi xayd1.fngd~th1.fchi~ncongvi~cnay.Thu~t
roanseduQctrlnhbaytrongph~n2.2.2.2.
2. Sailkhi dffxacdinhduQccacgiaodi~m,mOts6thongtin "luanchuyin"b6
sungseduQcthemVaGcacgiaodi~md~ph1,lcV1,lchobuGCcu6icuathu~t
roan(ph~n2.2.2.3).
3. Trongph~ncu6i,thu~troand1.fatrencac du li~uclingcfipbdi haibuGCtruGc
va xay d1.fngda giac giaob~ngcach "bztac"luan phien qual'.li trenhai da
giactu giaodi~mnayde'ngiaodi~mkhac.
2.2.2.2. Xacdinhcacgiaodi~m
Vi~ctinhroancacgiaodi~mchinhla congvi~ckh6khannhfittrongthu~troan.
N6 c6 dQphuct'.lPtinhroankhacao.Ne'udungphuongphapbrute-forcedQ
phlict'.lPsela O(nxm),trongd6n vaml~nluQtIa s6dinhcuahaidagiac.Th~t
maym~n,n6ichung,s6giaodi~mgiuahaidagiacnhohonnXmrfitnhi~u.Tuy
nhien, trongmOts6 truonghQprfit hie'm,nguongO(nxm)khongth~vuQtqua
45
(xemffinh2.24).Va'nd~la c~ntlmramQtphuongphapxacdinhta'tca.cacgiao
di€mvdidQphlict~ptrungblnhnhohonnhi~usovdiO(nxm).
Hlnh2.24.86giaodiim giiiacaec~nhcuahaidagiac Iii n x m
Vi dt;l,trongHlnh2.25,dagiacP co 7 va dagiacQ co 5 dinh.Trongphuong
phapbrute-force,thu~troansephaiki€m traca 35c~pc~nhtrongkhichico 8
giaodi€m. Se ra'tto'tne'ucomQtthu~troan"thongminh"d€ chichuy de'ncac
e~pe~nheokhananggiaonhau.
Vdi mt;lcdichnay, chungWi dff dungthu~troansweepline.Vit$esli'dt;lngeae
sweeplinera'tthongdt;lngtrongvit$cgiai cac bai roancuahlnhhQctinhroanva
d6ho~(vi dt;l,thu~troantomatiscanline,khli'm~tkhua't,...).Ta tudngtu<;5ng
sweeplines tru<;5ttrenm~tphAngtu-00 de'n+00.No ehidungl~it~imQtsO'di€m
d~cbit$t- t~icacdinhcuadagiac- t~ido thu~troantht;rchit$ncaexli'ly c~n
thie't(xacdinht~pc~nhlienquail,xacdinhgiaodi€m, ...).Trongbairoantlm
giaodi€m giuacacc~nhcuadagiae,taquailHimde'ncacc~nhbi sweepline
"xuyenqua"t~ithai di€m quailsat (haid~ucuac~nhn~md hai phiacua
sweepline).Chungla caclingcli'viento't rhovit$ctlmgiaodi€m. R6 rang,t~p
eaee~nhbi "xuyenqua"bdi sweeplinechi bi thayd6i t~ieaedinheuadagiac.
Thongtinnaydu<;5Cxemnhula tr~ngthaicuasweepline.Co mQtphuonganra't
hit$uquad€ giaibai roantlmta'tca giaodi€m giuacacdo~nthAngtrenm~t
phAngla dunghai cayAVL [7]du<;5Ctrlnhbay trong[3]va [43].Ta co th€ dung
46
phuongan nay d~giai bai toantlm giao da giac voi mQtchlithi<%uchlnh.Tuy
nhien,trongphc.tmvi lu~nvan nay,VImvcdichdongian,chungt6i sa dvngmQt
phuongphapkernhi<%uquahonchutit nhunglc.tid6dd d~thall.
I
I
I
I
I
I
I
I
I
I
I
I
I
I
I
I
I
I
I
I
I
I
I
I
I
I
I
I
vo'
I I
I I
I I
I I
I I
I I
I I
I I
I I
I I
I I
I I
I I
I I
I I
I I
I I
I I
I I
I V8 :
I
I
I
I
I
I
I
IV!
.L..1
50 51 52 53 54 55 56 57 58 59 510 511
~
x
Hinh2.25.Xac djnhcaegiaodiim sO'd~ngsweepline
Gia sa dlnh Vkn~mtrensweeplineSr. Tc.tidlnhnay,hai cc.tnhek,iva ek,jndi no
voi cac dlnhVi va Vj. Ta se xftydvnghai t~pcac cc.tnhdangdU<;1Cxet. T~pSp
chuacaccc.tnhcuadagiacP va t~pSqse chuacaccc.tnhcuadagiacQ. Hinh 2.26
minhhQacactinhhudngco khanangxayra va tase giai quye'tchungb~ngcac
lu~tsan:
Lu~t a: Vj>Vk& Vj>Vk;cc.tnhek,jva ek,jdu<;1cchen vao Sp(VkEP) ho~cSq(VkESq),
Lu~t b: Vj<Vk& Vj<Vk;cc.tnhek,jva ek,jbi loc.tira khoi Sp(VkEP) ho~cSq(VkESq),
Lu~t c: VjVk;them cc.tnhek,jva loc.tiek,jkhoi Sp(VkEP) ho~cSq(VkESq),
Lu~t d: Vj>Vk& Vj<Vk;loc.ticc.tnhek,jva them ek,jvao Sp(VkEP) ho~cSq(VkESq),
Di nhien,coth~xayra truongh<;1pkhinhi~udlnhn~mtrensweepline.Truong
h<;5pnayd6 danggiai quye't,va se dU<;1Cxemxetd ph~ncudicuaph~nnay.
Truoctienchungtahaytimhi~uthu~toan.
47
E>Schophepsweeplinetnt<;1tmill trenm~tph~ng,dlnhcuacacdagiacdU<;1cs~p
thlitv theochi~utangd~ncuahoanhdQ(do sweeplinetru<;1ttu trai sangphai).
Secot6ida12di€m dungcuasweeplinetrongvi dl.lcuachungta(xemHinh
2.25).Tasexemxetthu~ttoanlamvi<$ct'.lim6idi€m naynhuthe'naG:
Sk
a)
Sk
b)
Sk
c)
Sk
c)
mnb2.26.Caevi tri cothi euacaedinhdagiaetrlongdngvOisweepline
Di~mdung1: Di€m dungd~utiencuasweeplinela t'.lidlnhVo(Hinh2.25).
Lu~ta du<;1capdl.lngtrongtruongh<;1pnayva hai c'.lnheO,lva eO,6du<;1CthemVaG
t~pcac c'.lnhdangxet Sp(dochungthuQcdagiacP). T~pSqv~nconr6ngva VI
v~ytakh6ngc~nthvchi<$nvi<$cki€m tratimgiaodi€m.
Sp={eO,l,eO,6},Sq={ }.
Di~mdung 2: sweeplinechuy€n de'ndlnhV6va lu~td du<;1cdung.C'.lnheO,6bi
lo'.liva c'.lnhe6,Sdu<;1CchenVaGSp(V6E P):
Sp={e6,S, eo,d, Sq ={ }.
Di~mdung 3: sweeplinechuy€n de'ndlnhVsva lu~td du<;1cdungmQtl~nnua.
Cact~pSpva Spcogia tri nhusau:
Sp={eS,4, eo,d, Sq= { }.
48
Di~m,dung 4: sweeplinedi de'ndlnhv3va ap dl;lllglu~t a ta them2 c<;lnhmoi
VaGSp:
Sp={e3,2, e3,4, eS,4, eo,d, Sq={}.
Di~mdung 5: sweeplinedi de'ndlnhV7E Q. Dlnh V7k@hai dlnhVsva Vll. Vi
v~y,xua'thi~nkha nangcac c<;lnhe7,Sva e7,llgiaovoi cac c<;lnhthuQcSr' Phep
ki~rntrasausedu'Qcapd1.;lllg:
e7,1l&e3,Z:thli va tlrntha'y1giaodi~rn e7,S&e3,Z: kh6ngthliYmax(e7,S)<Ymin(e3,Z)
e7,1l&e3,4:thli va tlrntha'y1giaodi~rn e7,S&e3,4: kh6ngthliYmax(e7,S)<Ymin(e3,4)
e7,1l&eS,4:thli va tlrntha'y1giaodi~rn e7,S&eS,4: thliva tlrnkh6ngtha'ygiaodi~rn
e7,1l&eO,l: kh6ngthliYmax(eO,l)<Ymin(e7,1l)e7,S&eO,l:kh6ngthli Ymax(eO,l)<Ymin(e7,S)
SaukhikiSmtra,nQidungt~pSpva t~pSqdu'Qc~pnh~tl<;linhu'sau:
Sp={e3,2, e3,4, eS,4, eo,d, Sq={e7,S , e7,1l}.
Di~mdung6: sweeplinede'ndlnbV4va lu~tb du'Qcdung.C<;lnheS,4va c<;lnhe4,3
bi lo<;likhoi Sp:
Sp ={e3,2, eo,d, Sq={e7,S, e7,1d.
De'nday,tadffco thShinhdungcachmathu~toantie'pt1.;1Cth1!chi~n.Bangqua
cacbu'occon l<;li,taxet de'nbu'occu6i cungkhi sweepline d1.;1ngc<;lnhVs.Tr<;lng
thaicuaSpva Sqngaytru'ockhi sweplinech<;lmVsla:
Sp={e2,l, eo,d, Sq={e9,S , e7,s}.
Tqi dlnhVs,apdl,lllglu~tb tadu'Qc:
Sp={e2,l, eo,d, Sq={ }.
DomQttronghai t~pcacc<;lnhdangxettronenr6ng,nenkhongthSt6nt<;lithem
giaodiSm.Ta co thSdungt<;liday.
49
TrongVI dl.;lcua chungta,chi co mQtl~nvi~cgQide'nhamxac dinhgiaodi~m
khongthanhcongoDi nhien,b~ngmQtki~mtra don gian, ta co th~phathi~n
qnh eO,lkhongc~tba"tky c(;lnhnaGthuQcdagiacQ va khongc~nphaichenno
V~lOt~P Sr'
TruonghQpd~cbi~txayrakhi conhi~udinhclingn~mtrensweepline.Hlnh
2.27minhho(;lcactruonghQpcoth@.Ta coth~giaiquye'tchungb~ngcaclu~t
sau:
Hioh2.27.Caetru'ooghqpd~ebi~t
Lu~t e: Ca hai c(;lnhek,iva ek,jbi lO(;likhoi Sp(VkE P) ho~cSq(VkE Sq),
Lu~tf: Thil'tlmgiaodi~mvdi cahai c(;lnhek,iva ek,j;themchungVaGSp(VkE P)
ho~cSq(VkE Sq),
Lu~t g: Thil' tlm giao di~mgiuahai c(;lnhek,iva ek,jvdi cac c(;lnhtrongSq(Vi E P)
ho~cSp(ViE Sq),nhungchi c(;lnhek,iduQcthem VaGt~ptuongling.
Lu~th: Thil'tlmgiaodi~mgiuahaic(;lnhek,jvdi cacc(;lnhtrongSq(ViE P) ho~c
Sp(ViE Sq),nhungno khongduQcthemVaGt~pnaGca.C(;lnhek,ibi xoakhoi t~p
Sp(Vi E P) ho~c Sq (Vi E Sq)
Lu~t i: Thil' tlm giao di~mvdi ca hai c(;lnhek,iva ek,j,nhungkhongthemVaG
danhsach.
I
I
y. I
:\ ) :I'kv'v; : Vi,I I
I I I I
Stc Sj, St St: St
e) 1) g) h) i)
50
2.2.2.3. Themthongtin"luanchuytin"chocacgiaoditim
Trangbuacthli hai cuathu~toan,m6igiaoditimse duQcb6 sungthemcac
thongtinb6trQ.uti minhho~cachthu~ttoancuachungtaxli'lycac16trongda
giae,tathemVaGdagiaeP, Q mQts6l6. Ua giacP co themringRplva Rpl chlia
Rp2,trongkhi Q secO-themringRq.Chu y lacace~nhcuadagiaedffdinhhuang
theoquyt:1eban tay phai (xemHinh 2..28).Ngoai to~dQ,m6i giaoditimtrong
buGenayconchliathemthongtin:
. Vi tri li~nk~(CPp, CPQ ). MQtgiaoditimn~mgiuahai dinhViva Vj (i <j)
seduQcg:1nvai mQte~ps6th\ielam chImvctudnglingvai khoangeach
ehu§'nboatudinhVidenno.Vi trinaysegiupxaedinhnhanhchongcacdinh
n~mgiuahaigiaoditimlien tiep.Bang2.1choth1ygiatri cuacac index
tudnglingvai cacgiaoditim
Bang2.13.Vf tri li~nk~
Giao di6m CPr CPo Giao di6m CPr CPo
a 4.13 18.60 1 12.45 22.21
b 3.85 18.51 j 12.30 14.58
c 2.66 18.21 k 8.83 21.25
d 7.32 22.64 1 1.75 17.16
e 7.21 14.31 m 9.50 14.69
f 2.32 17.74 n 1.66 16.62
g 13.81 14.39 0 1.43 15.36
h 13.63 22.55 P 1.31 14.92
Sl
Hinh2.28.Giaohaidaghicco16
Co baodagiacke'.Gia trinaybi~udi~ndagiacnaGtrendotaseditugiao
di~m-dangxet.Gia sacohaivectora vab; a thuQcdagiacP vab thuQCda
.
giacQ. HamlefCof(a,b) trav~vectornftmv~naam?tphingtraixacdinh
boi vectorIdatronghaivector.Ching h<;tn,trongHlnh2.29,tasephaitiep
t1J.Ctugiaodi~mdi theovectorb,nghlala di theobiencuadagiacQ. Chi~u
cuabuocdi luonthu~ntheochi~ucuacacloopclingnhuring.
IS
J4
a) b)
Hinh2.29.a)Caehrlongdicothi tITm(}tgiaodiim b) Lu~t left_ofCa,b)
Chodengio,tachimoi thaolu~nv~cacgiaodi~m.Tuynhien,coth~xayra
truonghQpkhongt6nt<;tig aodi~m.Nhii'ngtruonghQpnayra'td~giaiquyetVI
chungchico2khanang:
. Hai dagiachoantoankhonggiaonhau
52
. MQtdagiacn~mhoantoantrongdagiackia.
TrangtruanghQpthlinha't,khongt5nt~idagiacgiao.TrangtruanghQpthlihai,
tasedungmQtphepkiSmtrakinhdiSndSbietduQcdagiacnaon~mtrang,da
giacnaon~mngoai.
2.2.2.4. Xacdinhdagiacgiao
Trangph~nnaycuathu~toan,phep"bllde"dQctheobiencacdagiacseduQc
thvchi~n.Vdi ca'utrucdiI li~umdi,hi~uquamachungtadiixaydvngtrongcac
budctrudckerntheocacthongtin"luiinehuyin"diithemvao,congvi~cnayco
thSthlichi~nra'tnhanhva hi~uqua.Ta hay khao saty tudngnay chi tiet hall.
Ta chiadanhsachcac giaodiSmtimduQccungvdi thongtin luan chuySnthanh
3 mangconva hai trongchungduQcsa:pthli tv theovi tri li~nk~CP (Hinh 8),
tu'anglingvdihaidagiac(mangcpr vaCPQ).
Mang
CPcua
dagiac
P
Vi tri
1i~nk~
MangCP
cuada
giacQ
Vi trili~n
k~
Keys
IndexP
IndexQ
Khoa
Hlnh2.30.xe'pd~tdl1li~utheovi trf li~nk~cuacaegiaodiim
T~ithaidiSmba:td~u,tala'ydiSmd~utientlimangKeysvaghinhdno.Taphai
quayl~idiSmxua'tphatnaydScha'mdlitphep"bllde"cuachungta.Tli diSm
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
-
P a n 1 f c b a 1
e d k m -1 J 1 h g -1
1?1 I t I t I
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
e g J m P a n 1 f c b a -1 k 1 h d -1
1\31 I t I
a b c d e f g h 1 i k 1 m n a p
7 6 5 10 9 4 17 16 15 14 11 3 12 2 1 0
11 10 9 16 0 8 1 15 14 2 13 7 3 6 5 4
53
xua'tphat,thu~ttoandi theoda giac xac dinhbeiithongtin "luan chuy€n" cho
de'nkhi g~pgiaodi€m ke'tie'p.Giao di€m nay chinhla di€m ngaybell phai cua
mangs~pthlitt;1'lingvoidagiacmatadangditrendo.Ta'tcaccacc~nhdagiac
n~mgiii'ahaivi tri li~nk~nay,baag6mca cacgiaodi€m sedu'<;1Cdu'avaoda
giacke'tqua.D€ tha'yra thu~toanchophepxacdinhcacc~nhc~ndu'avaoda
giacke'tquaddngiannhu'the'nao,taxettru'ongh<;1pkhiphaitlmcacc~nhn~m
giii'ahaigiaodi€m x vay. Chi co haikhanang:
a) y n~mngayc~nhbellphaix. Trongtru'ongh<;1pnayCP(x)<CP(y)va ta'tca
cacc~nhvoi chimlJcn~mtrongdo~ntUrxl de'nLyJ sedu'<;1cdu'avaodagiac
ke'tqua.
b) Langgi~ngphaicuax trC)de'ny (xemmnh2.30).Ta coCP(x)>CP(y).Cac
c~nhdagiacn~mgiii'ahaigiaodi€m x,y du'<;1Cxacdinhquahaibu'oc:
. Cacc~nhco chimlJci thai: rxl:::;i:::;chimlJccuac~nhcu6icungtrang
loop(ho~cring)
. Caec~nhcochimlJci thoa:chimlJccuac~nhcu6icungtrongloop(ho~c
.
) <.<rIng - L y.
Ten cua di€m li~nk~du'<;1Cdungnhu'khoa trongmangKeys,trongkhi do vi tri
cuadi€m naytrongmangthli tt;1'sedu'<;1Clu'utrii'l~i.B~ngcachnay,ta "nhay"tIT
mQtmangling voi da giac nay sangmQtmangkhac ma khongc~nphai tht;1'c
hi~nvi~ctlmkie'mgl ca.M6i giaodi€m dffdi quase du'<;1Cdaubda'ula "dff
qua".Quatrlnhtie'pdi~nchode'nkhitaquayl~idi€m xua'tphat,nghlala tavila
khepkin dagiac ke'tqua.Trangtru'ongh<;1pcac da giac l6i, khongco 16thl da
giacgiaovila tlmdu'<;1Cchinhla Wi giai. Trangtru'ongh<;1pt6ngquat,giaohaida
giaccoth€ baag6mnhi~udagiacroinhau.Vlly donay,thu~toancuachung
tasetie'ptlJCchode'nkhinaymQigiaodi€m trangmangKeysdu'<;1cdaubda'ula
"dffqua".
S4
D~minhho(;lthu~t toan,tasethvchi~nthaotac "bu'Gc"trencacdagiactrongvi
d\lcuacuachungta (xemHlnh 2.28va Bang 2.13).Giao di~md~utienla di~m
a.Ta da:bitt sephaibu'GCtheodagiacQ nhothongtin "luanchuy~n".Giao
di~ma n~md vi tri s6 11trongmangvi tri li@nk@CPQcuadagiacQ (Hlnh
2.30).K@bellphaicuaa trongmangnaykhongphaila mQtgiaodi~m.Do la
mQtcontrotrod€n giaodi~mk€ cuaa trenloopcuadagiacQ. Theocontro
nay,tath.1ygiaodi~me. B~ngthutl,lCda:mo tad tren,taHmth.1yc(;lnhV14n~m
gifi'ahaigiaodi~mava e.Nhu'v~y,taco:
pnQ ={a,v14, e}.
T(;ligiaodi~me, tanhaysangP. NhomangKeystanh~nth.1ye n~md vi tri9
?
trongmang
CPPcuadagiacP . Trongmangnayphaicuae la d.Ta themdvaodagiack€t
?
qua:
PnQ={a,v14,e,d}.
Bay giGtaquayl(;lidagiacQ. Vi tri cuad la 16trongCPQ. Cu ti€p t\lCnhu'v~y,
tasexay dvngdu'<;5Ck€t quahoanchlnh
2.2.2.5. DQphuct(;lpthu~toan
DQphuct(;lpcuathu~ttoantrongtru'ongh<;5px.1unha'tla O(nxm),trongdo n, m
la s6 dlnh cua cac da giac P va Q. Chi phi nay la do ph~nthunha'tcua thu~t
toan.TrongmQts6 tru'ongh<;5p(xemHlnh 2.24),ta khongth~lamt6thandu'<;5c
doco dungnXmgiaodi~m.May m3:nla trongd(;lidas6 cactru'ongh<;5plingd\mg
thvc t€, s6 lu'<;5nggiao di~mit han nhi@u.Ngu'oita da:chungminhdng, thu~t
toansweeplinesa d\lngca'utrucdfi'li~ucayAVL co dQphuct(;lpO((k+I)logk),
trongdok la t6ngs6dlnhcuacacdagiacvaI la s6giaodi~m([3],[43]).Tren
55
ly thuye't,thu~ttoancuachungtoi v~nco dQphlict~pb~chai,nhungchiphi
tIlingbinhth1.fcte'nhobonO(nxm)nhi~u.Ta hayxemxetchiphicuatungbuoc
trongthu~toan.
Trangbuoc dfiu tien, tO~lllbQk =m+nc~nhcuacacdagiacbandfiuduQcs3:p
xe'ptheoto~dQx.Ne'udungquicksort,ato'nchiphiO(klog2k).Saudo,t~im6i
diemdungcuasweepline,mQttrongcach~mhdQngsauduQcth1.fchit$n(xem
phfin2.2.2.2):
. Ap d1.;lllgLu~Ha: hai c~nhcuadagiacP, nSuViE P (ho~ccuaQ, nSuViE Q),
duQckiem trade tlmgiaodiemvoi cacc~nhtrongSq(ho~cSp).Ghl sii'dang
co r (r :::;max(m,n)<k) c~nhtrongt~pdangxet. H~lllhdQngnay t6nchi phi
20(r).
. Ap dvngLu~tb: taco thebuyhaic~nhkhoi t~ptuongling voi thaigian
0(1).
. Ap dvngLu~tc va d: trongtruanghQpnay,mQtc~nhduQckiemtradetlm
giaodiemvamQtc~nhkhacbihuy.Chiphiclingsela OCr).
. Cac lu~tdegiaiquye'tcactruanghQpd~cbit$t(xemHlnh2.27trongphfin
2.2.2.2)cothexemxettuongt1.fnhucaclu~ta-d.
MQttrongcaccongvit$ctrenphai duQcapdvngt~im6i dlnhVi(i :::;k).Ta giasii'
r~ng,t~im6i dlnh,lu~ta d~uduQcap dvng.Nhu v~y,taphai th1.fchit$n2kO(r)
phepkiemtra.Ta co,
Tl =O(kr) (seb~ng0(k2)trongtruanghQpxa'unha't)
R6 rang,ch~ntrennaykhongsatVI trongth1.fcte',khongchllu~ta duQcsii'dvng.
Hon nlla, sO'luQngc~nhtrongt~pdangxet r « k. Day chinhla ly do chuySu
khie'nthu~toanch~ynhanhhoncaid~tbinhthuang.Ta clingcfinlu'uy dng
56
t6ngs6l~n ki€m trac~nthlfchi~nd€ tlmgiaodi€m xa'pXl vai s6 giaodi€m cua
haidagiac.s6 giaodi€m cangIt, chiphi thlfchi~nthu~toancangtha'p.
Chi phi thlfchi~nph~nhai cuathu~toanpht;lthuQcvaos6giaodi€m tlmduQcW
~k.Nhu v~y,chiphicuaph~nnayla:
T2=Dew) =O(k).
Trongph~nthilba,c~nthlfchi~nhaipheps~pxe'pWI=W +R + 1ph~ntll',trong
doWla s6giaodi€m, vaRia s6ringcuadagiac(xemHlnh2.30).Haipheps~p
Xe'pt6nchiphi:
T3=2 O(wIlog2 WI)
Ta co th€ ghl dinhWI~ kvanhuv~y,T3trdthanh:
T3=O(k log2k).
T6ngchiphicuathu~ttoantrongtruonghQpxa'unha'tla:
T =TI + T2+ T3=O(kr)+ O(k)+O(k log2k)=Gee).
Khi ki€m nghi~mb~ngs6li~u thlfcte',chungtoi tha'yr~ng,danhgia 19thuye't
tren la ch~ntren khongt6t. Chi phi thlfchi~ntrungblnh cua thu~ttoanvao
khoangO(k log2k).Nennhadng, Gee)trongcongthilctrenthlfccha'tchlla
O(kr).
2.3. .Tom tilt
Trangchudngnay, chungWi da trlnhbay mQts6 ke'tqua lien quailde'nva'nd6
hill trli va t:;tol~pdli li~u.MQt cd che't6 chilcdli li~uvai ca'utructopologyda
duQcd6 nghi phil hQpvai cac tieu chu~ncua VPF. Bai toan vectorhoa anh
bitmapvai dinhhuangchinhla vectorhoa band6 da duQcgiai quye'tvai tie'p
c~nthongquapheplammanh'duongbien.
57
MQthuangtie'pc~nt6ngquatd6tlmgiaocuahaidagiackhongtv c~tba'tky
clingdffdU<;5Ctrlnhbay.Thu~toancoth6caid~tdSdang.Nhungva'nd~v~gioi
h(;lntinhtoansf)hQcchinaysinhkhi phaitinhgiaodi6mcuahai c(;lnhdagiacva
nhuv~ytahoantoanco th6ki6m soatchung.Nho v~y,taco th6xay dvngmQt
thu~ttoannhanhva6ndinhmQtcachdSdang.Thu~toanclingcoth6marQng
d6thvchi~ncacpheptoanBoolkhac(he>i,ph~nbu,...cuahaidagiac)khong
ma'ykho khanchivai me>tsf)thayd6i nhokhi themcacthongtin" luanchuyin"
trangph~nhai cuathu~toan.
Chungtoi xaydvngthu~toannayd6sadvngtrangvi~cgiaimQtsf)bai toan
trangcach~GIS maBe>manrang ngh~ph~nm~m,KhoaCongngh~Thongtin
TruongDR KRTN dangphattri6n.Trangcacbaitoannay,cacdagiacth6hi~n
cacvungda't,diagiai,song,h6, Cacbai toannhutirihdi~ntichph~ngiao,
phanchiagiaithaa,tinhtoand~nbu,quiho~chdothila nhungva'nd~thaisv
machungtoidffvadanggiaiquye't.
Trangchuangnaychungtoikhongtrlnhbayv~cacthaotactrenmohinhhilltru
duli~ud~nghivi trangcaid~tthvcte',chungWi dffsadvngva ke'thuatubQ
thuvi~nCGAL [19],[20]docacu'udi6mcuabe>thuvi~nnay.Day la be>thu
vi~ndocacphongthlnghi~mn6itie'ngachauAu nhuVi~nnghienCUllINDRA,
TruongD~ihQcKy thu~tETRZ - Zurich,TruongD(;lihQcBerlin, ...
MQtph~ncac ke'tqua trlnhbay trongchuangnay dff dU<;5Ccongbf) trang[30],
[18],[29].