# What's the fastest way to get the points I want out of a huge blob?

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?

• The keyword you are looking for is quadtree. – user2987828 Apr 8 '14 at 21:01

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


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

• MathJax was introduced to Code Review yesterday – syb0rg Apr 8 '14 at 21:53