burton@nicmad.UUCP (Kevin Burton) (12/02/89)
A while back I posted the following question: > I have been considering for quite some time an efficient data structure > for 2-D objects. By efficient I mean that the closest object or objects > to a given object can be found very quickly and objects can be added and > deleted easily. There are many structures that lend themselves very well > to points (eg binary trees, B-trees, Delaunay triangulation ...) but I > am unaware of any that explicitly deal with two dimensional objects. The > quad-tree has the general flavor of the structure I am looking for but > it seems too "raster" oriented to be adapted. Does anybody have any infor- > mation, opinions, advice ? I sincerely appreciate all of the responses I received. I will have some reading to do. Thank you. Following is a summary of the responses: *************************************************************************** From: astroatc!uwvax!rutgers!cs.umd.edu!mjr (Marcus J. Ranum) Subject: R-trees I think what you're looking for is an R-tree - it is essentially a B-tree that chunks things in "rectangles" rather than "lines". I have a paper I can send you a copy of - send me mail if you're interested. *************************************************************************** From: astroatc!uwvax!rutgers!phoenix.princeton.edu!markv (Mark T Vandewettering) Subject: Re: Graphics data structure info request You said it already: quadtrees. Almost any kind of search is effectively done via quadtrees, I have used them as well as octrees in raytracers and other graphics algorithms. They are simple to code, with a little work they perform nearly as good as more complex structures, with fewer headaches. Don't worry too much about their raster-like nature. If your leaf nodes hold lists of objects, you can do real interesting things too. Samet has two new books, one with the theory and one with applications of quadtree/octree like structures, and they seem pretty thorough and useful. I don't have the particulars here, but they are both really new, bearing a 1990 copyright. Mark VandeWettering *************************************************************************** From: astroatc!uwvax!rutgers!ai.mit.edu!tmb (Thomas M. Breuel) Subject: Graphics data structure info request Try k-D trees or k-D tries. However, for most applications, a simple 2D array (coarse grid with constant bin size) is good enough. Only if you have very high resolution and a very large number of objects will anything else really pay off. *************************************************************************** >From: flynn@pixel.cps.msu.edu (Patrick J. Flynn) Subject: Re: Graphics data structure info request [my apologies if you see this twice; the first posting was truncated and I am trying to cancel & repost...] Hanan Samet from Maryland has a new book out entitled... [rustle, rustle...] "The Design and Analysis of Spatial Data Structures", published by Addison-Wesley, copyright 1990 (!). I don't have the ISBN number handy. There is a companion volume on applications that hasn't shown up in our bookstore yet. The "Design" book discusses data structures for 2D and 3D objects, focusing on tree-structures of various sorts. While I haven't done a thorough reading, it seems like a very nice treatment of a variety of useful techniques. There is a HUGE bibliography. -- Patrick Flynn, CS, Mich. State U., flynn@cps.msu.edu *************************************************************************** >From: rick@hanauma.stanford.edu (Richard Ottolini) Xref: nicmad comp.graphics:8976 comp.databases:4426 A related question. Have there been attempts to coerce model data structures into standard databases, e.g. normal relational form, to take advantage of high speed database engines. I remember some people doing this for AI knowledge bases. It wasn't very creative, but faster. *************************************************************************** >From: jack@odi.com (Jack Orenstein) Subject: Re: Graphics data structure info request There are a few approaches to dealing with non-point spatial data. The simplest is to place each data object in a container, such as a circle or box. Then describe the container parametrically, yielding a point in a higher-dimension space. Many spatial search problems can be restated in the parameter space. For example, a 2-d box is represented by the point (xlo, xhi, ylo, yhi) in 4-d space, and a circle whose center is at (x, y) is represented by the point (x, y, radius) in 3-d space. Following the search, weed out data objects that don't really satisfy the query. This refinement step is necessary because the container is not an exact representation of the data object (usually). Some spatial search structures have been designed to deal with non-spatial objects. These also involve some kind of approximation and also require a refinement step. For example, there's the R-tree, a variation of it - the R+-tree, the hB-tree, and there are variations of the EXCELL and grid file search structures which were originally proposed for point data. I have done research in this area for several years. The basic idea of my work is to transform the data objects and search problem into an equivalent data set and search problem in 1-d. The transformation is based on the use of space-filling curves. Each data object and query region is represented by a sequence of consecutive points on this curve, which can be concisely encoded as an integer key. My algorithms work on top of any data structure supporting random and sequential access. I.e., you can put the algorithms on top of a btree, binary tree, or even just a sorted array (if you don't care about updates). Queries are run by generating random accesses based on the integer keys, and sequential accesses. Quadtrees can be adapted to non-point objects also. The "raster" orientation means that there must be a refinement step, as with other structures. (Is this why you ruled it out?) The work on non-point data is all pretty recent. There hasn't been a lot of work on performance comparisons. The performance results, for the most part, examine a single data structure. In terms of implementation, the methods that use existing data structures are the simplest, (the parameter-space method and the space-filling curve method). These are obviously dynamic, since the underlying data structures are dynamic. The other structures are dynamic also, but the insertion and deletion algorithms are fairly complex, and in some cases, there is no lower bound on storage utilization. I could go on for pages. Send email if you want more information. Jack Orenstein Object Design, Inc. References: Parameter space method: Ph.D. thesis by Hinrichs, Swiss Federal Institute of Technology; various tech reports by Faloutsos, Rego, Sellis, University of Maryland. R-tree: Guttman, SIGMOD 84. R+-tree: University of Maryland, again. Also, see VLDB 87 (Sellis, Roussopoulos, Faloutsos). Grid file: ACM Trans. on Database Systems, 9, 1 (1984), Nievergelt, Hinterberger, Sevcik. EXCELL for non-point data: 19th ACM Design Automation Conference, Tamminen & Sulonen. hB-tree: Data Engineering 1989, Lomet & Salzberg. Using space-filling curves: papers by Orenstein in SIGMOD 86, IEEE Trans. on Soft. Eng. May 1988, SIGMOD 89. Survey of the area: Recent ACM surverys article by Hanan Samet, who also has a new book surveying the field. *************************************************************************** From: Landon Dyer <astroatc!uwvax!apple.com!landon> Subject: Re: Graphics data structure info request Big area. Definitely check out Hanan Samet's work from the University of Maryland -- he has a number of ACM articles on quad-trees and related topics (including an excellent survey in ACM Surveys) and two recent books on spatial data structures (which I haven't had time to read, but that _look_ great). ----------------------------------------- "Mmmph! Urghurmph! Grugmph!" Landon Dyer, Apple Computer, Inc. "What's he trying to say?" Development Systems Group (MPW / DSG) "I dunno -- there's a lawyer NOT THE VIEWS OF APPLE COMPUTER crammed in his mouth." *************************************************************************** From: Christophe Dubreuil <astroatc!uwvax!rutgers!cs.heriot-watt.ac.uk!dubreuil> Subject: data bases and quadtrees hi, Maybe you could have a look at the following paper: Object representation by means of non minimal division quadtrees and octrees. D ayala P Brunet and al ACM Transaction on graphics Vol 4 N 1 Jan 85 pp41-59 This article proposes a way to store 2 D polygons using some kind of quadtree. The quadtree used are edge oriented not area oriented. I don't know if this is of some help. If you summurise answers I'd be happy to get the summary since I am playing with that as well Thanks in advance Christophe * Christophe Dubreuil JANET: dubreuil@uk.ac.hw.cs * * Heriot-Watt University ARPA: dubreuil@cs.hw.ac.uk * * Dept of Computer Science UUCP !ukc!hw.ac.uk!dubreuil * ================================================================================ att!terminus-----\ | harvard-\ att--\ | Kevin Burton (608) 276-6166 ucbvax!uwvax!astroatc!nicmad!burton | Nicolet Instrument Corp. rutgers--/ rolls--/ | 5225-2 Verona Rd ames--/ decvax-/ | Madison, WI 53711-0288 ================================================================================