Talk:Octree
From Wikipedia, the free encyclopedia
[edit] What is an MX octtree?
This article mentions an "MX octtree". Unfortunately, no where are such trees explained.
This article also mentions that PR octtrees can represent "infinite" space. To me, this is somewhat vague. Perhaps the word "unbounded" would be more appropriate? In any case, I do not quite see how it is possible for an octtree to keep track of things which may be arbitrarily far away from some center. This relates to my first question, because this seems to be where the difference lies between PR and MX varieties of octtrees.
- MX Octree and PR Octree are by analogy to those terms for quadtrees; googling will turn up more information. I don't know where the terminology originates, but it's popularized in Samet's spatial data structure books. And yes, by "infinite" I meant "unbounded". Consider your classic binary tree: the tree represents arbitrary points (by inserting them) from some essentially unbounded space. If a new element is inserted outside the range of the existing elements, there's no problem, the tree can "grow" appropriately. Normally we don't think very explicitly about a binary tree partitioning space, but it is doing so implicitly. A PR quadtree/octree works the same way; you insert specific data items and they go somewhere in the tree and divide the space correspondingly. In an MX quadtree/octree, you define a finite space to be partitioned, and each partitioning step halves it. 71.141.227.19 01:14, 17 September 2007 (UTC)
-
- I've also never seen the MX and PR nomenclature. It looks like it is specific to that particular author. In any case, what it describes is a detail that should not be present in this article, or at least be moved way down the page. BTW, PR trees as you describe them sound awfully similar to K-D trees. And K-D trees aren't octrees even if they're three dimensional. Nomis80 (talk) 05:42, 24 February 2008 (UTC)
[edit] Picture
Does the picture look messed up to anyone else? Mainly the right hand side.
