P°edstavme si na chvφli mapu ·zemφ a dotaz ôNajdi vÜechny lesy ve m∞stech na danΘm ·zemφö. Jsou-li oba typy objekt∙ souΦßstφ mapy, jist∞ nebude problΘm zφskat po troÜe ·silφ odpov∞∩. Pon∞kud horÜφ situace nastane, budou-li m∞sta na jednΘ map∞ a lesy na druhΘ. Pomineme-li °eÜenφ, ₧e mapy jdou p°ekr²t a prohlΘdnout proti sv∞tlu, nebude ji₧ zφskßnφ v²sledku tak trivißlnφ. O co jde? P°ekrytφ a pr∙niky objekt∙ souvisφ s operacφ, kterou naz²vßme prostorovΘ spojenφ.

V databßzφ prostorov²ch objekt∙ budeme p°edpoklßdat prostorovΘ relace M╠STO(JmΘno_m, PS╚, Populace, ┌zemφ_m) a LES(OznaΦenφ_l, JmΘno_l, ┌zemφ_l), kde geometrickΘ atributy - ·zemφ popisujφ hranice m∞st resp. les∙. Prostorov² predikßt P, kter²m se dan² dotaz °eÜφ, je pr∙nik dvou mno₧in. Odmyslφme-li si ostatnφ atributy relacφ, pak platφ-li P(a,b) = TRUE, nazveme dvojici objekt∙ (a,b) hitem. P m∙₧e b²t i jin² prostorov² predikßt. V ka₧dΘm p°φpad∞ vÜak jde o operaci na dvou prostorov²ch relacφch, kterß vracφ dalÜφ relaci - relaci hit∙, kterΘ spojujφ jistΘ °ßdky relacφ na vstupu.

Zdß se, ₧e prostorovß spojenφ majφ pro prostorovΘ databßze podobnou d∙le₧itost jako operace spojenφ v klasick²ch databßzφch.

D∙le₧it²m aspektem implementace prostorov²ch objekt∙ je jejich reprezentace pomocφ aproximacφ. Jednou z mo₧nostφ jsou ji₧ v p°edchozφch dφlem DatabßzovΘ abecedy zmi≥ovanΘ MOO, kterΘ slou₧φ jako prvnφ krok pro v²poΦet prostorovΘho spojenφ. SkuteΦn² vztah dvou objekt∙ je aproximovßn vztahem jejich MOO. TakovΘ spojenφ nazveme MOO-spojenφ. Pro pr∙nik dßvß operace dvojice (Id(a),Id(b)) takovΘ, ₧e platφ MOO(a) Ç MOO(b) ¹ Æ . Bohu₧el, ne vÜechny dvojice objekt∙ takto zφskan²ch jsou hity. Takov²m p°φpad∙m budeme °φkat faleÜnΘ hity. Pro p°esn∞jÜφ odliÜenφ budeme pou₧φvat dalÜφ aproximace a teprve v nerozhodnuteln²ch p°φpadech se p°istoupφ p°esnΘ k geometrickΘ reprezentaci prostorov²ch objekt∙ a odpovφdajφcφmu vyhodnocenφ P(a,b).

Nejsiln∞jÜφ operaci pro spojenφ objekt∙ je ta, kterß vracφ pr∙niky objekt∙, tj. v p°φpad∞ les∙ a m∞st ty Φßsti m∞sta, kterΘ jsou lesem. Naopak, slabÜφ operace spojenφ poskytuje pouze identifikßtory objekt∙ z dvojice, tj. Id-spojenφ je definovßno jako mno₧ina dvojic (Id(a),Id(b)) takov²ch, ₧e platφ P(a,b).

