Create a Forum Topic by Logging In or Creating an Account

speeding up imagetransform voronoi?

Thu, 07/18/2013 - 04:22 pm

I have a 3x1 million point scatter plot (xyz triplet wave) which i want to interpolate to a 2500 x 400 point 2d matrix. I tried the imagetransform/s={...} voronoy, tripletWave command, but it is very slow for this large dataset. Is there any way to achieve this interpolation in a faster way?

Background: we measure a LIDAR (laser ranging) point cloud of an object using a scanning mirror, i.e. each point is composed of a measured distance between mirror and object and two angles. Both mirror angles are modulated with triangular waveforms that have a period of 2500 points (horizontal) respectively 2500x400 points (vertical), resulting in 1 million data points. We then transform the point cloud from spherical coordinates to cartesian coordinates. We want to create a surface image of our LIDAR point cloud in cartesian coordinates.

Thanks,
Fabrizio

Igor

Hello Fabrizio,

I would not attempt this size of a problem with ImageInterpolate Voronoi -- and I am only referencing the input size.

The main issue here is the triangulation which is O(N^2). The interpolation part is linear in rows*columns. The triangulation algorithm does not support multi-threading and that is the core problem.

If you absolutely have to proceed with this approach I'd recommend pre-sorting the input points radially out from the CM of the data. Other approaches involve pre-sorting and splitting the input into smaller data sets and then trying to fuse the sets along boundaries.

It seems to me that in your application it should be possible to convert the coordinates in a more deterministic manner. Feel free to send me an experiment via support@wavemetrics.com and I'll try to help.

A.G.
WaveMetrics, Inc.

July 18, 2013 at 05:27 pm - Permalink