<!-- MHonArc v2.4.4 --> <!--X-Subject: Re: Quadtrees? --> <!--X-From-R13: "Qnegre F Eubpx" <pgfbNhzvnpf.hzq.rqh> --> <!--X-Date: from babe.globecomm.net [207.51.48.8] by mx01.ny.us.ibm.net id 857310090.131406-1 Sun Mar 2 13:41:30 1997 --> <!--X-Message-Id: 199703021110.LAA18892#lupa,umiacs.umd.edu --> <!--X-Content-Type: text/plain --> <!--X-Head-End--> <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN"> <html> <head> <title>MUD-Dev message, Re: Quadtrees?</title> <!-- meta name="robots" content="noindex,nofollow" --> <link rev="made" href="mailto:ctso#umiacs,umd.edu"> </head> <body background="/backgrounds/paperback.gif" bgcolor="#ffffff" text="#000000" link="#0000FF" alink="#FF0000" vlink="#006000"> <font size="+4" color="#804040"> <strong><em>MUD-Dev<br>mailing list archive</em></strong> </font> <br> [ <a href="../">Other Periods</a> | <a href="../../">Other mailing lists</a> | <a href="/search.php3">Search</a> ] <br clear=all><hr> <!--X-Body-Begin--> <!--X-User-Header--> <!--X-User-Header-End--> <!--X-TopPNI--> Date: [ <a href="msg00033.html">Previous</a> | <a href="msg00035.html">Next</a> ] Thread: [ <a href="msg00030.html">Previous</a> | <a href="msg00040.html">Next</a> ] Index: [ <A HREF="author.html#00034">Author</A> | <A HREF="#00034">Date</A> | <A HREF="thread.html#00034">Thread</A> ] <!--X-TopPNI-End--> <!--X-MsgBody--> <!--X-Subject-Header-Begin--> <H1>Re: Quadtrees?</H1> <HR> <!--X-Subject-Header-End--> <!--X-Head-of-Message--> <UL> <LI><em>To</em>: <<A HREF="mailto:mud-dev#null,net">mud-dev#null,net</A>></LI> <LI><em>Subject</em>: Re: Quadtrees?</LI> <LI><em>From</em>: "Carter T Shock" <<A HREF="mailto:ctso#umiacs,umd.edu">ctso#umiacs,umd.edu</A>></LI> <LI><em>Date</em>: Sun, 2 Mar 1997 06:09:56 -0500</LI> </UL> <!--X-Head-of-Message-End--> <!--X-Head-Body-Sep-Begin--> <HR> <!--X-Head-Body-Sep-End--> <!--X-Body-of-Message--> <PRE> > [Discussion of "B-tree with space-filling curve to index the tree"] > > Ahm, you've totally lost me here! I know what B-trees are (did one for > a database system I wrote), and I've heard of space-filling curves, but > I can't imagine how a curve can be used to index things. Can you say > some more about this? Lessee... if it's a curve, then there is a function that generates it. For the Morton curve we'll call that function M(x,y). The range and domain of M are both the set of Integers (i.e. the function is not continuous, but is defined for all integral values of x and y). So, if we generate values of M(x,y) for all values of x and y, the result is a series of integers. In this case it's called the Morton series. What I'm getting at is that the set of integer x and y is an infinite, dense matrix of equidistant points in 2 dimensional space. For each of these points there exists a unique value in the Morton series. This value is derived by interleaving the bits of the x and y coordinates as described in previous mail. So.. now we want to index a collection of points in 2 dimensional space (btw, it all works in any number of dimensions you want). Any index (B-Trees included) requires that we have some key for each datum we index. For simplicity's sake, we'll say that the key must have >, <, and == defined for it. Now, if you wanted to, you could store off both the x and y from your points and derive >, <, and == operators that compared the tuples. Equality is pretty easy, but greater than and less than get a little funky.. is [2,3] greater than or less than [3,2]? But wait! For any point (x,y) there exists some value in the morton series M(x,y). M(x,y) is just an integer and >, <, == are all trivially defined for integers. In short, you use the morton codes for the points to sort the points in your index. You don't have to use a B-Tree.. anything will do, but the B-Tree is attractive for large data sets used with limited core space. Next mail shows how to do a linear quadtree. -Todd </PRE> <!--X-Body-of-Message-End--> <!--X-MsgBody-End--> <!--X-Follow-Ups--> <HR> <!--X-Follow-Ups-End--> <!--X-References--> <!--X-References-End--> <!--X-BotPNI--> <UL> <LI>Prev by Date: <STRONG><A HREF="msg00033.html">Linear Quadtrees</A></STRONG> </LI> <LI>Next by Date: <STRONG><A HREF="msg00035.html">Re: Just a bit of musing</A></STRONG> </LI> <LI>Prev by thread: <STRONG><A HREF="msg00030.html">Re: Quadtrees?</A></STRONG> </LI> <LI>Next by thread: <STRONG><A HREF="msg00040.html">Re: Quadtrees?</A></STRONG> </LI> <LI>Index(es): <UL> <LI><A HREF="index.html#00034"><STRONG>Date</STRONG></A></LI> <LI><A HREF="thread.html#00034"><STRONG>Thread</STRONG></A></LI> </UL> </LI> </UL> <!--X-BotPNI-End--> <!--X-User-Footer--> <!--X-User-Footer-End--> <ul><li>Thread context: <BLOCKQUOTE><UL> <LI><STRONG>Re: Quadtrees?</STRONG>, <EM>(continued)</EM> <ul compact> <LI><strong><A NAME="00023" HREF="msg00023.html">Re: Quadtrees?</A></strong>, S001GMU <a href="mailto:S001GMU#nova,wright.edu">S001GMU#nova,wright.edu</a>, Sat 01 Mar 1997, 04:11 GMT </LI> <LI><strong><A NAME="00025" HREF="msg00025.html">Re: Quadtrees?</A></strong>, Carter T Shock <a href="mailto:ctso#umiacs,umd.edu">ctso#umiacs,umd.edu</a>, Sat 01 Mar 1997, 05:12 GMT </LI> <LI><strong><A NAME="00026" HREF="msg00026.html">Re: Quadtrees?</A></strong>, S001GMU <a href="mailto:S001GMU#nova,wright.edu">S001GMU#nova,wright.edu</a>, Sat 01 Mar 1997, 05:38 GMT </LI> <LI><strong><A NAME="00030" HREF="msg00030.html">Re: Quadtrees?</A></strong>, Chris Gray <a href="mailto:cg#ami-cg,GraySage.Edmonton.AB.CA">cg#ami-cg,GraySage.Edmonton.AB.CA</a>, Sat 01 Mar 1997, 17:34 GMT </LI> <LI><strong><A NAME="00034" HREF="msg00034.html">Re: Quadtrees?</A></strong>, Carter T Shock <a href="mailto:ctso#umiacs,umd.edu">ctso#umiacs,umd.edu</a>, Sun 02 Mar 1997, 21:41 GMT </LI> <LI><strong><A NAME="00040" HREF="msg00040.html">Re: Quadtrees?</A></strong>, coder <a href="mailto:coder#ibm,net">coder#ibm,net</a>, Mon 03 Mar 1997, 03:26 GMT </LI> <LI><strong><A NAME="00048" HREF="msg00048.html">Re: Quadtrees?</A></strong>, coder <a href="mailto:coder#ibm,net">coder#ibm,net</a>, Tue 04 Mar 1997, 14:53 GMT </LI> </ul> </LI> <LI><strong><A NAME="00009" HREF="msg00009.html">Just a bit of musing</A></strong>, Nathan Yospe <a href="mailto:yospe#hawaii,edu">yospe#hawaii,edu</a>, Thu 27 Feb 1997, 08:49 GMT <UL> <li><Possible follow-up(s)><br> <LI><strong><A NAME="00010" HREF="msg00010.html">Re: Just a bit of musing</A></strong>, Adam Wiggins <a href="mailto:nightfall#inficad,com">nightfall#inficad,com</a>, Thu 27 Feb 1997, 12:24 GMT </LI> </UL> </LI> </UL></BLOCKQUOTE> </ul> <hr> <center> [ <a href="../">Other Periods</a> | <a href="../../">Other mailing lists</a> | <a href="/search.php3">Search</a> ] </center> <hr> </body> </html>