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

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

pdf50 trang | Chia sẻ: maiphuongtl | Lượt xem: 1813 | Lượt tải: 0download
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].

Các file đính kèm theo tài liệu này:

  • pdf3.pdf
  • pdf0.pdf
  • pdf1.pdf
  • pdf2.pdf
  • pdf4.pdf
  • pdf5.pdf
  • pdf6.pdf
  • pdf7.pdf
Tài liệu liên quan