What is an simple way to compute the overlap betwe

Question

I have a closed non-self-intersecting polygon. Its vertices are saved in two vectors X, and Y. Finally the values of X and Y are bound between 0 and 22.

I'd like to construct a matrix of size 22x22 and set the value of each bin equal to true if part of the polygon overlaps with that bin, otherwise false.

My initial thought was to generate a grid of points defined with [a, b] = meshgrid(1:22) and then to use inpolygon to determine which points of the grid were in the polygon.

[a b] = meshgrid(1:22);
inPoly1 = inpolygon(a,b,X,Y);

However this only returns true if if the center of the bin is contained in the polygon, ie it returns the red shape in the image below. However what need is more along the lines of the green shape (although its still an incomplete solution).

To get the green blob I performed four calls to inpolygon. For each comparison I shifted the grid of points either NE, NW, SE, or SW by 1/2. This is equivalent to testing if the corners of a bin are in the polygon.

inPoly2 = inpolygon(a-.5,b-.5,X,Y) | inpolygon(a+.5,b-.5,X,Y) | inpolygon(a-.5,b+5,X,Y) | inpolygon(a+.5,b+.5,X,Y);

While this does provide me with a partial solution it fails in the case when a vertex is contain in a bin but none of the bin corners are.

Is there a more direct way of attacking this problem, with preferably a solution that produces more readable code?

This plot was drawn with:

imagesc(inPoly1 + inPoly2); hold on;
line(a, b, 'w.');
line(X, Y, 'y); 

Answer 1

One suggestion is to use the polybool function (not available in 2008b or earlier). It finds the intersection of two polygons and returns resulting vertices (or an empty vector if no vertices exist). To use it here, we iterate (using arrayfun) over all of the squares in your grid check to see whether the output argument to polybool is empty (e.g. no overlap).

N=22;
sqX = repmat([1:N]',1,N);
sqX = sqX(:);
sqY = repmat(1:N,N,1);
sqY = sqY(:);

intersects = arrayfun((@(xs,ys) ...
      (~isempty(polybool('intersection',X,Y,[xs-1 xs-1 xs xs],[ys-1 ys ys ys-1])))),...
      sqX,sqY);

intersects = reshape(intersects,22,22);

Here is the resulting image:

Code for plotting:

imagesc(.5:1:N-.5,.5:1:N-.5,intersects');
hold on;
plot(X,Y,'w');
for x = 1:N
    plot([0 N],[x x],'-k');
    plot([x x],[0 N],'-k');
end
hold off;

Answer 2

Well, I guess I am late, though strictly speaking the bounty time was till tomorrow ;). But here goes my attempt. First, a function that marks cells that contain/touch a point. Given a structured grid with spacing lx, ly, and a set of points with coordinates (Xp, Yp), set containing cells:

function cells = mark_cells(lx, ly, Xp, Yp, cells)

% Find cell numbers to which points belong.
% Search by subtracting point coordinates from
% grid coordinates and observing the sign of the result.
% Points lying on edges/grid points are assumed
% to belong to all surrounding cells.

sx=sign(bsxfun(@minus, lx, Xp'));
sy=sign(bsxfun(@minus, ly, Yp'));
cx=diff(sx, 1, 2);
cy=diff(sy, 1, 2);

% for every point, mark the surrounding cells
for i=1:size(cy, 1)
    cells(find(cx(i,:)), find(cy(i,:)))=1;
end
end

Now, the rest of the code. For every segment in the polygon (you have to walk through the segments one by one), intersect the segment with the grid lines. Intersection is done carefully, for horizontal and vertical lines separately, using the given grid point coordinates to avoid numerical inaccuracies. For the found intersection points I call mark_cells to mark the surrounding cells to 1:

% example grid
nx=21;
ny=51;
lx = linspace(0, 1, nx);
ly = linspace(0, 1, ny);
dx=1/(nx-1);
dy=1/(ny-1);
cells = zeros(nx-1, ny-1);

% for every line in the polygon...
% Xp and Yp contain start-end points of a single segment
Xp = [0.15 0.61];
Yp = [0.1 0.78];

% line equation
slope = diff(Yp)/diff(Xp);
inter = Yp(1) - (slope*Xp(1));

if isinf(slope)
    % SPECIAL CASE: vertical polygon segments
    % intersect horizontal grid lines
    ymax = 1+floor(max(Yp)/dy);
    ymin = 1+ceil(min(Yp)/dy);
    x=repmat(Xp(1), 1, ymax-ymin+1);
    y=ly(ymin:ymax);
    cells = mark_cells(lx, ly, x, y, cells);
else
    % SPECIAL CASE: not horizontal polygon segments
    if slope ~= 0
        % intersect horizontal grid lines
        ymax = 1+floor(max(Yp)/dy);
        ymin = 1+ceil(min(Yp)/dy);
        xmax = (ly(ymax)-inter)/slope;
        xmin = (ly(ymin)-inter)/slope;
        % interpolate in x...
        x=linspace(xmin, xmax, ymax-ymin+1);
        % use exact grid point y-coordinates!
        y=ly(ymin:ymax); 
        cells = mark_cells(lx, ly, x, y, cells);
    end

    % intersect vertical grid lines
    xmax = 1+floor(max(Xp)/dx);
    xmin = 1+ceil(min(Xp)/dx);
    % interpolate in y...
    ymax = inter+slope*lx(xmax);
    ymin = inter+slope*lx(xmin);
    % use exact grid point x-coordinates!
    x=lx(xmin:xmax); 
    y=linspace(ymin, ymax, xmax-xmin+1);
    cells = mark_cells(lx, ly, x, y, cells);
end

Output for the example mesh/segment:

Walking through all polygon segments gives you the polygon 'halo'. Finally, the interior of the polygon is obtained using standard inpolygon function. Let me know if you need more details about the code.

Answer 3

I would suggest using poly2mask in the Image Processing Toolbox, it does more or less what you want, I think, and also more or less what youself and Salain has suggested.

Answer 4

How about this pseudocode algorithm:

For each pair of points p1=p(i), p2=p(i+1), i = 1..n-1
    Find the line passing through p1 and p2
    Find every tile this line intersects // See note
    Add intersecting tiles to the list of contained tiles

Find the red area using the centers of each tile, and add these to the list of contained tiles

Note: This line will take a tiny bit of effort to implement, but I think there is a fairly straightforward, well-known algorithm for it.

Also, if I was using .NET, I would simply define a rectangle corresponding to each grid tile, and then see which ones intersect the polygon. I don't know if checking intersection is easy in Matlab, however.

Answer 5

Slight improvement

Firstly, to simplify your "partial solution" - what you're doing is just looking at the corners. If instead of considering the 22x22 grid of points, you could consider the 23x23 grid of corners (which will be offset from the smaller grid by (-0.5, -0.5). Once you have that, you can mark the points on the 22x22 grid that have at least one corner in the polygon.

Full solution:

However, what you're really looking for is whether the polygon intersects with the 1x1 box surrounding each pixel. This doesn't necessarily include any of the corners, but it does require that the polygon intersects one of the four sides of the box.

One way you could find the pixels where the polygon intersects with the containing box is with the following algorithm:

For each pair of adjacent points in the polygon, calling them pA and pB:
    Calculate rounded Y-values: Round(pA.y) and Round(pB.y)
    For each horizontal pixel edge between these two values:
        * Solve the simple linear equation to find out at what X-coordinate
          the line between pA and pB crosses this edge
        * Round the X-coordinate
        * Use the rounded X-coordinate to mark the pixels above and below
          where it crosses the edge
    Do a similar thing for the other axis

So, for example, say we're looking at pA = (1, 1) and pB = (2, 3).

• First, we calculated the rounded Y-values: 1 and 3.
• Then, we look at the pixel edges between these values: y = 1.5 and y = 2.5 (pixel edges are half-offset from pixels
• For each of these, we solve the linear equation to find where pA->pB intersects with our edges. This gives us: x = 1.25, y = 1.5, and x = 1.75, y = 2.5.
• For each of these intersections, we take the rounded X-value, and use it to mark the pixels either side of the edge.
  • x = 1.25 is rounded to 1 (for the edge y = 1.5). We therefore can mark the pixels at (1, 1) and (1, 2) as part of our set.
  • x = 1.75 is rounded to 2 (for the edge y = 2.5). We therefore can mark the pixels at (2, 2) and (2, 3).

So that's the horizontal edges taken care of. Next, let's look at the vertical ones:

• First we calculate the rounded X-values: 1 and 2
• Then, we look at the pixel edges. Here, there is only one: x = 1.5.
• For this edge, we find the where it meets the line pA->pB. This gives us x = 1.5, y = 2.
• For this intersection, we take the rounded Y-value, and use it to mark pixels either side of the edge:
  • y = 2 is rounded to 2. We therefore can mark the pixels at (1, 2) and (2, 2).

Done!

Well, sort of. This will give you the edges, but it won't fill in the body of the polygon. However, you can just combine these with your previous (red) results to get the complete set.

Answer 6

First I define a low resolution circle for this example

X=11+cos(linspace(0,2*pi,10))*5;
Y=11+sin(linspace(0,2.01*pi,10))*5;

Like your example it fits with in a grid of ~22 units. Then, following your lead, we declare a meshgrid and check if points are in the polygon.

stepSize=0.1;
[a b] = meshgrid(1:stepSize:22);
inPoly1 = inpolygon(a,b,X,Y);

Only difference is that where your original solution took steps of one, this grid can take smaller steps. And finally, to include anything within the "edges" of the squares

inPolyFull=unique( round([a(inPoly1) b(inPoly1)]) ,'rows');

The round simply takes our high resolution grid and rounds the points appropriately to their nearest low resolution equivalents. We then remove all of the duplicates in a vector style or pair-wise fashion by calling unique with the 'rows' qualifier. And that's it

To view the result,

[aOrig bOrig] = meshgrid(1:22);
imagesc(1:stepSize:22,1:stepSize:22,inPoly1); hold on;
plot(X,Y,'y');
plot(aOrig,bOrig,'k.');
plot(inPolyFull(:,1),inPolyFull(:,2),'w.'); hold off;

Changing the stepSize has the expected effect of improving the result at the cost of speed and memory.

If you need the result to be in the same format as the inPoly2 in your example, you can use

inPoly2=zeros(22);
inPoly2(inPolyFull(:,1),inPolyFull(:,2))=1

Hope that helps. I can think of some other ways to go about it, but this seems like the most straightforward.