# Method to get as large and few as number boxes

3 views (last 30 days)

Show older comments

Pete sherer
on 18 Oct 2023

Commented: Pete sherer
on 20 Oct 2023

oriLat=[48.3860120000000;49.3686790000000;48.0145280000000;46.6825390000000;47.4787370000000;46.5073030000000;46.5176190000000;44.9243550000000;45.2906840000000;42.3015220000000;41.9182910000000;44.6990460000000;45.7893010000000;45.2741950000000;43.7351650000000;43.8312240000000;41.7326470000000;41.3863160000000;44.9774490000000;45.2345130000000;47.3537330000000;44.8174190000000;43.3218860000000;41.5511100000000;39.4791860000000;37.8949860000000;37.1004480000000;39.4531150000000;38.0365030000000;38.6352170000000;35.2258250000000;31.1253830000000;26.7715300000000;24.8661310000000;29.9185130000000;30.6849560000000;30.0184100000000;28.9338120000000;29.4307800000000;27.9083070000000;25.8403780000000;29.7380790000000;28.9821380000000;31.7520090000000;31.3322390000000;34.5540170000000;40.2609740000000;46.2591090000000;48.3860120000000];

oriLon=[-124.725839000000;-94.9521110000000;-89.4892260000000;-91.9618890000000;-87.9292690000000;-87.3667670000000;-84.1179250000000;-87.8434330000000;-86.9777800000000;-87.8347690000000;-86.5978990000000;-86.2484740000000;-84.7727650000000;-83.3851040000000;-83.9477400000000;-82.6336410000000;-83.4538320000000;-82.4605990000000;-74.9927560000000;-70.8444300000000;-68.2697100000000;-66.9498950000000;-70.5538540000000;-69.9649820000000;-75.5930680000000;-75.3386230000000;-75.9796080000000;-76.0123120000000;-76.3220930000000;-77.2467040000000;-75.5336270000000;-81.4020960000000;-80.0321200000000;-80.6511890000000;-83.6792190000000;-88.0083960000000;-89.8450650000000;-89.4009660000000;-94.6703890000000;-97.0033250000000;-97.4226360000000;-101.400636000000;-103.281190000000;-106.417940000000;-111.074825000000;-120.622575000000;-124.363414000000;-123.547659000000;-124.725839000000];

N = 100 ; % can be varied

lon = linspace(min(oriLon),max(oriLon),N) ;

lat = linspace(min(oriLat),max(oriLat),N) ;

%

[Lon,Lat] = meshgrid(lon,lat) ;

% pick points lying inside the given region

idx = inpolygon(Lon(:), Lat(:),oriLon, oriLat) ;

Lon(~idx) = NaN ; Lat(~idx) = NaN ;

plot( oriLon, oriLat, 'b')

hold on

plot(Lon,Lat,'.r')

The above gives me multiple uniform grids fitting within a polygon. From above I would like to reduce number of recangulars by replacing them with larger grids/ boxes. Each box could have different size. Usually near the edge, the size would be smaller.

What would be the approach to go about this?

##### 6 Comments

Steven Lord
on 19 Oct 2023

What's your ultimate goal in creating these boxes? What are you hoping to use these boxes to do?

Do you require these boxes to stay strictly within the boundaries of the shape or is some coverage of the area outside the shape acceptable?

Are the boxes required to be rectangles? Are general quadrilaterals allowed? Are polygons with other number of sides allowed (triangulate the area, tile it with hexagons, cover it with N-sided polygons for large N that approximate circles, etc.)? Are arbitrarily shaped regions allowed (jigsaw puzzle pieces or electoral district drawing / gerrymandering)?

What's your success criteria? What's most important from the list below?

- maximum amount of coverage / minimize uncovered area
- minimize amount of area outside the shape that is covered (if covering outside the area is allowed)
- minimize number of boxes
- maximize box size

Walter Roberson
on 19 Oct 2023

### Accepted Answer

Fabio Freschi
on 20 Oct 2023

Edited: Fabio Freschi
on 20 Oct 2023

The following attempt is far from being a perfect answer to your question. All perplexities of @Walter Roberson are also mine, so I have drastically simplified the problem assuming

- the use of square boxes instead of rectangular ones
- the possibility of randomly starting the creation of new boxes
- the number of boxes is not minimum

If you are optimistic and benevolent, the solution found can be said to be "sub-optimal", but I think it's a starting point you can use to find a better solution.

clear variables, close all

% perimeter

oriLat = [48.3860120000000;49.3686790000000;48.0145280000000;46.6825390000000;47.4787370000000;46.5073030000000;46.5176190000000;44.9243550000000;45.2906840000000;42.3015220000000;41.9182910000000;44.6990460000000;45.7893010000000;45.2741950000000;43.7351650000000;43.8312240000000;41.7326470000000;41.3863160000000;44.9774490000000;45.2345130000000;47.3537330000000;44.8174190000000;43.3218860000000;41.5511100000000;39.4791860000000;37.8949860000000;37.1004480000000;39.4531150000000;38.0365030000000;38.6352170000000;35.2258250000000;31.1253830000000;26.7715300000000;24.8661310000000;29.9185130000000;30.6849560000000;30.0184100000000;28.9338120000000;29.4307800000000;27.9083070000000;25.8403780000000;29.7380790000000;28.9821380000000;31.7520090000000;31.3322390000000;34.5540170000000;40.2609740000000;46.2591090000000;48.3860120000000];

