VRSTA GRADIVA | analitična raven (sestavni del), tekstovno gradivo, tiskano, 1.03 - kratki znanstveni prispevek |
DRŽAVA IZIDA | Slovenija |
LETO IZIDA | 2001 |
JEZIK BESEDILA/IZVIRNIKA | angleški |
PISAVA | latinica |
AVTOR | Žalik, Borut - avtor |
ODGOVORNOST | Zadravec, Mirko - avtor // Clapworthy, Gordon J. - avtor |
NASLOV | Constructing geometric outlines for line segments |
V PUBLIKACIJI | Contributions to geometric modelling and multimedia. - ISSN 1580-5689. - ǂVol. ǂ1, ǂno. ǂ6 (2001), str. 1-26. |
KRATKA VSEBINA | V članku predstavimo algoritem za določanje geometrijskih očrtij iz množice daljic z uporabo skanirne premice. Algoritem deluje v štirih korakih: ustvarjanje ciklov in določanje prostorskih odnosov med cikli. V najslabšem primeru, ko se vsako osnovno geometrijsko očrtje seka z vsemi ostalimi, je časovna zahtevnost O(▫$n[na]$▫log n), kjer je n število vhodnih daljic. Iz praktičnih meritev pa se izkaže, da je časovna zahtevnost zelo blizu O (n log n). Algoritem seuporablja v GIS aplikacijah in se je izkazal kot zelo uspešen. // The paperpresent an algorithm for constructing the geometric outlines of a given setof line segments, using a sweep-line approach. The algorithm works in four steps: creating the basic geometric outlines, identifying the intersection points between them, constructing cycles, and determining the spatial relationships amongst the cycles. In the worst case, when each basic geometric buffer intersects all the others, the time complexity of the algorithm is O(▫$n[sup]$▫ log n), where n is the number of input line segments. However, in practice, te expected time complexity is much lower, and this has been confirmed by experiments - it has been shown that O (n log n) time complexity is a good estimation in most cases. The algorithm has been used in GIS applications over a period and has proved to be successful. |
OPOMBE | Bibliografija: str. 25-26 |
PREDMETNE OZNAKE | // računalniška geometrija // GIS // geometrijsko očrtje // algoritmi |
UDK | 004.9:514.116 |