4
\$\begingroup\$

In MATLAB I have a set of 5393280 points in the form of a decimal-valued vector (x,y,z). How do I represent them in a way that I can quickly collect all the points within some rectangular x-y domain?

Right now I'm representing them as a 3-column matrix, sorted by x-values, and using the following code to extract a rectangular region:

mtx_region = mtx_pointList( dxLowerBound < mtx_pointList(:,1) & ...
                            dxUpperBound > mtx_pointList(:,1) & ...
                            dyLowerBound < mtx_pointList(:,2) & ...
                            dyUpperBound > mtx_pointList(:,2), : );

However, I suspect that this is slowing my code down considerably.

What is a better way?

\$\endgroup\$
  • 1
    \$\begingroup\$ The keyword you are looking for is quadtree. \$\endgroup\$ – user2987828 Apr 8 '14 at 21:01
3
\$\begingroup\$

Prefiltering all relevant x-values with a binary search could speed up the process.

[a,A]=myFind2(mtx_region(:,1),dxLowerBound,dxUpperBound);

xpoints=mtx_region(a:A,:);
mtx_region = xpoints(     dyLowerBound < xpoints(:,2) & ...
                            dyUpperBound > xpoints(:,2), : );

Binary search on sorted arrays is already discussed here.

function [b,c]=myFind2(x,A,B)
a=1;
b=numel(x);
c=1;
d=numel(x);
while (a+1<b||c+1<d)
    lw=(floor((a+b)/2));
    if (x(lw)<A)
        a=lw;
    else
        b=lw;
    end
    lw=(floor((c+d)/2));
    if (x(lw)<=B)
        c=lw;
    else
        d=lw;
    end
end
end
\$\endgroup\$
2
\$\begingroup\$

if you only need to select once then there is no need to sort at all; filtering can happen in \$ O \left( n \right) \$ while the sort needs \$ O \left( n \log n \right) \$

if you need to select multiple times then put them in a \$ n \times n \$ grid structure, where each grid is a list of points that lie within it

\$\endgroup\$
  • 1
    \$\begingroup\$ MathJax was introduced to Code Review yesterday \$\endgroup\$ – syb0rg Apr 8 '14 at 21:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.