n*n blocks and polygons

Question

Hi, this is actually meant to be for a function called roipoly in matlab but it can be considered a general case problem.

Roipoly is a function which lets u select a polygon over an image, and returns a binary mask where u can use it to get indices of the desired polygon. (It is just a normal polygon after all).

My application (K-Nearest Neighbor) requires that i make n*n blocks out of the data i have (the polygon), i.e. If i have a polygon (a road or a piece of land), i want a n*n square moving over it while avoiding intersection with edges and putting those n*n pixels into some variable.

This problem would be a lot easier if i had all my shapes in the form of rectangles, but that unfortunately isn't the case. I might have something going diagonal, circular or just irregular.

Is there a known algorithm i can implement? or something that already does this or can make it easier in matlab?

I'm already working on it but its quite tricky, i want to make sure I'm not wasting time reinventing a wheel somewhere.

Any ideas?

Answer 1

I'm not entirely sure what you want, but lets assume it's this: You have a binary mask, and you want all (possibly overlapping) n*n squares that fit.

You can try this by generating all possible n*n squares and then discarding all that do not fit inside the polygon.

For example

%# create a circle - this is the binary mask
bw = false(101);
[xx,yy] = ndgrid(-50:50,-50:50);
bw((xx.^2+yy.^2)<625)=true;

%# since we'd want to know which windows fit, we'll collect the linear indices
%# pointing into bw. Thus, we need an array of the same size as bw that contains
%# the linear index of each pixel
indexMask = zeros(size(bw));
indexMask(:) = 1:numel(indexMask);

%# create all possible 5*5 windows with im2col. 
allWindows = im2col(indexMask,[5,5]);

%# discard all windows that lay even partially outside the mask
goodWindowIdx = all(bw(allWindows),1);

goodWindows = allWindows(:,goodWindowIdx);

Every column in goodWindows lists the indices corresponding to one position of a 5*5 mask that completely lies inside the polygon (circle in my case).