Hledat pro prostorovΘ spojenφ inspiraci v relaΦnφch databßzφch nep°inßÜφ mnoho u₧iteΦnΘho. Algoritmus set°φd∞nφ-slΘvßnφ po₧aduje set°φd∞nφ objekt∙ a tedy jednorozm∞rnou reprezentaci dvourozm∞rn²ch objekt∙. Bohu₧el ·plnΘ uspo°ßdßnφ prostorov²ch objekt∙ kterΘ zachovßvß prostorovΘ vzdßlenosti, neexistuje. Tato cesta je mo₧nß pouze u operßtoru ôp°ekr²vßö, kdy se m∙₧e pou₧φt nap°. z-uspo°ßdßnφ (Peanovy k°ivky). OmezenΘ mo₧nosti majφ dφky tomu i indexy, kterΘ v∞tÜinou spolΘhajφ na uspo°ßdßnφ. HaÜovanß spojenφ nejsou v∙bec vhodnß, tak₧e vlastn∞ zb²vß algoritmus vno°en²ch cykl∙. Lze ho pou₧φt jako odrazov² m∙stek pro dalÜφ ·vahy.

Algoritmus PROSTOROV╔_SPOJEN═1(A,B)

Vstup: prostorovΘ relace A, B

V²stup: mno₧ina dvojic objekt∙, kterΘ se p°ekr²vajφ

begin ODPOV╠╧:=Æ ;

for i:=1 to m do

begin p°eΦti objekt a_i z A do buffer_A;

for j:=1 to n do

begin p°eΦti objekt b_j z B do buffer_B;

if P(a_i,b_j) then ODPOV╠╧:= ODPOV╠╧ È (a_i,b_j)

end

end

Nev²hodou uvedenΘho algoritmu m∙₧e b²t jeho nßroΦnost Φasovß i pam∞¥ovß v kroku p°enßÜenφ objekt∙ do vnit°nφ pam∞ti (buffer). Objekty toti₧ mohou obsahovat mnoho bod∙. Navφc, jeden objekt m∙₧e b²t Φten vφcekrßt a takΘ poΦet cykl∙ m∙₧e b²t vysok².

Zam∞°φme se proto na postupnΘ zpracovßnφ spojenφ, kterΘ vlastnφ p°enos objekt∙ oddaluje a pou₧φvß ho jen kdy₧ u₧ neexistuje jinß mo₧nost. ProstorovΘ objekty budeme p°edpoklßdat organizovanΘ pomocφ n∞jakΘ vhodnΘ datovΘ struktury, nap°. R-stromu.

ProstorovΘ spojenφ lze realizovat ve t°ech krocφch:

1. Aplikacφ datovΘ struktury pro organizaci aproximacφ prostorov²ch objekt∙ (prostorovΘ indexy) se spoΦφtß MOO-spojenφ, kterΘ ovÜem poskytne pouze mno₧inu kandidßt∙ na spojenφ objekt∙.
2. V geometrickΘm filtru se pomocφ dalÜφch, lepÜφch aproximacφ a p°φdavn²ch kritΘriφ odhalujφ hity, faleÜnΘ hity a dvojice, kde nelze rozhodnout. Tyto vstupujφ do t°etφho kroku.
3. Pomocφ p°esnΘ geometrie objekt∙ se odd∞lφ dalÜφ hity

relace A relace B

Procesor pro zpracovßnφ prostorov²ch dotaz∙

ProstorovΘ

indexy * _MOO

geometrick² filtr

hity chybnΘ hity dvojice kandidßt∙

p°esn² geometrick²

procesor

Obr. 1 Zpracovßnφ prostorovΘho spojenφ

T°etφ krok je v²poΦetn∞ nejdra₧Üφ, pou₧φvß algoritm∙ v²poΦetnφ geometrie. V²slednß architektura zpracovßnφ je na obrßzku 1.

Zatφm jsme uva₧ovali pro aproximaci objekt∙ pouze MOO, tj. pouze konzervativnφ aproximace. Jsou-li spolu s objekty a jejich konzervativnφmi aproximacemi uklßdßny i jejich nevyu₧itΘ plochy nebo progresivnφ aproximace, lze jednoduÜe zφskat n∞kolik test∙ pro p°esn∞jÜφ rozpoznßnφ hit∙.

OznaΦme KApr, resp. PApr funkci p°i°azujφcφ objektu jeho konzervativnφ, resp. progresivnφ aproximaci. Funkce NA p°i°azuje konzervativnφ aproximaci objektu jeho nevyu₧itou plochu. Pak existujφ postaΦujφcφ podmφnky pro to, aby bylo spln∞no Ç (o₁,o₂). Lze tak ΦßsteΦn∞ zlepÜit algoritmus pro prostorovΘ spojenφ zalo₧enΘ na pr∙niku objekt∙. Platφ nßsledujφcφ dv∞ tvrzenφ:

1. Jestli₧e KApr(o ₁) Ç KApr(o ₂) > NA(o ₁) + NA(o ₂), pak o ₁ Ç o_{2 ¹} Æ .
2. Jestli₧e PApr(o₁) Ç PApr(o₂) ¹ Æ , pak o₁ Ç o_{2 ¹} Æ .

P°i praktickΘm °eÜenφ problΘmu spojenφ prostorov²ch objekt∙, nap°. pomocφ R-strom∙, lze postupovat klasicky podle MOO nebo podle n∞jakΘ jinΘ konzervativnφ aproximace, nebo udr₧ovat vedle MOO ve struktu°e jeÜt∞ dalÜφ progresivnφ aproximaci. Zßkladnφ trik spoΦφvß v tom, ₧e testovßnφ ôna hruboö podle MOO je levnΘ. ╚φm vφce parametr∙ konzervativnφ aproximace, tφm slo₧it∞jÜφ je vyhodnocenφ Ç (o₁,o₂). Uklßdßnφ dalÜφch aproximacφ znamenß takΘ nßr∙st pam∞ti.

Na zßv∞r si jeÜt∞ vyzkouÜφme spojenφ pomocφ z-uspo°ßdßnφ a R-strom∙.

Ka₧d² prostorov² objekt je (v 2D) dekomponovßn do Φtverc∙ rekurzivnφm d∞lenφm objektu Orientace a pozice d∞lenφ jsou takovΘ, ₧e v²slednΘ regiony jsou reprezentovßny mno₧inou z-hodnot. Dekompozice poskytuje jednu nebo n∞kolik takov²ch mno₧in z-hodnot z₁,..., z_n. Prostorov² objekt je definovßn sjednocenφm oblastφ korespondujφcφch k z₁,..., z_n. Tyto oblasti obsahujφ objekt, tj. jde o konzervativnφ aproximaci objektu. Ka₧d² prostorov² objekt je dßn jako mno₧in dvojic [ z₁, o] ,...,[ z_n, o] .

ProstorovΘ spojenφ je zalo₧eno na algoritmu set°φd∞nφ-slΘvßnφ pro dv∞ posloupnosti, kterΘ jsou z-uspo°ßdßny, tj. ka₧dß z nich je set°φd∞na podle z-hodnoty.

V prvnφm kroku algoritmu prostorovΘho spojenφ se zφskajφ dvojice (Id(a),Id(b)), pro kterΘ z-hodnota z a je obsa₧ena mezi z-hodnotami z b nebo naopak. Ve druhΘm kroku se p°ejde ke geometrickΘmu porovnßnφ.

Budeme p°edpoklßdat, ₧e pro ka₧dou prostorovou relaci A, B existuje odpovφdajφcφ R-strom. DalÜφm (ne nutn²m) p°edpokladem bude stejnß hloubka obou R-strom∙. Algoritmus MOO-spojenφ lze popsat nßsledovn∞.

Algoritmus PROSTOROV╔_SPOJEN═3(T,U)

Vstup: R-stromy s ko°eny T, resp. U

V²stup: mno₧ina dvojic identifikßtor∙ objekt∙, jejich₧ MOO se p°ekr²vajφ

foreach E_T Î T do

forach E_U Î U with E_T.I Ç E_U .I ¹ Æ do

if U je list then PRINT(E_T.Id , E_U .Id)

else PROSTOROV╔_SPOJEN═3(E_T. p, E_T.p);

end

Pro algoritmus je d∙le₧itΘ minimalizovat nejenom poΦet p°φstup∙ na disk, ale i Φas CPU, kter² m∙₧e p°i vyhodnocovßnφ operace pr∙nik vzr∙stat. Jedno ze zlepÜenφ algoritmu bude zahrnovat omezenφ prohledßvanΘho prostoru, tj. redukci poΦtu porovnßnφ dvojic kostek. DalÜφ mo₧nß zlepÜenφ vyu₧φvajφ mo₧nostφ jistΘho uspo°ßdßnφ kostek v uzlu.