Talk:Quadtree

Thanks to the editors who wrote this article. I think the end of the sentence, "A point region (PR) quadtree is a type of quadtree where each node must have exactly four children, or leaf, having no children." could be clearer, though. Could someone who knows the subject clarify what's meant here? Thanks! --Allen 02:54, 9 March 2006 (UTC)Reply

The author probably meant: A point region quadtree is a type of quadtree where each node either has exactly four children, or none. A node with no children is called a leaf.

However, that would define a full or proper quadtree, rather than explain why or how such a tree is used as a region or point region quadtree. -- Gimmetrow 03:49, 4 May 2006 (UTC)Reply

"The point quadtree is an adaptation of a binary tree used to represent two dimensional point data. It shares the features of all quadtrees but is a true tree as the centre of a subdivision is always on a point." The tree in the picture looks rather like a Region Tree to me, but I'm not really sure... —Preceding unsigned comment added by 85.0.157.176 (talk) 16:25, 6 February 2008 (UTC)Reply

I believe you're correct. A point quadtree would only subdivide around an existing point in the dataset - the uniform divisions shown in the image sound more like a region tree according to the definitions in this article. I'd like someone else to double-check this though before we change it. Dcoetzee 19:48, 6 February 2008 (UTC)Reply

It's a point quadtree. See http://donar.umiacs.umd.edu/quadtree/regions/regionquad.html for a example of how a region quadtree looks like108.54.157.242 (talk) 14:51, 21 April 2015 (UTC)Reply

Sadly, those Java animations are pretty much dead. Oracle disabled the ability to lower security settings below high around JRE7 U50 or something. Now the only way to run java applets anywhere on the internet is pretty much individually adding every url that has one (no wildcards allowed) to the whitelist manually. Here's David Mount's notes on the point quadtree , with a reading level aimed at undergraduate Computer Science juniors and seniors. ― Padenton|✉   21:44, 21 April 2015 (UTC)Reply

Apparently, the point/region dichotomy confuses two unrelated issues: how to split (into four rectangles at a sample point or into four squares at the median lines of the parent square) and whether to split (when a box contains too many sample points vs when some continuous function is close enough to constant within it). If you insist that both issues have to be resolved point/point or region/region, you will be unable to correctly describe this example, which is a very standard type of quadtree. The solution is to fix the nomenclature, not to argue about which of two incorrect descriptions is least incorrect. —David Eppstein (talk) 22:25, 21 April 2015 (UTC)Reply

Article states:

The region quadtree is not strictly a 'tree' - as the positions of subdivisions are independent of the data

This doesn't make any sense to me, and seems to need expanding. From my perspective, a 'tree' is a structure that consists of (quoting Tree (graph theory)) an undirected simple graph G that satisfies any of the following equivalent conditions:

• G is connected and has no cycles.
• G has no cycles, and a simple cycle is formed if any edge is added to G.
• G is connected, but is not connected if any single edge is removed from G.
• G is connected and the 3-vertex complete graph is not a minor of G.
• Any two vertices in G can be connected by a unique simple path.

The region quadtree clearly meets this definition, so saying it isn't strictly a tree is apparently untrue. Am I missing something? 212.159.69.4 (talk) 06:02, 25 September 2012 (UTC)Reply

I agree with you. I've removed that sentence. —Bkell (talk) 16:34, 25 September 2012 (UTC)Reply

This article doesn't explain what the benefits of storing information in this way are. For example, if I had to store coordinates of the points of rectangles, why would I use a quadtree rather than simply make a data structure that holds the coordinates and use an array of that structure? That would be faster and have less overhead. — Preceding unsigned comment added by 194.42.186.216 (talk) 15:58, 14 September 2013 (UTC)Reply

They're commonly used in 2d cad applications to improve performance. Instead of keeping all elements in the drawing space in memory to an infinite depth, only a quadrant that is in the visible pane is drawn, and only neighbouring nodes are processed when zooming in/out or panning. — Preceding unsigned comment added by 165.255.97.64 (talk) 20:49, 16 July 2016 (UTC)Reply

really? A citation would be nice! — Preceding unsigned comment added by 134.3.92.202 (talk) 22:27, 21 November 2013 (UTC)Reply

Hello fellow Wikipedians,

