vendredi 20 mars 2015

How to draw rectangles for 2D arrays


I have an 2D boolean array that looks like this:



[0][0][0][0][0][0][0][0][0][0]
[0][0][0][0][0][0][0][0][0][0]
[0][0][0][0][0][0][0][0][0][0]
[0][0][0][1][1][1][0][0][0][0]
[0][0][0][1][1][1][0][0][0][0]
[0][0][0][1][1][1][0][0][0][0]
[0][0][0][1][1][1][0][0][0][0]
[0][0][0][1][1][1][0][0][0][0]
[0][0][0][0][0][0][0][0][0][0]
[0][0][0][0][0][0][0][0][0][0]


(0 = false, 1 = true)


I've found a way to combine neighbouring zeros on the horizontal plane like like:



[----------------------------]
[----------------------------]
[----------------------------]
[-------][1][1][1][----------]
[-------][1][1][1][----------]
[-------][1][1][1][----------]
[-------][1][1][1][----------]
[-------][1][1][1][----------]
[----------------------------]
[----------------------------]


The code for achieving this is as such:



for y = 0 to ySize
for x = 0 to xSize
if array[x][y] = 0
set width = 1

for x2 = x + 1 to xSize
if array[x][y] = 0
width++
else
break

add object at x, y and set width to width
set x = x + width - 1


So it loops the 2D array looking for zeros, and if it finds one, it loops until the end of the row to find where it is no longer a zero.


It then creates an object at the position where it first found a zero, and stretches it to fill the part until it is not a zero.


I want to adapt this code in order to make rectangles instead of long planks, like:



____________________________
| |
| | <------ rect at 0, 0 with size (10, 3)
|____________________________|
| |[1][1][1]| |
| |[1][1][1]| |
| |[1][1][1]| | <------ rect at 6, 3 with size (4, 5)
| |[1][1][1]| |
| |[1][1][1]|__________|
| | |
|_______|____________________| <------ rect at 3, 8 with size (7, 2)

^
|
|
rect at 0, 3 with size (3, 7)


So instead of making 15 horizontal planks, it makes 4 rectangles that surround the ones.


In short, I want to create an algorithm that will, when given an 2D array of ones and zeros, create rectangles around the ones.


For a smaller example:



{
[0][0][0] { 0, 0, 0 },
[0][1][0] { 0, 1, 0 },
[0][0][0] { 0, 0, 0 }
}


Will return the position and dimension of rectangles such as:



[-------]
[-][1][-]
[-------]

{
{0, 0, 3, 1}, //rect at (0, 0) with width 3, height 1
{0, 1, 1, 1}, //rect at (0, 1) with width 1, height 1
{2, 1, 1, 1}, //rect at (2, 1) with width 1, height 1
{0, 2, 3, 1} //rect at (0, 2) with width 3, height 1
}


What should this algorithm look like?





Aucun commentaire:

Enregistrer un commentaire