Proximity Algorithm

[Nameless]

Hi everyone. I don't know if this is the best forum to post this but this didn't seem like a math or physics problem so I figured this would be the next best fit.

I'm looking for some background on the following problem: I have a (3d or 2d) point cloud, and for every point (player) I need to calculate a visibility set of all other points within a radius r (let's say that all players have the same r for now). The naive solution is n^2.

Basically I'm not sure what keywords to google for. I've tried algorithm proximity/range/radius/etc. but the best I could find was 'nearest neighbour search', which isn't what I need. Also the players will of course always be moving so I can't build a kd-tree.

Thanks in advance for any help!

[.oisyn]

Divide and conquer; subdivision is your friend :)

[Nameless]

Indeed... but what I'm looking for is maybe a good link so I can research the problem in more depth.

Right now the best I would do is something like this: http://www.cs.sunysb.edu/~algorith/files/range-search.shtml

(Keep a sorted list by every dimension: 3*nlogn, find approximate neighbours for every point: n*3logn. So nlogn overall, but with a steep constant term).

I get the feeling that there's a much better algorithm out there though since I can already think of some optimizations (if 'r' is the same for every player, then adding player1 to player2's list means player2 is automaticalyl in player1's list, etc.)

[roxtar]

I really don't have much idea of range searching, but I managed to dig up this:

http://www.cs.wustl.edu/~pless/506/l11w.html

Hope it helps.

[bladder]

if your radii are all the same then one thing to keep in mind when iterating through the points is that if A can see B then that automatically implies that B can see A. Another thing to keep in mind regardless of whether your radii are the same or not is that you can probably sort the points from left to right, so when you check for what point A can see, after a certain point there is no need to check because all the rest of the points are too far right.

Same thing if you are checking a point in the middle somewhere. For example you'd know that:

Point A's radius is 5
After the 100th point, the x values are A.x - 5
So you start checking from after the 100th point until you reach a point whose X value is greater the A.x + 5

Does that make sense?

[baldurk]

For reference this is more appropriate in the maths & physics forum.

[Nameless]

Okay thanks everyone. I'll keep indexes on each dimension and just do 'n' lookups. I was just wondering if there is a better data structure for this kind of problem, but this should be good enough.

[m4x0r]

The exact solution you choose depends on a lot of additional factors, but sweep and prune can be used to solve this problem pretty efficiently.

Max

[maglos]

I was woundering how an mmorpg would solve this problem, a r-tree or even a quad-tree seems like it could be expensive with fast action, requiring frequent reorganizing, although im sure it could be optimized for this. Is their any other methods that could work?

[SigKILL]

I wrote a lenghty answer earlier today, but I lost my internet connection. Anyways, the short one: Try to find John Ratcliffs sphere tree article (It's in GPG 2, but it used to be on the 'net somewhere, and it is used in a MMO), I don't see a quadtree/octree would be expensive unless when poorly implemented (I can see when it is sub-optimal though).

-si

[GroundKeeper]

There is a hash solution that would run in O(n) time.. =) Try the book "Algorithm Design by Jon Kleinberg and Eva Tardos"
(In 2D)

[Altair]

You can just put all players into a grid and just process grid cells that are completely or partially inside the view range (fast to check). If a grid cell is completely inside the range of a player then all players inside that cell are in the view. If the cell is partially inside, then just run the regular distance check for those players. It's still O(n^2) worst case if all players are in cells that are partially inside each players view range, but properly selecting the cell size should fix that.

Cheers, Altair

[Willem]

This problem can easily be solved in O(log N) time and O(N) storage using a kD-tree with a point from your cloud for each node in the tree. If you choose as your splitting-plane the median of the points along any of the three axes the resulting tree is guaranteed to be perfectly balanced.

Henrik W. Jensen wrote a fast implementation for his book on photon mapping. I'm sure there's other implementations floating 'round the web.

Cheers,
Willem

[Willem]

And this is where I failed to read your last line, doh! :(
That and the fact that you need this for *every* point in the cloud, not just one, making the kD-tree algorithm's running time O(N log N)

A naive solution would be to uniformly discretise your space; you don't even need to construct a grid for this, just discretise your coordinates along the axes. Still worst-case O(N^2) :(

[Altair]

A naive solution would be to uniformly discretise your space; you don't even need to construct a grid for this, just discretise your coordinates along the axes. Still worst-case O(N^2) :(
You need a grid to quickly detect which players are in close proximity of a point, because otherwise you'll have Theta(n^2) run-time. With grid you get O(n^2) but Omega(n) where O(n^2) is quite rare case. Another good thing with naive grid is that it fits well dynamic objects (e.g. players), so updates are fast.

Cheers, Altair

[Willem]

Conceptually it's a grid yes. However the implementation could be as simple as a hash-table: since you've discretised the coordinates, you can construct a perfect-hash and store everything in a hash-table. I guess this would just be *an* implementation of a grid.