Stack Overflow
Stack Overflow

Questions tagged [quadtree]

A quadtree is a geometric data structure for storing points in two-dimensional space. Quadtrees recursively partition a space into four quadrants.

380 questions
101
votes
7 answers

Efficient (and well explained) implementation of a Quadtree for 2D collision detection

I've been working on adding a Quadtree to a program that I'm writing, and I can't help but notice that there are few well explained/performing tutorials for the implementation that I'm looking for. Specifically, a list of the methods and pseudocode…
Zimri Leisher
  • 1,236
  • 3
  • 10
  • 14
84
votes
8 answers

When to use Binary Space Partitioning, Quadtree, Octree?

I have recently learned about binary space partitioning trees and their application to 3d graphics and collision detection. I have also briefly perused material relating to quadtrees and octrees. When would you use quadtrees over bsp trees, or…
Martin
  • 5,945
  • 7
  • 50
  • 77
43
votes
2 answers

R-Tree and Quadtree Comparison

I want to compare the R-Tree and the Quadtree for geospatial data. While there is literature out there I struggle to find documents that cover real basic comparison. So I decided to ask this question. In my opinion, the R-Tree has the advantage of…
Andre
  • 1,249
  • 1
  • 15
  • 38
36
votes
3 answers

Quadtree for 2D collision detection

I'm trying to use a quadtree for 2D collision detection, but I'm a little stumped on how to implement it. First of all, I'd have a quadtree which contains four subtrees (one representing each quadrant), as well as a collection of objects which don't…
bfops
  • 5,348
  • 5
  • 36
  • 48
34
votes
3 answers

Implementing a Quadtree in Mathematica

I have implemented a quadtree in Mathematica. I am new to coding in a functional programming language like Mathematica, and I was wondering if I could improve this or make it more compact by better use of patterns. (I understand that I could…
M-V
  • 5,167
  • 7
  • 52
  • 55
30
votes
1 answer

Difference between quadtree and kd-tree

What is the main difference between a quadtree and kd-tree? I understand they split points in many dimensions, but I do not understand why we would use one over the other. I need a structure that allows me to count how many points (2D points) are in…
Mauricio Galindo
  • 638
  • 1
  • 10
  • 16
20
votes
4 answers

Are any of these quad-tree libraries any good?

It appears that a certain project of mine will require the use of quad-trees, something that I have never worked with before. From what I have read they should allow substantial performance enhancements than a brute-force attempt at the problem…
Noctis Skytower
  • 21,433
  • 16
  • 79
  • 117
17
votes
1 answer

QuadTree for 2D collision detection

I'm currently working on a 2D shoot them up type of game, and I'm using a quad tree for my collision detections. I wrote a working quad tree that correctly pushes my actors into the nodes/leaves they belong to in the tree. However, I've got a few…
dotminic
  • 1,135
  • 2
  • 14
  • 28
17
votes
6 answers

Storing objects for locating by x,y coordinates

I'm trying to determine a fast way of storing a set of objects, each of which have an x and y coordinate value, such that I can quickly retrieve all objects within a certain rectangle or circle. For small sets of objects (~100) the naive approach of…
Derek Lewis
  • 1,067
  • 1
  • 10
  • 16
13
votes
3 answers

Fast method to find distance from point to closest edge of polygon

Setup Function will need to provide the distance from a point to the closest edge of a polygon Point is known to be inside of the polygon Polygon can be convex or concave Many points (millions) will need to be tested Many separate polygons (dozens)…
thaspius
  • 1,135
  • 3
  • 17
  • 33
12
votes
1 answer

What is a coarse and fine grid search?

I was reading this answer Efficient (and well explained) implementation of a Quadtree for 2D collision detection and encountered this paragraph All right, so actually quadtrees are not my favorite data structure for this purpose. I tend to prefer a…
jokoon
  • 6,207
  • 11
  • 48
  • 85
11
votes
1 answer

Using a QuadTree to get all points within a bounding circle

I have a set of 100 to 200 points (x,y). I have to check which ones fall within a particular distance of the others. The particular distance is fixed for the entire program, say 50. Say point 1 falls within the range of points…
aps
  • 2,452
  • 10
  • 35
  • 47
11
votes
3 answers

Quad tree and Kd tree

I have a set of latitude and longitude for various locations and also know the latitude and longitude of my current location. I have to find out the nearest places from current location. Which algorithm is best one from Kdtree and quadtree to find…
Kesiya Abraham
  • 753
  • 3
  • 10
  • 24
10
votes
2 answers

QuadTree find neighbor

I'm searching for a algorithm to find neighbors of a quadtree, in the example image, I got the red node, how to find the blue nodes. Any ideas?
sebbn
  • 113
  • 2
  • 2
  • 7
9
votes
1 answer

Nearest neighbor search in D3

I have implemented a 2-dimensional k-d tree in Javascript (check it out on GitHub), and I am using it for nearest-neighbor searches alongside D3. I learned that there is a quadtree implementation in D3, but also discovered that the API documentation…
Jacob Marble
  • 28,555
  • 22
  • 67
  • 78
1
2 3
…
25 26