Hi Saul,
thank you for your reply.
On 13 Feb., 13:18, (EMail Removed) wrote:
> On Feb 13, 8:38*am, "Marco Körner" <(EMail Removed)> wrote:>
> > I'm working on mapping the car's environment by updating an occupancy
> > grid. An occupancy grid dicretizes the 3D space in small grid elements
> > (voxels). A grid element contains informations about the space it's
> > representing.
>
> I recently did something similar to this in 6D where I used my own
> datastructures.
>
> > I need to map a space of the dimensions 50m * 5m * 3m with grid
> > elements of size 1cm * 1cm * cm (= 750 000 000 grid elements).
>
> Does every element in the grid contain data? In my case they didn't,
> and I found a sparse matrix was the best data structure to use.
Yes, normally it does. I would like to implement a probabilistic
approach, so every grid element is initialized with probability 0.5.
> > My question is how to implement such a data structure in an efficient
> > way. I need to access fast by indizes. Access by iterators is not
> > needed. The implentation has to be dynamic because of the iterative
> > mapping process.
>
> I'd consider a 3D matrix or 3D sparse matrix. I've not used them, but
> google shows there are some free implementations.
>
> > My idea was to store all voxels in a long std::vector<double> and let
> > pointing a kdtree's leafs on the vector elements. But this would have
> > the drawback that the kdtree has to be reorganized during the update
> > process to avoid a degeneration to a linear list.
>
> Are there any advantages to using a kdtree that can't be done by
> indexing a 3D matrix (this is a genuine question)?
I don't know. My idea was to create a grid element if it's not
allready stored in the vector. The kdtree would be used to find and
access each grid element in logarithmic time O(log N) instead of
search linear through the vector of grid elements in O(N). The
advantage would be, that I just manage cells I've previously touched.
Queries for all other grid elements would return the initial value.