oriLon = [-124.725839000000;-94.9521110000000;-89.4892260000000;-91.9618890000000;-87.9292690000000;-87.3667670000000;-84.1179250000000;-87.8434330000000;-86.9777800000000;-87.8347690000000;-86.5978990000000;-86.2484740000000;-84.7727650000000;-83.3851040000000;-83.9477400000000;-82.6336410000000;-83.4538320000000;-82.4605990000000;-74.9927560000000;-70.8444300000000;-68.2697100000000;-66.9498950000000;-70.5538540000000;-69.9649820000000;-75.5930680000000;-75.3386230000000;-75.9796080000000;-76.0123120000000;-76.3220930000000;-77.2467040000000;-75.5336270000000;-81.4020960000000;-80.0321200000000;-80.6511890000000;-83.6792190000000;-88.0083960000000;-89.8450650000000;-89.4009660000000;-94.6703890000000;-97.0033250000000;-97.4226360000000;-101.400636000000;-103.281190000000;-106.417940000000;-111.074825000000;-120.622575000000;-124.363414000000;-123.547659000000;-124.725839000000];

% discretization size

N1 = 80;

N2 = 60;

x = linspace(min(oriLon),max(oriLon),N1) ;

y = linspace(min(oriLat),max(oriLat),N2) ;

% create meshgrid

[x,y] = meshgrid(x,y) ;

% pick points lying inside the given region

idx = inpolygon(x(:),y(:),oriLon, oriLat);

% reshape idx

idx = reshape(idx,size(x));

% coloring matrix (-1: out, 0: in & never touched, >0 in & touched)

col = zeros(size(idx));

col(~idx) = -NaN;

% plot

h = figure; hold on

plot(oriLon, oriLat, 'b')

% rng(2);

for icol = 1:N1*N2

% select a random point to start

idx0 = find(col(:) == 0);

if isempty(idx0)

break

end

[i0,j0] = ind2sub(size(col),idx0(randi(length(idx0))));

% move north-est

chk = true;

k_ne = 0;

while chk

k_ne = k_ne+1;

if any(any(col(i0:i0+k_ne,j0:j0+k_ne) ~= 0))

k_ne = k_ne-1;

% col(i0:i0+k_ne,j0:j0+k_ne) = icol;

chk = false;

end

end

% move south-west

chk = true;

k_sw = 0;

while chk

k_sw = k_sw+1;

if any(any(col(i0-k_sw:i0+k_ne,j0-k_sw:j0+k_ne) ~= 0))

k_sw = k_sw-1;

col(i0-k_sw:i0+k_ne,j0-k_sw:j0+k_ne) = icol;

chk = false;

end

end

% plot colored points

scatter(reshape(x(i0-k_sw:i0+k_ne,j0-k_sw:j0+k_ne),[],1),...

reshape(y(i0-k_sw:i0+k_ne,j0-k_sw:j0+k_ne),[],1),...

15,reshape(col(i0-k_sw:i0+k_ne,j0-k_sw:j0+k_ne),[],1),'filled');

if k_ne+k_sw > 1

xl = [x(i0-k_sw,j0-k_sw)

x(i0+k_ne,j0-k_sw)

x(i0+k_ne,j0+k_ne)

x(i0-k_sw,j0+k_ne)

x(i0-k_sw,j0-k_sw)];

yl = [y(i0-k_sw,j0-k_sw)

y(i0+k_ne,j0-k_sw)

y(i0+k_ne,j0+k_ne)

y(i0-k_sw,j0+k_ne)

y(i0-k_sw,j0-k_sw)];

plot(xl,yl,'-','LineWidth',2);

end

end

fprintf('final number of boxes: %d\n',icol)

Hope it helps

##### 3 Comments

Fabio Freschi
on 20 Oct 2023

Edited: Fabio Freschi
on 20 Oct 2023

I added the possibility of creation rectangles from squares, as suggested in my provious comment, with some cleanup and small improvements: the number of rectangles is now reduced to 25%-30% with respect to the previous method.

clear variables, close all

% perimeter

oriLat = [48.3860120000000;49.3686790000000;48.0145280000000;46.6825390000000;47.4787370000000;46.5073030000000;46.5176190000000;44.9243550000000;45.2906840000000;42.3015220000000;41.9182910000000;44.6990460000000;45.7893010000000;45.2741950000000;43.7351650000000;43.8312240000000;41.7326470000000;41.3863160000000;44.9774490000000;45.2345130000000;47.3537330000000;44.8174190000000;43.3218860000000;41.5511100000000;39.4791860000000;37.8949860000000;37.1004480000000;39.4531150000000;38.0365030000000;38.6352170000000;35.2258250000000;31.1253830000000;26.7715300000000;24.8661310000000;29.9185130000000;30.6849560000000;30.0184100000000;28.9338120000000;29.4307800000000;27.9083070000000;25.8403780000000;29.7380790000000;28.9821380000000;31.7520090000000;31.3322390000000;34.5540170000000;40.2609740000000;46.2591090000000;48.3860120000000];

