Efficient represention for growing circles in 2D space?(stackoverflow.com)

13 pointsby DanWaterworth15 anni fa3 comments

Efficient represention for growing circles in 2D space?

http://stackoverflow.com/questions/9031778/efficient-represention-for-growing-circles-in-2d-space

2 comments

akg15 anni fa

If you have a large domain with a large number of N circles, you could try using a B-Tree like approach. Basically partitioning your domain in a N-Tree (instead of a traditional quad-tree). The wide branching factor per node will give you a shallower tree that's more efficient if you are doing lots of updates to the data-structure. You can also rid yourself of pointers to do really fast traversals through your N-Tree using an approach like (http://www.matmidia.mat.puc-rio.br/tomlew/publication_page.p...). Lewiner et. al. talk about oct-trees there, but it could be generalized.

I have some code that implements such a data-structure in 3D (should be easily modifiable to 2D). I can mail you the source if you are interested.

ajuc15 anni fa

Well, growing 2d circles are just static sliced cones in 3d.

So maybe some 3d space partitioning technique will do.

EDIT: but I can't really think of any suitable for indexing big long cones. So it's no really useful idea :/

mchouza15 anni fa

You can try posting your question in http://cstheory.stackexchange.com/