Prev: Ricianchan and Doppler frequency spread modeling
Next: gui and simulink
From: Steve on 28 Feb 2010 23:12
Hi!

I have an empty volume of a cuboid. This volume is permanently filled with points. This points are decimal (x,y,z)-coordinates. And there lies my problem: Before a new point is added to the volume, I will check if in the neighborhood (radius r) of the proposed position another point already exists (in the volume).

This can be easily solved by euclidian distances between all points and the new point, but I have a very big volume and also a lot of points, so the calculation of the euclidian distances takes very long. However, this algo is also placed in a loop, so it will be called very often.

My idea is now to generate a 3D Heatmap or a distance map for the volume and check just via indexing (x,y, and z) if the proposed position of the new point is free (not in the neighborhood of another point). This will have the advantage that the heatmap just has to be new calculated if a new point is added, otherwise i can work with indexing, which is a lot faster!

Do you have any ideas how to do this or is something like this already existing?


Please help!!!
Thanks
From: Walter Roberson on 28 Feb 2010 23:33
Steve wrote:


> I have an empty volume of a cuboid. This volume is permanently filled
> with points. This points are decimal (x,y,z)-coordinates. And there lies
> my problem: Before a new point is added to the volume, I will check if
> in the neighborhood (radius r) of the proposed position another point
> already exists (in the volume).
> This can be easily solved by euclidian distances between all points and
> the new point, but I have a very big volume and also a lot of points, so
> the calculation of the euclidian distances takes very long. However,
> this algo is also placed in a loop, so it will be called very often.

That's the sort of reason that octtrees were invented.
From: Steve on 28 Feb 2010 23:51
> That's the sort of reason that octtrees were invented.

How can I use that?
From: Walter Roberson on 1 Mar 2010 00:35
Steve wrote:
>> That's the sort of reason that octtrees were invented.
>
> How can I use that?

http://en.wikipedia.org/wiki/Octree
http://en.wikipedia.org/wiki/Collision_detection#Optimization
 | 
Pages: 1
Prev: Ricianchan and Doppler frequency spread modeling
Next: gui and simulink