# Rotating Rectangle Problem

• (2 Pages)
• 1
• 2

## 26 Replies - 6445 Views - Last Post: 18 July 2012 - 02:19 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=285663&amp;s=73d0d0e4e2ed7673090d240a43ff0b73&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 hexie

Reputation: 0
• Posts: 16
• Joined: 12-July 12

# Rotating Rectangle Problem

Posted 12 July 2012 - 11:49 PM

Hi Guys

I have been asked to solve an issue - same as the one posted here;
http://www.devx.com/...t/Article/36005[^]

I have managed to get the rectangles up and displaying, the problem i am having is when i try to get them all on one touching and NOT overlapping -
if i manually add 3 RANDOM rectangles i can get 2 of them to look perfect, the last will appear in random and overlapping.

If i manually set the properties of the rectangles, i can accomplish what i am wanting - hence, the confusion;

The below code works;

```rectangles = new List<rectangle>();
Rectangle rect4 = new Rectangle(10, 160, 100, 100);
Rectangle rect5 = new Rectangle(rect4.X + rect4.Width, 160, 120, 120);
Rectangle rect6 = new Rectangle(rect5.X + rect5.Width, 160, 100, 140);
Rectangle rect7 = new Rectangle(rect6.X + rect6.Width, 160, 100, 80);

graphics.DrawRectangles(pen1,rectangles.ToArray());

```

Yet the following loop doesn't;

```Rectangle foo = GetRandomRectangle(rng);
Rectangle bar = GetRandomRectangle(rng);
Rectangle car = GetRandomRectangle(rng);
List<rectangle> rectangles = new List<rectangle>();

foreach (Rectangle rect in rectangles)
{
if (rect.Height > TallestRectangle) { TallestRectangle = rect.Height; }
}
foreach (Rectangle rect in rectangles)
{
if (PreviousRectangleX + PreviousRectangleWidth == 0)
{
graphics.DrawRectangle(pen1, new Rectangle(rect.X, (TallestRectangle - rect.Height), rect.Width, rect.Height));
}
else
{
graphics.DrawRectangle(pen1, new Rectangle((PreviousRectangleX + PreviousRectangleWidth), (TallestRectangle - rect.Height), rect.Width, rect.Height));
}
PreviousRectangleX = rect.X;
PreviousRectangleWidth = rect.Width;
}

```

Function GetRandomRectagle;

```private Rectangle GetRandomRectangle(Random rnd)
{
int x = rnd.Next(4, 110);
int y = rnd.Next(4, 110);
int width = rnd.Next(4, 110);
int height = rnd.Next(4, 110);
Rectangle rec = new Rectangle(x, y, width, height);
return rec
};

```

Any help would be greatly appreciated?

Regards

Is This A Good Question/Topic? 0

## Replies To: Rotating Rectangle Problem

### #2 hexie

Reputation: 0
• Posts: 16
• Joined: 12-July 12

## Re: Rotating Rectangle Problem

Posted 13 July 2012 - 12:58 AM