I have just added archive links to one external link on Quadtree. Please take a moment to review my edit. If necessary, add {{cbignore}} after the link to keep me from modifying it. Alternatively, you can add {{nobots|deny=InternetArchiveBot}} to keep me off the page altogether. I made the following changes:

• Added archive http://web.archive.org/web/20120204170335/http://homepages.ge.ucl.ac.uk/~mhaklay/java.htm to http://homepages.ge.ucl.ac.uk/~mhaklay/java.htm

When you have finished reviewing my changes, please set the checked parameter below to true or failed to let others know (documentation at {{Sourcecheck}}).

 Y An editor has reviewed this edit and fixed any errors that were found.

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—^{cyberbot II}_{Talk to my owner:Online} 12:56, 28 February 2016 (UTC)Reply

In the section about Polygonal Map Quadtrees, the term "black node" appears out of the blue:

"There are three main classes of PM Quadtrees, which vary depending on what information they store within each black node"

There is no prior mention of "black nodes" in this article, nor any link to a definition of these nodes.

Can someone provide one, and do these "black nodes" have any relation to any other Quadtree type? — Preceding unsigned comment added by 192.31.106.36 (talk) 04:43, 4 May 2017 (UTC)Reply

In the section titled "Mesh generation using quadtrees," someone wrote the following sentence:

"We say v is balanced (for mesh generation) if the cell's sides are intersected by the corner points of neighbouring cells at most once on each side."

There is a diagram to the right that tries to show the difference between "balanced" and "not balanced," but the right side of the so-called "balanced" cell seems to intersect with two corner points of its neighbor to the right, which is inconsistent with the definition of "balanced." Does the "intersection" of a "corner point" with a "side of a neighboring cell" NOT include any corner points it may have in common with that neighboring cell? — Preceding unsigned comment added by 192.31.106.36 (talk) 05:47, 4 May 2017 (UTC)Reply

found this Blackdiamand (talk) 22:05, 25 March 2018 (UTC)Reply

While implementing, I did not realise that for a quadtree over 13 points the algorithm described by the wikipedia balances the tree like this:

Root: 4
|- NW: 4
|  |- NW: 3
|  |- NE: 1
|  |- SW: 0
|  |- SE: 0
|- NE: 1
|- SW: 0
|- SE: 0

However typically I would expect branches to not have children, i.e.

Root: 0
|- NW: 0
|  |- NW: 0
|  |  |- NW: 4
|  |  |- NE: 3
|  |  |- SW: 1
|  |  |- SE: 0
|  |- NE: 2
|  |- SW: 2
|  |- SE: 0
|- NE: 1
|- SW: 0
|- SE: 0

This changes queryRange code to this:

if (northWest == null){
  // Check objects at this quad level
  for (int p = 0; p < points.size; p++)
  {
    if (range.containsPoint(points[p]))
      pointsInRange.append(points[p]);
    }
  }
} else {
  // Otherwise, add the points from the children
  pointsInRange.appendArray(northWest->queryRange(range));
  pointsInRange.appendArray(northEast->queryRange(range));
  pointsInRange.appendArray(southWest->queryRange(range));
  pointsInRange.appendArray(southEast->queryRange(range));
}

Are these just 2 different kinds of quadtree? Personally I feel the one in this article is wasting computation on each level where it's unnecessary, but it does have other advantages like better handling of duplicates. Sancarn (talk) 10:52, 20 July 2024 (UTC)Reply

It might be valuable to add a concerns/challenges section for those implementing a quadtree. For instance:

1. How does one handle duplicates in a dataset (in my case I had sometimes up to 30 duplicates; and with the algorithm described above, these were cascading down into 0E-10 halfDimension distances as a result). In my case I added an exception to insertPoint:

//When halfDimension is significantly small, append and do not subdivide further
if(boundary.halfDimension < 0.00001){
  points.append(p)
  return true
}

2. Selecting initial bounds - you can do this from minX, minY, maxX and maxY making it dynamic to your dataset.

float rx = (maxX - minX) / 2
float ry = (maxY - minY) / 2
float rT = ry > rx ? ry : rx
float cx = minX + rx
float cy = minY + ry

Sancarn (talk) 11:20, 20 July 2024 (UTC)Reply