Stack Overflow
Stack Overflow

Questions tagged [space-partitioning]

36 questions
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
13
votes
8 answers

Space partitioning algorithm

I have a set of points which are contained within the rectangle. I'd like to split the rectangles into subrectangles based on point density (giving a number of subrectangles or desired density, whichever is easiest). The partitioning doesn't have…
Karol Kolenda
  • 1,660
  • 2
  • 25
  • 37
12
votes
1 answer

Partitioning big rectangle to small ones (2D Packing)

I need algorithm which splits big static sized rectangle to small ones. A perfect implementation for me look like this: struct RECT { int l,t,r,b; }; class BigRect { public: // width and height of big rect BigRect( unsigned width, unsigned…
pure cuteness
  • 1,635
  • 11
  • 26
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
9
votes
3 answers

Binary Space Partitioning Data Structure For Donut 2D Space

I have a 2D map which wraps at the edges. So if you move off the right edge you will reappear at the left side of the map. Likewise with the three other edges. This is inheritable a problem for the KDTree which I use to find elements in range of…
Kasper Holdum
  • 12,993
  • 6
  • 45
  • 74
7
votes
1 answer

Looking for a good space-partitioning data structure to generate millions of atomic bonds quickly from

I'm performing some MD simulations involving systems of millions of atoms. I have written some code to generate a file which is just a listing of XYZ atom coordinates. Now I need to generate bonds between the atoms. If two atoms are within a…
Nick
  • 5,228
  • 9
  • 40
  • 69
6
votes
4 answers

Nearest neighbor zones visualized

I'm writing an app that looks up points in two-dimensional space using a k-d tree. It would be nice, during development, to be able to "see" the nearest-neighbor zones surrounding each point. In the attached image, the red points are points in the…
Jacob Marble
  • 28,555
  • 22
  • 67
  • 78
6
votes
2 answers

Octree implementation for triangular mesh and particles

I am currently working in an efficient calculation engine for particle simulation both in CPU and GPU. I have been working lately in octrees and I managed to write a working version of octree for particles in space and also efficiently handled their…
rawcoder
  • 113
  • 1
  • 9
5
votes
2 answers

How does space partitioning algorithm for finding nearest neighbors work?

For finding the nearest neighbor, Space Partitioning is one of the algorithms. How does it work? Suppose I have a 2D set of points (x and y coordinates), and I am given a point (a,b). How would this algorithm find out the nearest neighbor?
Moeb
  • 10,527
  • 31
  • 84
  • 110
4
votes
3 answers

How to eliminate colliding markers in Google Maps

I should show a set of markers on map to indicate nearby points of interest. These markers will open public chat rooms by click and therefore I think the users should see short address information about each marker before entering that room without…
Dorukhan Arslan
  • 2,676
  • 2
  • 24
  • 42
4
votes
2 answers

How to perform spatial partitioning in n-dimensions?

I'm trying to design an implementation of Vector Quantization as a c++ template class that can handle different types and dimensions of vectors (e.g. 16 dimension vectors of bytes, or 4d vectors of doubles, etc). I've been reading up on the…
kevin42
  • 2,108
  • 3
  • 22
  • 21
4
votes
1 answer

data structure for movable points in 3d

I have many points (+100,000) in 3 dimensional space. I need to use nearest neighbor and range queries. Firstly I used kdtree (k=3) but each point has a velocity attribute. Their location is not static, they change their location. The problem begins…
Taha Altuntaş
  • 93
  • 1
  • 1
  • 4
3
votes
1 answer

2D Spatial partitioning alternatives to spatial hashes and quadtrees

I've been trying to implement a spatial partitioning algorithm in my game, but both spatial hashes and quadtrees aren't what I'm looking for. My level size is not supposed to have a limit (only Int32 limits). I need a spatial partitioning algorithm…
Vittorio Romeo
  • 90,666
  • 33
  • 258
  • 416
3
votes
6 answers

Thousands of rays intersections with Triangles in 3D space

There are thousands of rays and triangles. We need get all the intersection points. If we use the normal two level loops,we need O(mn) time complexity.Is there any way to low the time complexity fronm O(mn) to O(m* logn) or O(logm*n)? Best Regards,
ET 0.618
  • 3,433
  • 4
  • 17
  • 5
3
votes
3 answers

How to do a space-partitioning of the Utah Teapot?

Having dealt with converting the Bezier Patches into triangles, I need to do a Binary Space Partition in order to draw the projected triangles using the Painter's Algorithm. I've implemented the algorithm from Wikipedia with much help with the…
luser droog
  • 18,988
  • 3
  • 53
  • 105
1
2 3