how to improve loops in matlab, especially with big variables.

hei, i have two loops, where each point is checked how many other points are within a certain radius.

the point is, that i have a huge point cloud. 100000 xy coordinates are one of the smaller files. - this makes is run for ever.

      radius=1;

      data=rand(100000,3);

      k=size(data,1);

      data(:,4)=0;

      for i = 1:k

          CR=[data(i,1:2) radius];

          for j=1:k

              P=data(j,1:2);

              if isPointInCircle(P, CR)
                  data(i,4)=data(i,4)+1;
              end

          end
      end

[Markus]

in the meantime i installed the kd-tree.

https://sites.google.com/site/andreatagliasacchi/software/matlabkd-treelibrary

however, i dont know how i can implement the isPointInCircle function or the loop into it.

[Markus]

the run and time analyses showed, that by 1000 datapoints the function isPointInCircle http://www.mathworks.com/matlabcentral/fileexchange/7844-geom2d/content/geom2d/geom2d/isPointInCircle.m needs about 20 seconds, while the loops need only 6 seconds. therefore is it more essential, to find a way to avoid unnecessary comparisons.

Answer 1

[Chetan Rawal]

You may want to see the vectorization link here. I tried doing the vectorization for you, but just got confused in the loops. Since you understand your program better than I do, you might be able to find a way after reading the info in this link.

[Markus]

hei, thanks for this answer. i am not sure how this works, since i dont calculate one value.

the first loop (i). chooses the point (CR) with the radius. the second loop checks every point (P) whether it is within this circle or not. if yes, the counter goes one up.

[Markus]

ill try to explain the loops: loop 1 (i = 1:k), defines the point in the point cloud with a certain radius. and each point in the point cloud has to be compared to all others, whether the point is within the distance or not.

loop 2 (j = 1 : k), chooses one point (P) after another and checks whether this point lies within the radius of the first point (CR) if yes, the counter goes up.

Answer 2

[Image Analyst]

Allocate the 4th column of data in advance of the loops. Then, data has 3 (or 4) columns so what do you think you're getting for CR and P when you refer to data(i,1:2)? What's the third index? Why are you not specifying it?

[Markus]

i did allocate it (data(:,4)=0;), or do i have a mistake in it?

the file data contains x y and z values from a point cloud. i get the i¨th point CR (x-value, y-value, radius) with the defined radius with this:

CR=[data(i,1:2) radius]

and in the second loop will all points P (x-value y-value) be tested, whether they are within radius distance from the first point. P=data(j,1:2);

what third index do you mean, which i should specifiy?

[Image Analyst]

Right - nevermind - I was thinking 3D in my head, but you have a 2D matrix. Have you tried the run and time button? I don't have isPointInCircle() so I can't really help a lot.

[Image Analyst]

You mgiht try pulling the CR and P out of the loops:

        CR=data(:,1:2);
      CR(:,3) = radius;
        P=data(:,1:2);
      for i = 1:k
            ci = CR(i,:);
            for j=1:k
          pj = P(j,:);
  %               if isPointInCircle(pj, ci)
  %                   data(i,4)=data(i,4)+1;
  %               end

            end
      end

[Markus]

i did the run and time (guess our posts did overlap) :) : the run and time analyses showed, that by 1000 datapoints the function isPointInCircle

 http://www.mathworks.com/matlabcentral/fileexchange/7844-geom2d/content/geom2d/geom2d/isPointInCircle.m

needs about 20 seconds, while the loops need only 6 seconds. therefore is it more essential, to find a way to avoid unnecessary comparisons.

i am gonna try your idea and let you know the results.

[Markus]

i tried this and it went faster. unfortunatly only one second. - the problem is, that i need to get rid of unnecessary loops. so that points wich are far out of range are not going to be tested again. or i need a method, to skip the points in the second loop, when they have been tested in the first loop.

Generated 14-Sep-2013 18:13:12 using cpu time.

Function Name      Calls  Total Time    Self Time*Total Time Plot

cleanPointClouds     1    24.952 s       5.131 s

isPointInCircle  1000000  19.822 s       19.822 s