Sorry guys, the URL mentioned above is incorrect (I'm not sure how to edit the post).
The correct URL is;
http://social.msdn.m...e7-c8d1861657e0

### #3 Skydiver

• Code herder

Reputation: 6063
• Posts: 20,877
• Joined: 05-May 12

## Re: Rotating Rectangle Problem

Posted 13 July 2012 - 06:29 AM

You really need to fix your indent style to be consistent. It makes your code hard to read otherwise.

### #4 hexie

Reputation: 0
• Posts: 16
• Joined: 12-July 12

## Re: Rotating Rectangle Problem

Posted 13 July 2012 - 06:32 AM

Update:
I have managed to get the rectangles to draw as wanted, i am now in the process of implementing a loop for them all, will keep you posted.
Thanks.

Skydiver, on 13 July 2012 - 06:29 AM, said:

You really need to fix your indent style to be consistent. It makes your code hard to read otherwise.

Apologies; It was my first post and i wasn't too sure how it was going to come out on screen, hence i adjusted the indentation.

### #5 hexie

Reputation: 0
• Posts: 16
• Joined: 12-July 12

## Re: Rotating Rectangle Problem

Posted 16 July 2012 - 06:51 AM

Hi Guys

Keeping with this post, i was thinking of the best way to achieve this;
"Generate the requested amount of rectangles and write them to file (in a human readable)."

I have done this using a bitmap with the graphics object (i.e. i save the image of the rectangles) and was wondering if there might be a better way (i.e. save everything to XML or something?)

Thanks

### #6 Skydiver

• Code herder

Reputation: 6063
• Posts: 20,877
• Joined: 05-May 12

## Re: Rotating Rectangle Problem

Posted 16 July 2012 - 08:51 AM

On the second link you sent, it says:

"Write the output rectangle coordinates into an output file (human readable)"

http://social.msdn.m...e7-c8d1861657e0

As much as people claim that XML is "human readable", I tend to qualify it as "human readable if you really make me read it."

I would rather read a text file that says:
```The rectangles positions and sizes are:
Location    Size
1:   0,  0     45, 23
2:  45,  0     67, 36

```

than

```<?xml version="1.0" encoding="UTF-8" ?>
<rectangles>
<rectangle id="1" Position="0,0" Size="45, 23" />
<rectangle id="2" Position="45,0" Size="67, 36" />
</rectangles>

```

Now, on the other hand, if the file were both meant to human and machine readable, then I would prefer the XML.

This post has been edited by Skydiver: 16 July 2012 - 08:52 AM

### #7 hexie

Reputation: 0
• Posts: 16
• Joined: 12-July 12

## Re: Rotating Rectangle Problem

Posted 16 July 2012 - 09:03 AM

Skydiver, on 16 July 2012 - 08:51 AM, said:

On the second link you sent, it says:

"Write the output rectangle coordinates into an output file (human readable)"

http://social.msdn.m...e7-c8d1861657e0

As much as people claim that XML is "human readable", I tend to qualify it as "human readable if you really make me read it."

I would rather read a text file that says:
```The rectangles positions and sizes are:
Location    Size
1:   0,  0     45, 23
2:  45,  0     67, 36

```

than

```<?xml version="1.0" encoding="UTF-8" ?>
<rectangles>
<rectangle id="1" Position="0,0" Size="45, 23" />
<rectangle id="2" Position="45,0" Size="67, 36" />
</rectangles>

```

Now, on the other hand, if the file were both meant to human and machine readable, then I would prefer the XML.

Hi Skydiver,

Thanks for that - point taken (i think i will adjust the code and make it a text file).
The only problem that i then have is, taking it from a text file back to an image (i.e. i can save the co-ordinates within a text file but then i am also required to use that same text file to draw the image back).

At the moment (as mentioned), i am saving the image to a jpg - i then load that saved jpg into a picture box for when the image needs to be re-drawn.

That's currently how i am doing it - but would also prefer a .txt file.

I hope that makes sense?

Thanks again for the help so far.

### #8 Skydiver

• Code herder

Reputation: 6063
• Posts: 20,877
• Joined: 05-May 12

## Re: Rotating Rectangle Problem

Posted 16 July 2012 - 10:41 AM

You must be operating on a completely different set of specs...

Nothing on the second link you sent ( http://social.msdn.m...e7-c8d1861657e0 ) says that you have to take the text file and use that to draw the image back. All it says are:

Quote

Create an application that will:

Allow the user to specify the number of input rectangles (between 3 and 30).

Generate the requested number of input rectangles (with random widths and heights) and write them to a file (human readable)

Read the randomly generated input rectangles from the file generated in the step above.

Display the input rectangles graphically, correctly laid out, as in the example.

Calculate the output rectangles.

Display the output rectangles graphically, correctly laid out as in the example above. Note: Both the input and

output rectangles must be displayed at the same time.

Write the output rectangle coordinates into an output file (human readable)

Since the only requirement was "display", I wouldn't even have bothered with generating .jpg files. I would create a custom control that just takes a list of Rectangles, and renders them (probably with different random colors) using Graphics.DrawRectangle(). On my screen I would have two of these custom controls. The Before custom control instance takes a list of the original randomly generated rectangles, and the After custom control instance takes a list of the computed rectangles. The code that generates the text file, just prints out a little introduction text, and then does a foreach() loop on the list of computed rectangles printing out position and location.

(I'm sorry if I'm coming across as too literal today. I spent most of the weekend playing rules lawyer and got very good at parsing what the rules "required" vs. what people thought was "intended".)

This post has been edited by Skydiver: 16 July 2012 - 11:36 AM

### #9 hexie

Reputation: 0
• Posts: 16
• Joined: 12-July 12

## Re: Rotating Rectangle Problem

Posted 16 July 2012 - 11:15 PM

Skydiver, on 16 July 2012 - 10:41 AM, said:

You must be operating on a completely different set of specs...

Nothing on the second link you sent ( http://social.msdn.m...e7-c8d1861657e0 ) says that you have to take the text file and use that to draw the image back. All it says are:

Quote

Create an application that will:

Allow the user to specify the number of input rectangles (between 3 and 30).

Generate the requested number of input rectangles (with random widths and heights) and write them to a file (human readable)

Read the randomly generated input rectangles from the file generated in the step above.

Display the input rectangles graphically, correctly laid out, as in the example.

Calculate the output rectangles.

Display the output rectangles graphically, correctly laid out as in the example above. Note: Both the input and

output rectangles must be displayed at the same time.

Write the output rectangle coordinates into an output file (human readable)

Since the only requirement was "display", I wouldn't even have bothered with generating .jpg files. I would create a custom control that just takes a list of Rectangles, and renders them (probably with different random colors) using Graphics.DrawRectangle(). On my screen I would have two of these custom controls. The Before custom control instance takes a list of the original randomly generated rectangles, and the After custom control instance takes a list of the computed rectangles. The code that generates the text file, just prints out a little introduction text, and then does a foreach() loop on the list of computed rectangles printing out position and location.

(I'm sorry if I'm coming across as too literal today. I spent most of the weekend playing rules lawyer and got very good at parsing what the rules "required" vs. what people thought was "intended".)

Hi Skydiver

Thanks for all that - it did make sense and i will keep it handy.

As for the spec, the one in the URL above is incomplete (the user never pasted the entire thing), the other points that follow are;
. Read the randomly generated input rectangles from the file generated in the step above (this is point 3 - following on from the point 2 in the URL)- (done, using .txt file)
. Display the input rectangles graphically, correctly laid out as in the example 1. (done)
. Calculate the output rectangles (this one i am struggling with)
. Display the output rectangles graphically, correctly laid out as in the above example 2. Note - both the input and output rectangles must be displayed at the same time. (this one i am struggling with)
. Write the output rectangle coordinates into an output file that is human read-able (done, using a .txt file)

As mentioned in the above steps there are still 2 that i am struggling with and will try bash them out today - any input you have on them would be great?

Also - when you say "I would create a custom control that just takes a list of Rectangles", do you mean creating a control and then giving it an override method that takes in a list?

Thanks

### #10 Skydiver

• Code herder

Reputation: 6063
• Posts: 20,877
• Joined: 05-May 12

## Re: Rotating Rectangle Problem

Posted 16 July 2012 - 11:51 PM

Custom Controls as described here: http://msdn.microsof...6(v=vs.71).aspx

I managed to create my CirclePainter custom control:
Right click on Project.
Windows Forms on the left side, Custom Control on the right side, and I gave the class the name CirclePainter.
I then went to View Code and added my code.

Here's my really basic code:
```        class Circle
{
public Point Center;
}

List<Circle> Circles = new List<Circle>();

{
}

protected override void OnPaint(PaintEventArgs pe)
{
base.OnPaint(pe);

Graphics g = pe.Graphics;
Pen pen = new Pen(Color.DeepSkyBlue);

foreach (var circle in Circles)
{
int diameter = circle.Radius * 2;
g.DrawEllipse(pen, circle.Center.X, circle.Center.Y, diameter, diameter);
}
}

```

To test things out, I added dragged drop CirclePainter from the Toolbox to Form1, and added the following code to Form1's constructor:
```        public Form1()
{
InitializeComponent();

Random random = new Random();
Size size = circlePainter1.ClientSize;
int maxRadius = Math.Min(size.Width, size.Height) / 2;
for (int i = 0; i < 50; ++i)
{
random.Next(size.Height)),
}
}

```

That should help with the display issue. Just create your own RectanglePainter that lets you add rectangles and their colors. Put two of these controls on your form and you should be good to go.

### #11 hexie

Reputation: 0
• Posts: 16
• Joined: 12-July 12

## Re: Rotating Rectangle Problem

Posted 17 July 2012 - 12:09 AM

Skydiver, on 16 July 2012 - 11:51 PM, said:

Custom Controls as described here: http://msdn.microsof...6(v=vs.71).aspx

I managed to create my CirclePainter custom control:
Right click on Project.
Windows Forms on the left side, Custom Control on the right side, and I gave the class the name CirclePainter.
I then went to View Code and added my code.

Here's my really basic code:
```        class Circle
{
public Point Center;
}

List<Circle> Circles = new List<Circle>();

{
}

protected override void OnPaint(PaintEventArgs pe)
{
base.OnPaint(pe);

Graphics g = pe.Graphics;
Pen pen = new Pen(Color.DeepSkyBlue);

foreach (var circle in Circles)
{
int diameter = circle.Radius * 2;
g.DrawEllipse(pen, circle.Center.X, circle.Center.Y, diameter, diameter);
}
}

```

To test things out, I added dragged drop CirclePainter from the Toolbox to Form1, and added the following code to Form1's constructor:
```        public Form1()
{
InitializeComponent();

Random random = new Random();
Size size = circlePainter1.ClientSize;
int maxRadius = Math.Min(size.Width, size.Height) / 2;
for (int i = 0; i < 50; ++i)
{
random.Next(size.Height)),
}
}

```

That should help with the display issue. Just create your own RectanglePainter that lets you add rectangles and their colors. Put two of these controls on your form and you should be good to go.

Hi Skydiver

I am trying to test your "custom control" and dont seem to understand this comment;
"To test things out, I added dragged drop CirclePainter from the Toolbox to Form1, and added the following code to Form1's constructor:"

I have created a similar control no and would like to test it, just not 100% sure on what component to place onto the custom control?

Thanks

hexie, on 17 July 2012 - 12:06 AM, said:

Skydiver, on 16 July 2012 - 11:51 PM, said:

Custom Controls as described here: http://msdn.microsof...6(v=vs.71).aspx

I managed to create my CirclePainter custom control:
Right click on Project.
Windows Forms on the left side, Custom Control on the right side, and I gave the class the name CirclePainter.
I then went to View Code and added my code.

Here's my really basic code:
```        class Circle
{
public Point Center;
}

List<Circle> Circles = new List<Circle>();

{
}

protected override void OnPaint(PaintEventArgs pe)
{
base.OnPaint(pe);

Graphics g = pe.Graphics;
Pen pen = new Pen(Color.DeepSkyBlue);

foreach (var circle in Circles)
{
int diameter = circle.Radius * 2;
g.DrawEllipse(pen, circle.Center.X, circle.Center.Y, diameter, diameter);
}
}

```

To test things out, I added dragged drop CirclePainter from the Toolbox to Form1, and added the following code to Form1's constructor:
```        public Form1()
{
InitializeComponent();

Random random = new Random();
Size size = circlePainter1.ClientSize;
int maxRadius = Math.Min(size.Width, size.Height) / 2;
for (int i = 0; i < 50; ++i)
{
random.Next(size.Height)),
}
}

```

That should help with the display issue. Just create your own RectanglePainter that lets you add rectangles and their colors. Put two of these controls on your form and you should be good to go.

Hi Skydiver

I am trying to test your "custom control" and dont seem to understand this comment;
"To test things out, I added dragged drop CirclePainter from the Toolbox to Form1, and added the following code to Form1's constructor:"

I have created a similar control no and would like to test it, just not 100% sure on what component to place onto the custom control?

Thanks

Apologies, i have found the control and added it to the form - its just not displaying anything?

Thanks.

### #12 hexie

Reputation: 0
• Posts: 16
• Joined: 12-July 12

## Re: Rotating Rectangle Problem

Posted 17 July 2012 - 12:14 AM

Hi Skydiver

Sorry to mess you around like this - i have managed to resolve the displaying of the circles (i wasnt referencing the custom control i had added to the form - i was initialing a new one.)

Thank you for that - if you have ANY other input for those other questions that i am struggling with, please do share \

Regards

### #13 Skydiver

• Code herder

Reputation: 6063
• Posts: 20,877
• Joined: 05-May 12

## Re: Rotating Rectangle Problem

Posted 17 July 2012 - 12:15 AM

As for computing the minimum covering rectangles, I barely understand how the dynamic programming solution for the knapsack problem works, and that is a one dimensional problem. Or at least the discussion on that link was talking about it being a 2D knapsack problem, so I got scared off.

(Dear reader, if you are mathematically inclined, avert your eyes now, because this will get ugly.)

Well, actually, not fully scared off completely. I would just tackle the problem with techniques that I am familiar with from having taught myself computer graphics as a teenager when I didn't have any access to graphics or algorithm books. In the case of that problem, I would apply a brute force solution using scanlines floodfill.

I would create a white bitmap as wide as the all the rectangles place side side, and as tall as the tallest rectangle.
Next I would just have each rectangle draw itself as black against that white background.
Repeat Here:
Next I would trace horizontal scanlines from from the bottom scanline going up until I have scanline that hit white pixels. This means I found the the biggest base rectangle. Add this rectangle to the list of solution rectangles.
Lop off the bottom part of the bitmap.
Run vertical scanlines from left to right until black is hit.
Lop off everything left of this vertical scan line.
From this vertical scanline, move right until no more black is hit. Lop off everything to the right of the line and push it on a stack.
With the current smaller bitmap, I would go back to Repeat Here and recursively follow the same procedure to get the next rectangle. When no more black rectangles can be found, pop the previously saved portions of bitmaps from the stack and work on those recursively again until the stack is exhausted.

### #14 hexie

Reputation: 0
• Posts: 16
• Joined: 12-July 12

## Re: Rotating Rectangle Problem

Posted 17 July 2012 - 12:23 AM

Skydiver, on 17 July 2012 - 12:15 AM, said:

As for computing the minimum covering rectangles, I barely understand how the dynamic programming solution for the knapsack problem works, and that is a one dimensional problem. Or at least the discussion on that link was talking about it being a 2D knapsack problem, so I got scared off.

(Dear reader, if you are mathematically inclined, avert your eyes now, because this will get ugly.)

Well, actually, not fully scared off completely. I would just tackle the problem with techniques that I am familiar with from having taught myself computer graphics as a teenager when I didn't have any access to graphics or algorithm books. In the case of that problem, I would apply a brute force solution using scanlines floodfill.

I would create a white bitmap as wide as the all the rectangles place side side, and as tall as the tallest rectangle.
Next I would just have each rectangle draw itself as black against that white background.
Repeat Here:
Next I would trace horizontal scanlines from from the bottom scanline going up until I have scanline that hit white pixels. This means I found the the biggest base rectangle. Add this rectangle to the list of solution rectangles.
Lop off the bottom part of the bitmap.
Run vertical scanlines from left to right until black is hit.
Lop off everything left of this vertical scan line.
From this vertical scanline, move right until no more black is hit. Lop off everything to the right of the line and push it on a stack.
With the current smaller bitmap, I would go back to Repeat Here and recursively follow the same procedure to get the next rectangle. When no more black rectangles can be found, pop the previously saved portions of bitmaps from the stack and work on those recursively again until the stack is exhausted.

That is quiet a mouth fill
i don't suppose you have a working code snippet of what you are trying to explain?

Thanks again

### #15 Skydiver

• Code herder

Reputation: 6063
• Posts: 20,877
• Joined: 05-May 12

## Re: Rotating Rectangle Problem

Posted 17 July 2012 - 12:55 AM

See scanline flood fill:

http://en.wikipedia....wiki/Flood_fill

In what I was trying to describe above, I was doing a flood fill of the black area filling it with white. As long as an entire scanline made it full width it was part of a rectangle. Once a scanline got interrupted, that was the end of rectangle and it was time to start over with a smaller problem area to floodfill.

This post has been edited by Skydiver: 17 July 2012 - 12:56 AM