Make grid from patch object

Hi

I am trying to make a function for splitting a patch object into N equally sized indexed rectangles (like a grid). The intended use is that the patch object contains the (x,y) values for a floor in a room, and I want to split the room into N number of rectangles which later will be used to make a "Region of Interest" in an optimization problem.

Any help would be highly appreciated.

[Rik]

It might be an overpowered tool, but the FEX submission intriangulation might be of help here.

[Walter Roberson]

So for example it needs to be able to divide up a room that looks like this:

             -----
             |   |
     ________|   |
     |           |
     |        ___|
     |        |
     |________|

into

             -----
             |   |
     ________|   |
     |   +   +   |
     |   +   +___|
     |   +    |
     |___+____|

for N = 3, declare failure for N = 4 or N =5, for N = 6 it could subdivide those horizontally or could instead divide into 2 x 2 squares? And for higher numbers with more irregular walls it might have to "jig-saw", using a mix of horizontal and vertical orientations to fit all of the edge conditions?

https://community.esri.com/thread/45459

[proczell]

Yes, that is the general idea, although it should be noted that the room is not necesarilly make up op straight lines, it could look something like:

|\
| \
|  \  /\ 
|   \/  \
|       |
|       |    
|       |
|_______|

which may make it a bit more complicated. The thread you posted looks like is largely related to the same problems, although not in Matlab. Do you know any Matlab tools that may be helpful? If not I will certainely look through that thread and see if there may be anything helpful. Thanks!

My latest idea is in the lines of dividing the polygon with Delauney Triangulation and then try to divide the triangles into new cells again. But I don't know if it will be a good solution.

Thanks for your answer!

[Walter Roberson]

In order to be able to divide an area into rectangles that are not infinitely small, all internal angles must be multiples of 90 degrees -- unless, that is, it is permitted to have space left over, in which case ideally you would prefer to minimize the space left over.

[proczell]

That is true. Some space needs to be left over, but if the space is close to the "walls" it should be okay.

[proczell]

Do you know if Matlab includes any kind of "fishnet" function to divide polygons?

[Walter Roberson]

MATLAB itself does not have such a function.

I do not find such a function for MATLAB when I google, but perhaps different keywords would make a difference.

[proczell]

I have not found any functions, from Matlab, Python or any other language I am familiar with. May have to try and make the function myself as it is absolutely necessary for my task.. Thanks for your help!

[Walter Roberson]

With calls to arcgis: https://gis.stackexchange.com/questions/115351/automate-splitting-polygons-into-sections

Not sure of the requirements of the following python: https://github.com/rory/grid-polygons

[proczell]

I will check those out! Thank you.

[proczell]

Since you have shown interest in helping me, I though I would post the current code, which seems to have a good potential.

area = 45.020; 
sq_area = area/50; 
side = sqrt(sq_area); 
ylim = 5; 
xlim = 4; 
i = 1; 
origin = [0 ;0]
L = origin;
figure

bOK = true
while(bOK)

    L = [origin(1) ;origin(2)+side]; 
    B = [origin(1) + side ;origin(2)];
    R = [origin(1) + side ;origin(2) + side]; 

    if L(1) < xlim 

        if L(2) < ylim
        cubes{i} = [origin B R L origin]
        curr_cube = cubes{i}
        hold on
        plot(curr_cube(1,1:end),curr_cube(2,1:end),'b')

        origin = [L(1) ;L(2)]
        i = i + 1; 
        else
        cubes{i} = [origin B R L origin]
        curr_cube = cubes{i}
        hold on
        plot(curr_cube(1,1:end),curr_cube(2,1:end),'b')  

        origin = [B(1) ;0]
        i = i + 1;         
        end
    else
        bOK = 0; 
    end
    pause(0.5)
end

This will swipe along the y-axis, but could easily be extended to a possibility for swiping along the x-axis. The final problem to solve is to make xlim and ylim dynamic according to the given room, a problem I think is highly solvable.

[proczell]

Another update. This works as intended, but if anyone finds improvements or errors, please let me know.

clear all ;close all; clc
x = [0 18.01 18 14.51 0]; 
y = [0 0 0 0 0]; 
z = [0 0 5.0 2.5 24]; 

% Patch object 
nlin = 200; 
for i = 1:length(x)
    if i == length(x)
        if x(i) == x(1)
            x_l(i,1:nlin) = x(i);
            y_l(i,1:nlin) = linspace(z(i),z(1),nlin); 
        else  
            xd = x(i) + x(1); zd = z(i) + z(1); 
            m = (z(i) - z(1))/(x(i) - x(1)); 
            x_l(i,1:nlin) = linspace(x(i),x(1),nlin); 
            y_l(i,1:nlin) = m*x_l(i,1:nlin) - m*x(i) + z(i); 
        end
    else
    xd = x(i) + x(i+1); zd = z(i) + z(i+1); 
    m = (z(i) - z(i+1))/(x(i) - x(i+1)); 
    x_l(i,1:nlin) = linspace(x(i),x(i+1),nlin);
    y_l(i,1:nlin) = m*x_l(i,1:nlin) - m*x(i) + z(i); 
    end   
end    

y_l = [y_l(1,1:end) y_l(2,1:end) y_l(3,1:end) y_l(4,1:end),y_l(5,1:end)]; 
x_l = [x_l(1,1:end) x_l(2,1:end) x_l(3,1:end) x_l(4,1:end) x_l(5,1:end)]; 
% hold on
figure
p = patch(x,y,z,'r')
figure
scatter(x_l,y_l)

% Compute area
verts = get(p, 'Vertices');
faces = get(p, 'Faces');
a = verts(faces(:, 2), :) - verts(faces(:, 1), :);
b = verts(faces(:, 3), :) - verts(faces(:, 1), :);
c = cross(a, b, 2);
area = 1/2 * sum(sqrt(sum(c.^2, 2)));

% Fishnet generation
area = 45.020; 
sq_area = area/50; 
side = sqrt(sq_area); 
ylim = 5; 
xlim = 4; 
i = 1; 
origin = [0 ;0]
L = origin;

x_2 = round(x_l,1);
xlim = max(x_l)

bOK = true
while(bOK)

    L = [origin(1) ;origin(2)+side]; 
    B = [origin(1) + side ;origin(2)];
    R = [origin(1) + side ;origin(2) + side]; 
    L_2 = round(R(1),1); 
    x_current = find(x_2==L_2)
    for i = 1:length(x_current)
        y_vals = y_l(x_current); 
        ylim = max(y_vals)
    end
    if L(1) < xlim 

        if L(2) < ylim
            cubes{i} = [origin B R L origin];
            curr_cube = cubes{i};
            hold on
            plot(curr_cube(1,1:end),curr_cube(2,1:end),'k')

            origin = [L(1) ;L(2)]
            i = i + 1; 
        else
            cubes{i} = [origin B R L origin];
            curr_cube = cubes{i};
            hold on
            plot(curr_cube(1,1:end),curr_cube(2,1:end),'k')  

            origin = [B(1) ;0]
            i = i + 1;         
        end
    else
        bOK = 0; 
    end
    pause(0.03)
end