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

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(;[email protected] 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 [email protected]'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].