| VRSTA GRADIVA | analitična raven (sestavni del), tekstovno gradivo, tiskano, 1.03 - kratki znanstveni prispevek |
| DRŽAVA IZIDA | Slovenija |
| LETO IZIDA | 2002 |
| JEZIK BESEDILA/IZVIRNIKA | angleški |
| PISAVA | latinica |
| AVTOR | Gomboši, Matej - avtor |
| ODGOVORNOST | Žalik, Borut - avtor |
| NASLOV | Comparing two sets of polygons in land cadastre |
| V PUBLIKACIJI | Contributions to geometric modelling and multimedia. - ISSN 1580-5689. - ǂVol. ǂ2, ǂno. ǂ6 (2002), str. 1-24. |
| KRATKA VSEBINA | In this report, a new algorithm for determining differences between land cadastre polygons is considered. For this task, it has been proven, that it is enough to test only the polygon edges to perform the comparison. The algorithm works in two steps. First, the polygon edges are inserted into data structure and eliminated by a simple criterion. In the second part, the algorithem analyses the remainingedges and prepares the report about the detected differences. To speed-up the geometric search, the algorithm uses a combination of a uniform space subdivision and binary search trees. It has been shown, that the algorithmnis numerically stable, and works well also with the limited set of non-simple polygons occurring in practice. The algorithm's time complexity is O(n logn), and space complexity 0(n) where n is the common number of edges in both sets of polygons. That has been confirmed by experiments using data sets from a cadastre database. // V poročilu je podan nov algoritem, ki omogoča določanje razlik med dvema množicama mnogokotnikov. Algoritem uporablja mrežo uniformne razdelitve ravnine in dvojiška iskalna drevesa v vsaki celici mreže za hitrejšo doseganje rezultatov. Bistvo algoritma je iskanje enakih mnogokotnikovih robov. Vsak rob mnogokotnika sevstavi v iskalno drevo na ustreznem položaju v mreži. V primeru, da nek drugi mnogokotnik vsebuje enak rob, ga bomo hitro in učinkovito našli. Na ta način lahko zelo hitro določimo geometrijske in topološke razlike med dvema množicama mnogokotnikov. Algoritem je neobčutljiv na patološke primere, ki se dostikrat pojavljajo v računalniski geometriji. Uporabljene pohitritvene metode se kažejo tudi v časovni zahtevnosti algoritma. Analizapokaže časovno zahtevnost o (n .log m), kjer je n skupno število robov vsehmnogogokotnikov, m pa povprečno število robov znotraj iskalnega drevesa. |
| OPOMBE | Bibliografija: str. 22-24 |
| OSTALI NASLOVI | Primerjanje dveh množic mnogokotnikov v zemljiškem katastru |
| PREDMETNE OZNAKE | // računalniška geometrija // uniformna razdelitev prostora // operacije nad mnogokotniki // geometrijsko iskanje |
| UDK | 004.9:514.116 |