Xref: utzoo comp.graphics:8804 comp.databases:4326
Path: utzoo!attcan!uunet!cs.utexas.edu!uwm.edu!uwvax!astroatc!nicmad!burton
From: burton@nicmad.UUCP (Kevin Burton)
Newsgroups: comp.graphics,comp.databases
Subject: 2-D Data Structure
Keywords: data structure
Message-ID: <3910@nicmad.UUCP>
Date: 2 Dec 89 14:32:32 GMT
Organization: Nicolet Instrument Corp., Madison, WI
Lines: 225
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
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
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
================================================================================