[Beginning Database Design Solutions, Second Edition]

Title: Flow blocks around obstacles for document layout in C#

The following two document layout examples draw "illuminated" text by using an initial or drop cap.

Martin asked how we could do something similar when the text that follows the initial is drawn with different fonts. This is the first part of a three-part document layout example that does just that. This first post shows how you can perform layout for boxes, the second post will use these techniques to solve Martin's problem, and the third will refine the technique to work more easily with drop caps.

This is a fairly long example, so I'll describe it in pieces. Fortunately each of the methods is reasonably understandable if you focus only on its specific task and you don't think about how the other pieces work until you get to them.

The Idea

Suppose we need to arrange some boxes inside a drawing area. The area contains some rectangular obstacles where we are not allowed to place our boxes.

The basic idea is to start in the upper left corner and arrange boxes in a row left to right. If we come to an obstacle, we skip over it. As we add boxes to the current row, we arrange the boxes so they all share a common baseline, which is somewhere within the boxes.

See the picture at the top of this post to see the idea. Note that all of the green boxes on the top row are aligned on their red baselines.

The first row skips past the first pink obstacle in the upper left corner. Block 0 is relatively large, so it is the only one that fits before the second obstacle interrupts the row. Blocks 1 through 4 fit on the first row, and then the document layout moves to a new row.

Only block 5, which is relatively small, fits on the second row before another obstacle gets in the way. The program places block 6, skips another obstacle, and then positions blocks 7 and 8 before starting the third row.

You can look at the remaining boxes and obstacles to get an idea about how the method works. You can probably devise other document layout methods, but this one seems to produce a reasonable result.

Also note that this would be a truly bizarre document layout for drop caps. Normally all of the drop caps would be at the left edge and the remaining text would flow to the right. This method handles that normal arrangement. It can also deal with one or two pictures scattered across the page.

The program uses the RectangleF structure to represent obstacles. It uses a Block class to represent the blocks that it should flow. The following section describes that class.

The following sections explain how the program arranges its blocks.

Obstacles and Blocks

The program uses the following Block class to represent the blocks that it should flow around obstacles.