oriLon = [-124.725839000000;-94.9521110000000;-89.4892260000000;-91.9618890000000;-87.9292690000000;-87.3667670000000;-84.1179250000000;-87.8434330000000;-86.9777800000000;-87.8347690000000;-86.5978990000000;-86.2484740000000;-84.7727650000000;-83.3851040000000;-83.9477400000000;-82.6336410000000;-83.4538320000000;-82.4605990000000;-74.9927560000000;-70.8444300000000;-68.2697100000000;-66.9498950000000;-70.5538540000000;-69.9649820000000;-75.5930680000000;-75.3386230000000;-75.9796080000000;-76.0123120000000;-76.3220930000000;-77.2467040000000;-75.5336270000000;-81.4020960000000;-80.0321200000000;-80.6511890000000;-83.6792190000000;-88.0083960000000;-89.8450650000000;-89.4009660000000;-94.6703890000000;-97.0033250000000;-97.4226360000000;-101.400636000000;-103.281190000000;-106.417940000000;-111.074825000000;-120.622575000000;-124.363414000000;-123.547659000000;-124.725839000000];

% discretization size

N1 = 80;

N2 = 60;

x = linspace(min(oriLon),max(oriLon),N1) ;

y = linspace(min(oriLat),max(oriLat),N2) ;

% create meshgrid

[x,y] = meshgrid(x,y) ;

% pick points lying inside the given region

idx = inpolygon(x(:),y(:),oriLon, oriLat);

% reshape idx

idx = reshape(idx,size(x));

% coloring matrix (-1: out, 0: in & never touched, >0 in & touched)

col = zeros(size(idx));

col(~idx) = -NaN;

% plot

h = figure; hold on

plot(oriLon, oriLat, 'b')

rng(2);

for icol = 1:N1*N2

% select a random point to start

idx0 = find(col(:) == 0);

if isempty(idx0)

break

end

[i0,j0] = ind2sub(size(col),idx0(randi(length(idx0))));

% initial values

k_n = 0;

k_e = 0;

k_s = 0;

k_w = 0;

% move north-est

chk = true;

while chk

k_n = k_n+1;

k_e = k_e+1;

if any(col(i0:i0+k_e,j0:j0+k_n) ~= 0,'all')

k_n = k_n-1;

k_e = k_e-1;

chk = false;

end

end

% try only north

chk = true;

while chk

k_n = k_n+1;

if any(col(i0:i0+k_e,j0:j0+k_n) ~= 0,'all')

k_n = k_n-1;

chk = false;

end

end

% try only east

chk = true;

while chk

k_e = k_e+1;

if any(col(i0:i0+k_e,j0:j0+k_n) ~= 0,'all')

k_e = k_e-1;

chk = false;

end

end

% move south-west

chk = true;

while chk

k_s = k_s+1;

k_w = k_w+1;

if any(col(i0-k_w:i0+k_e,j0-k_s:j0+k_n) ~= 0,'all')

k_s = k_s-1;

k_w = k_w-1;

chk = false;

end

end

% try only south

chk = true;

while chk

k_s = k_s+1;

if any(col(i0-k_w:i0+k_e,j0-k_s:j0+k_n) ~= 0,'all')

k_s = k_s-1;

chk = false;

end

end

% try only west

chk = true;

while chk

k_w = k_w+1;

if any(col(i0-k_w:i0+k_e,j0-k_s:j0+k_n) ~= 0,'all')

k_w = k_w-1;

chk = false;

end

end

% set new box id

col(i0-k_w:i0+k_e,j0-k_s:j0+k_n) = icol;

% plot colored points

scatter(reshape(x(i0-k_w:i0+k_e,j0-k_s:j0+k_n),[],1),...

reshape(y(i0-k_w:i0+k_e,j0-k_s:j0+k_n),[],1),...

15,reshape(col(i0-k_w:i0+k_e,j0-k_s:j0+k_n),[],1),'filled');

if k_n+k_s > 0 && k_e+k_w > 0

xl = [x(i0-k_w,j0-k_s)

x(i0+k_e,j0-k_s)

x(i0+k_e,j0+k_n)

x(i0-k_w,j0+k_n)

x(i0-k_w,j0-k_s)];

yl = [y(i0-k_w,j0-k_s)

y(i0+k_e,j0-k_s)

y(i0+k_e,j0+k_n)

y(i0-k_w,j0+k_n)

y(i0-k_w,j0-k_s)];

plot(xl,yl,'-','LineWidth',2);

end

end

fprintf('final number of boxes: %d\n',icol)

### More Answers (0)

### See Also

### Categories

### Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!