smiller@wet.UUCP (Gregory Shane Miller) (03/15/91)
Wed. 13 March 1991
I am looking for references to the following:
[a] R-TREEs which are used to store and retrieve polygons. I
would like to get an article which gives a definition so I
implement the data structure and surrounding access algorithms.
[b] A data structure which stores areas covered by simple polygons
polygons efficiently (eg. like the segment tree which stores
line intervals with logorithmic access).
[c] Finally a data structure which could store a simple polygon
which also tell me, for example, when one polygon intersects
another.
Does R-TREE already encompass all these features? Please send any information
to smiller@wet.UUCP. I'll post a summary if required. Thanks.
--
--
G. Shane Miller [ smiller@wet.UUCP ]mao@eden.Berkeley.EDU (Mike Olson) (03/20/91)
mail to smiller@wet.UUCP fails from our mailer. sorry for posting... i just finished building an rtree indexed access method for the postgres database system, so i can respond to your questions: > [a] R-TREEs which are used to store and retrieve polygons. I > would like to get an article which gives a definition so I > implement the data structure and surrounding access algorithms. see antonin guttman's paper, "R-Trees: A Dynamic Structure for Spatial Searching" in proc sigmod 1984. > [b] A data structure which stores areas covered by simple polygons > polygons efficiently (eg. like the segment tree which stores > line intervals with logorithmic access). i don't know of *any* storage structure for two-dimensional (or higher) polygons that guarantee logarithmic access for anything other than insertion. on search, rtrees "are likely" to eliminate subtrees from the search, but how likely is a function of the data distribution and insertion order. > [c] Finally a data structure which could store a simple polygon > which also tell me, for example, when one polygon intersects > another. rtrees handle intersection, overlap, containment, and so on. as described by guttman, rtrees store bounding rectangles (in two or more dimensions) for arbitrary polygons. you don't store the polygons themselves in the index. if you have more questions, feel free to contact me directly (but please give me a better return address that wet.UUCP). mike olson postgres research group uc berkeley mao@postgres.berkeley.edu