public class Block { public RectangleF Bounds; public float TopHeight; public float BottomHeight { get { return Bounds.Height - TopHeight; } } public Block(RectangleF bounds, float top_height) { Bounds = bounds; TopHeight = top_height; } // Draw the block. public void Draw(Graphics gr, int index, Font font) { if (Bounds.X < 0) return; gr.FillRectangle(Brushes.LightGreen, Bounds); gr.DrawRectangle(Pens.Green, Bounds); float x1 = Bounds.Left; float x2 = Bounds.Right; float y = Bounds.Top + TopHeight; gr.DrawLine(Pens.Red, x1, y, x2, y); gr.DrawString(index.ToString(), font, Brushes.Black, Bounds); } }

This class defines two fields: Bounds and TopHeight. The Bounds value gives the block's size and location. Initially only the size matters. [Insert your joke here.] After the block has been positioned, Bounds indicates where it should be drawn.

The TopHeight value is the distance from the block's top to its baseline. The read-only BottomHeight property gives the distance from the block's baseline to its bottom. That value is simply the block's height minus its TopHeight value.

The class defines one simple initializing constructor.

The last part of the class defines a Draw method that draws the block on a Graphics object. That method fills the block's area with light green, outlines it in green, draws a red line at the block's baseline, and then draws the block's index number inside the block's area. (Look at the picture at the top of the post to see the result.)

The next section provides an overview of the methods that arrange the blocks. The sections after that describe each of those methods in greater detail.

Code Overview

The program uses the following methods to arrange blocks.

FlowBlocks: This is the high-level method that coordinates the document layout. It enters a loop that executes as long as any blocks are not positioned. Inside the loop, it calls PositionOneRow to position blocks on the next row. If no blocks fit on that row, it calls MoveDown to move down where a row might be drawn so it can hopefully position some blocks.
PositionOneRow: This method tries to position blocks in a row within a bounding area starting with a given Y coordinate. To do that, it tries to position one block, then two blocks, then three blocks, and so on until it finds a number of blocks that will not fit. For example, if it can position four blocks but not five blocks, then the method returns 4 and positions four blocks. To determine whether a given set of blocks fits on the row, the method calls BlocksFit.
BlocksFit: This method attempts to flow a given set of blocks around obstacles in a row with the given Y coordinate. If the blocks fit, the method leaves them positioned and returns true.
MoveDown: This method moves a Y coordinate downward to try to find a position for a new row. It is only called if the BlocksFit method was unable to fit even a single block on the next row. To make at least one block fit, the method moves the Y coordinate down so the next block will not overlap vertically with at least one obstacle. Note that the block may still overlap with other obstacles. In that case, the program will call MoveDown again until the block will fit or the document layout runs out of space.

The following sections show the methods' code and describe them in greater detail. You may want to refer back to the overview as you read through the code.

FlowBlocks

The following code shows the top-level FlowBlocks method.

// Flow blocks around obstacles. private void FlowBlocks(RectangleF bounds, List<RectangleF> obstacles, List<Block> blocks) { float y = bounds.Y; // Repeat until we place all blocks or run out of room. int first_block = 0; while (first_block < blocks.Count) { // Position a row of blocks. int num_positioned = PositionOneRow( bounds, obstacles, blocks, ref first_block, ref y); // See if any fit. if (num_positioned == 0) { // None fit. Move down. MoveDown(bounds, obstacles, blocks[first_block], ref y); } // See if we have run out of room. if (y > bounds.Bottom) { // Position the remaining blocks at (-1, -1). for (int i = first_block; i < blocks.Count; i++) { blocks[i].Bounds.X = -1; blocks[i].Bounds.Y = -1; } break; } } }

This method first sets variable y equal to the Y coordinate of the top of the drawing area. It uses variable first_block to keep track of the first block that has not yet been positioned. It sets that value to 0 and then enters a loop that continues until all of the blocks have been positioned.

Inside the loop, the method calls PositionOneRow to position blocks at the current Y coordinate. If no blocks will fit at that position, the method calls MoveDown to move the Y coordinate down so hopefully some blocks will fit.

After positioning some blocks or moving down, the method checks y to see if it has dropped off of the bottom of the document layout area. If we have run out of space, the method places the remaining unpositioned blocks at (-1, -1) and exits.

PositionOneRow

The following code shows the PositionOneRow method.

// Return the maximum number of blocks that will fit // on one row starting at the indicated Y coordinate. // If we position any blocks, update first_block and y. private int PositionOneRow(RectangleF bounds, List<RectangleF> obstacles, List<Block> blocks, ref int first_block, ref float y) { // Loop through the blocks. int last_that_fits = blocks.Count - 1; for (int i = first_block; i < blocks.Count; i++) { // See if we can place blocks[first_block] // through blocks[i]. if (!BlocksFit(bounds, obstacles, blocks, first_block, i, y)) { last_that_fits = i - 1; break; } } // If no blocks fit, return 0. if (last_that_fits < first_block) return 0; // Position the blocks that fit again. BlocksFit(bounds, obstacles, blocks, first_block, last_that_fits, y); // Find the maximum y coordinate for these blocks. for (int i = first_block; i <= last_that_fits; i++) { if (y < blocks[i].Bounds.Bottom) y = blocks[i].Bounds.Bottom; } // Update first_block. int num_blocks_positioned = last_that_fits - first_block + 1; first_block = last_that_fits + 1; // Return the number of blocks that fit. return num_blocks_positioned; }

The parameter first_block gives the index of the first block that has not yet been positioned. This method enters a loop where i runs from first_block to the last block in the list. Inside the loop, it calls the BlocksFit method to see if the blocks with indices first_block through i will fit on the current row.

After it finds a set of blocks that will not fit on the current row, the method backtracks to the previous set. If that set is empty (no blocks will fit on the row), the method returns 0.

If some blocks fit on the row, the method calls BlocksFit again for the set that fit to reposition them. The code then loops through the positioned blocks and finds their maximum Y coordinate. It updates y so the next row is positioned below this one.

Finally, the method updates first_block and returns the number off blocks that it positioned.

BlocksFit

The following code shows the BlocksFit method.

// Return true if the indicated blocks will // fit starting at the given Y coordinate. private bool BlocksFit(RectangleF bounds, List<RectangleF> obstacles, List<Block> blocks, int first_block, int last_block, float y) { // Find the maximum top height. float top_height = 0; for (int i = first_block; i <= last_block; i++) { if (top_height < blocks[i].TopHeight) top_height = blocks[i].TopHeight; } // Set the baseline. float baseline = y + top_height; // Position the blocks. float x = bounds.X; for (int i = first_block; i <= last_block; i++) { Block block = blocks[i]; block.Bounds.X = x; x += block.Bounds.Width; if (x > bounds.Right) return false; block.Bounds.Y = baseline - block.TopHeight; // See if the block intersects with an obstacle. RectangleF rect = block.Bounds; bool had_hit = true; while (had_hit) { had_hit = false; foreach (RectangleF obstacle in Obstacles) { if (obstacle.IntersectsWith(rect)) { had_hit = true; // Move the block to the right. rect.X = obstacle.Right; // See if we are out of bounds. if (rect.Right > bounds.Right) return false; } } } // Update the block's bounds. block.Bounds = rect; x = rect.Right; // Loop to position the next block. } // If we get this far, then we have // positioned all of the blocks. return true; }

This method first uses a loop to find the maximum top height of the blocks in question. It then positions the row's baseline at that distance from the row's upper Y coordinate.

The code then loops through the blocks and tries to position each block at the next available X coordinate. The code then loops through the obstacles to see if any intersect with the block at that position. If an obstacle intersects the block, the method moves the block to the right of that obstacle. It also restarts the loop that examines the obstacles in case one of the previous obstacles now intersects the moved block.

The inner loop ends when one of two things occurs. First, if block extends beyond the right edge of the document layout area, then the blocks will not fit on this row so the method returns false.

Second, if the block does not intersect any obstacle, then it is in a safe position. In that case, the method continues its outer loop to position the other blocks in the row.

If the method successfully positions all of the blocks, it returns true.

MoveDown

The following code shows the MoveDown method.

// Move down so the block will clear at least one new obstacle. private void MoveDown(RectangleF bounds, List<RectangleF> obstacles, Block block, ref float y) { float min_y = y + block.Bounds.Height; RectangleF rect = new RectangleF( bounds.X, y, bounds.Width, block.Bounds.Height); foreach (RectangleF obstacle in obstacles) { if (obstacle.IntersectsWith(rect)) { if (min_y > obstacle.Bottom) min_y = obstacle.Bottom; } } y = min_y; }

This method creates a rectangle as tall as the next block to position and as wide as the document layout area. It then loops through the obstacles to find the smallest Y coordinate of the bottom of any obstacle that intersects with the rectangle. The code updates the reference parameter y to move past that Y value and returns.

This moves the next row past the highest obstacle that intersects the rectangle. The higher-level methods then try to position the row again. If those methods fail again, they may call MoveDown again.

Main Program

That's all of the document layout code. The following code shows how the program generates some random obstacles and blocks.

// Obstacles. private List<RectangleF> Obstacles; // Blocks to flow around obstacles. private List<Block> Blocks; // Define some blocks. private void Form1_Load(object sender, EventArgs e) { Obstacles = new List<RectangleF>(); Obstacles.Add(new RectangleF(0, 0, 64, 64)); Obstacles.Add(new RectangleF(200, 50, 50, 100)); Obstacles.Add(new RectangleF(50, 150, 100, 70)); Obstacles.Add(new RectangleF(300, 200, 100, 64)); // Random rand = new Random(4); Random rand = new Random(4); Blocks = new List<Block>(); for (int i = 0; i < 25; i++) { float width = rand.Next(10, 100); float height = rand.Next(10, 100); Blocks.Add(new Block( new RectangleF(0, 0, width, height), height * 0.6f)); } }

At the form level, the code defines lists to hold obstacles and blocks. The form's Load event handler creates some specific obstacles and then uses a Random object to generate blocks with random sizes. It sets each block's TopHeight value to 0.6 times its height.

The program arranges the blocks in the following Paint event handler.

// Flow and draw the blocks. private void picWriting_Paint(object sender, PaintEventArgs e) { e.Graphics.SmoothingMode = SmoothingMode.AntiAlias; // Flow. FlowBlocks(picWriting.ClientRectangle, Obstacles, Blocks); // Draw obstacles. foreach (RectangleF obstacle in Obstacles) { e.Graphics.FillRectangle(Brushes.Pink, obstacle); e.Graphics.DrawRectangle(Pens.Red, obstacle); } // Draw flowed blocks. for (int i = 0; i < Blocks.Count; i++) { Blocks[i].Draw(e.Graphics, i, picWriting.Font); } }

This code calls the FlowBlocks method to position the blocks. It then loops through the obstacles and draws them as pink rectangles.

Next, the code creates a dashed pen and a StringFormat object to center text. It then loops through the blocks. It draws each block in green, draws its baseline with the dashed pen, and draws the block's index inside it.

Conclusion

This method is rather long, but it seems to produce a reasonable result. The picture shown at the top of the post includes some fairly large blank areas. For example, there's a pretty big break after block 0 and below block 0. Those should be smaller with a more realistic arrangement where drop caps are on the left and a relatively large amount of text flows to the right. After you see the next two posts, you can decide whether you want to modify the document layout algorithm.

Meanwhile, download the example and experiment with it. In my next post, I'll show how you can modify the block flow method to flow text with various fonts around obstacles.

Download the example to experiment with it and to see additional details.