Use VBA to make a Gantt chart showing work schedules


[Gantt chart]

This example shows how to use VBA (Visual Basic for Applications) in an Excel workbook to draw a Gantt chart showing when employees are scheduled to work. This isn’t C# programming, but you may find it useful. (And I don’t have a VBA blog right now where I can post it.)

You could do something similar in C# or another general-purpose programming language, but I decided to use Excel to take advantage off its spreadsheet features.

A Gantt chart uses colored bars to show the duration of tasks. In this example, it uses the bars to show when employees are working. That makes it easy to see when there are few, many, or no people working at the same time.

The example also demonstrates how to calculate elapsed time for employees. The following sections explain how to calculate and display elapsed time, and how to build the Gantt chart.

Calculating Elapsed Time

The entries in column D calculate the difference between columns C and B, but it uses a special rule. If the employee works for more than 5 hours, then we provide a half hour break.

To calculate elapsed time, you can simply subtract the start time from the finish time. Unfortunately the result is stored as a time. To convert it into a number, you multiply it by 24.

To add in the 30 minute break if the shift lasts more than five hours, you can use the Excel IF function.

The following statement shows the equation in cell D5.

=(C5-B5)*24-IF((C5-B5)*24>5,0.5,0)

The first part of this equation, (C5-B5)*24, subtracts the start time B5 from the end time C5 and multiples the result by 24 to convert the result into the number of hours.

Next, the equation uses the IF function. That function returns one of two values depending on whether a Boolean condition is true. In that sense it’s similar to C#’s conditional operator (aka ternary operator) ๐Ÿ˜•. In this example, the Boolean condition is (C5-B5)*24>5. This calculates the elapsed time again and checks whether it is greater than 5. If this sub-expression is true, then IF returns the value 0.5. If the sub-expression is false, the If function returns 0.

The expression then subtracts the result returned by IF from the elapsed time.

The final result of the equation is the elapsed time minus 0.5 hours if the elapsed time is greater than 5 hours.

Drawing the Gantt Chart

The example uses several VBA routines to work with Gantt charts. The following sections describe those methods.

Making Buttons

[Gantt chart]

If you haven’t created buttons in Excel before, here’s how. On the Developer tab, open the Insert dropdown and select the Button item. Then click and drag to position the button. At that point, the Assign Macro dialog shown on the right appears.

The dialog is a bit confusing. If you just click OK, it does not create a macro associated with the button. Instead you should either select a macro from the list and click OK, or enter a name for a new macro in the upper text box and click New. (Or you can record a macro, but I’m not going to talk about that.)

For this example, I entered names for new macros and clicked New.

At this point, Excel creates the button and the empty macro. It gives the button a default caption such as Button7. To change the caption, right-click the button (if you left-click it, it will fire) and select Edit Text. Type the new caption and click off of the button to finish.

The context menu that you get when you right-click the button contains some other useful commands. In particular you can use the Assign Macro command to change the macro associated with the button. You can also use the Format Control command to change the button’s text color, font, and other format properties.

Removing Bars

When you click the worksheet’s Remove Bars button, the following code executes.

Sub RemoveBars()
    Dim sheet As Worksheet
    Dim shp As Shape
    
    ' Remove existing rectangles.
    Set sheet = Application.ActiveSheet
    For Each shp In sheet.Shapes
        If shp.Type = msoShapeRectangle Then shp.Delete
    Next shp
End Sub

This code gets the active worksheet. It then loops through that sheet’s Shapes collection. If a shape is a rectangle, the code calls its Delete method.

If you’re interested in how different languages work, there are several differences between how this VBA code works and how similar C# code would work.

  • Variables must be declared before they are used. In C# you can declare and initialize variables in the same statement as in int number = 1337;. In VBA you must declare variables separately before you use them.
  • You must use the Set keyword to assign reference variables. C# uses the same syntax for reference and value types.
  • The syntax is different. Obviously the syntax is very different. One thing to note here is that the Next statement may include the name of the looping variable, in this case shp, if you like, but it is not required. You cannot include anything else there, however, just the name of the looping variable or nothing.

One other issue worth mentioning is that the code modifies the Shapes collection as it loops through it. In general modifying a collection while you are looping through it is a bad idea. It can be confusing and may cause problems. For example, C# does not allow you to add or remove items while you are looping through a collection.

In VBA you can actually add and delete objects while you loop through a collection, but the results can be strange. If you add or remove an item before the one that you are currently looking at, the items in the collection are renumbered so it’s not clear what will happen. In short, don’t do that.

However, this example loops through the Shapes collection and calls each item’s Delete method. Somehow that removes the item from the worksheet and the collection without messing up the collection. I’m actually not sure exactly how it does that. It could be that it is using a snapshot of the collection for looping purposes.

Making One Bar

The following MakeBar subroutine creates a bar for a row in the worksheet. It’s a bit intimidating because it’s long, but it’s really not that complicated. It also makes the other methods easier.

Sub MakeBar(ByRef sheet As Worksheet, ByVal row_num As Integer)
    Const first_hour As Single = 4
    Const last_hour As Single = 18
    Const left_col As Integer = 5
    Const right_col As Integer = 11
    Const start_col As Integer = 2
    Const end_col As Integer = 3
    
    Dim start_hour As Single
    Dim end_hour As Single
    Dim x1 As Integer
    Dim x2 As Integer
    Dim dx As Single
    Dim y1 As Integer
    Dim bar_x As Integer
    Dim bar_y As Integer
    Dim bar_width As Integer
    Dim bar_height As Integer
    Dim new_bar As Shape
    
    ' See if this person has hours.
    If sheet.Cells(row_num, start_col).Value = "" Then Exit Sub
    If sheet.Cells(row_num, end_col).Value = "" Then Exit Sub

    ' Get the hour range.
    start_hour = sheet.Cells(row_num, start_col) * 24
    end_hour = sheet.Cells(row_num, end_col) * 24

    ' See where the bar should begin and end.
    x1 = sheet.Cells(row_num, left_col).Left
    x2 = sheet.Cells(row_num, right_col).Left + sheet.Cells(row_num, right_col).Width
    dx = (x2 - x1) / (last_hour - first_hour)
    bar_x = x1 + dx * (start_hour - first_hour)
    bar_width = dx * (end_hour - start_hour)
    bar_y = sheet.Cells(row_num, left_col).Top
    bar_height = sheet.Cells(row_num, left_col).Height
    Set new_bar = sheet.Shapes.AddShape(msoShapeRectangle, bar_x, bar_y, bar_width, bar_height)
    
    new_bar.TextFrame2.TextRange = _
        HourTo12HourTime(start_hour) & _
        " - " & _
        HourTo12HourTime(end_hour)
    new_bar.TextFrame2.TextRange.ParagraphFormat.Alignment = msoAlignCenter
    new_bar.TextFrame2.VerticalAnchor = msoAnchorMiddle
    
    new_bar.TextFrame2.TextRange.Font.Fill.ForeColor.RGB = RGB(0, 0, 0)
    new_bar.Fill.ForeColor.RGB = RGB(255, 200, 200)
    new_bar.Line.ForeColor.ObjectThemeColor = msoThemeColorText1
    new_bar.Line.Weight = 1
End Sub

The code starts by defining some constants.

The values first_hour and last_hour are the first and last hours that the program will draw. In this example, those are 4 (4:00 am) and 18 (6:00 pm).

The left_col adn right_col values indicate the first and last worksheet columns where the bars will be drawn. In this case, those are columns 5 and 11. That means the time 4 (4:00 am) corresponds to the left edge of column 5, and the time 18 (6:00 pm) corresponds to the right edge of column 11.

The start_col and end_col values indicate the columns where the employees’ start and end times are stored.

Next the code defines the variables that it will use later. It then checks the start and end hours for this row. If either of those values is blank, the subroutine returns without doing anything interesting.

The code then gets the row’s start and end times. Notice that it retrieves the times and multiplies them by 24 to convert Excel’s time format into hours after midnight.

Next the subroutine calculates x1 and x2, the X coordinates that give the bar’s limits. The value x1 gives the left edge of the leftmost drawing column, and x2 gives the right edge of the rightmost drawing column.

The code then calculates a scale factor dx to map elapsed hours to the X coordinates. It uses that value to calculate the left edge of the bar bar_x, the bar’s width bar_width, the Y coordinate of the bar’s top bar_y, and the bar’s height bar_height.

The program then passes those values into the Shapes collection’s AddShape method to create the new rectangle. It sets the new shape’s TextRange value to the text that we want to display inside the bar. To do that, the code calls the HourTo12HourTime method described shortly.

The code formats the bar’s text so it is centered both vertically and horizontally, and it makes the text black. (The default is white text in the rectangle’s lower left corner.) The subroutine finishes by setting the rectangle’s background color, theme color, and line weight. You can experiment with those values if you want to use other colors.

HourTo12HourTime

The HourTo12HourTime helper subroutine converts a numeric time value into a string with the format 4:30p. (I wrote this to produce a more concise time format so times would fit better inside the bars.)

The following code shows the HourTo12HourTime subroutine.

Function HourTo12HourTime(ByVal the_hour As Single) As String
Dim the_date As Date
Dim am_pm As String

    If the_hour = 12 Then
        am_pm = "n"
    ElseIf (the_hour = 0) Or (the_hour = 24) Then
        am_pm = "m"
    ElseIf the_hour < 12 Then
        am_pm = "a"
    Else
        am_pm = "p"
    End If

    If the_hour = 0 Then
        the_hour = 12
    ElseIf the_hour >= 13 Then
        the_hour = the_hour - 12
    End If
    
    the_date = CDate(the_hour / 24)
    HourTo12HourTime = Format$(the_date, "h:mm") & am_pm
End Function

The code first checks the time and sets the variable am_pm to n (for noon), m (for midnight), a (for AM), or p (for PM) accordingly.

Next the code checks for special hours. If the hours is 0, then it represents midnight. The code changes the hour to 12 so the result will be 12m instead of 0m.

The value midnight could be confusing in many programs because it may not be clear whether you’re talking about midnight at the beginning of the day or at the end of the day. In this example, the context should be obvious from the column that contains the value. The elapsed time calculation still depends on you using the correct value, however. You should use 0:00 for start times and 24:00 for end times.

If the time greater than or equal to 13, then it represents a time that is 1:00 PM or later. In that case, the code subtracts 12 so it can display the result using a 12-hour clock. The code does not do this if the time is between 12:00 and 1:00. For example, if the time is 12:45, then we want to leave it at that rather than subtracting 12 to get 0:45.

Making Many Bars

The following MakeBars subroutine calls MakeBar to create all of the Gantt chart bars.

Sub MakeBars()
    Const first_row As Integer = 2
    Const last_row As Integer = 75
    
    Dim i As Integer
    Dim sheet As Worksheet
    Dim shp As Shape

    ' Remove existing rectangles.
    Set sheet = Application.ActiveSheet
    For Each shp In sheet.Shapes
        If shp.Type = msoShapeRectangle Then shp.Delete
    Next shp

    ' Make the rows.
    For i = first_row To last_row
        MakeBar sheet, i
    Next i
End Sub

This subroutine first defines constants to hold the indexes of the first and last rows that could contain employee hours. The code then simply loops through those rows and calls the MakeBar subroutine for each.

Other Calculations

The workbook performs a couple of other simpler calculations. If you look again at the picture at the top of this post, you can see that the workbook adds up the hours for each week. That makes it easier to keep tabs on the total amount of time spent by all employees.

The bottom of the worksheet also adds up the total hours for each employee for the week, as shown in the following picture.


[Gantt chart]

Those sums are straightforward. For example, the formula for adding up Adam’s hours in cell B78 is the following.

=SUM(D4,D14,D24,D34,D49,D59,D69)

The total at the bottom simply adds all of the employees’ weekly totals.

Conclusion

As I said earlier, you could do something similar in C# or some other language. Feel free to do so. That will give more control over the layout. For example, you can probably arrange things differently to make the chart fit on a single page. The example workbook is set up to use two pages, mostly to keep the font large enough to read easily.

One very unusual feature of this post is that the download includes an executable file. Because this example uses VBA macros, the example is a macro-enabled workbook. In general, you should not open macro-enabled workbooks unless they come from a trusted source. If you must use one, including this one, you should open it with the macros disabled first and look at the macro code to see if there’s anything suspicious in there before you run the macros.

That being said, download the example, verify that the macros are safe, and the experiment.


Download Example   Follow me on Twitter   RSS feed   Donate




Posted in Excel, VBA | Tagged , , , , , , , , | Leave a comment

Create a Contain FillMode for filling polygons in C#

[FillMode]

The example Understand fill modes in C# showed how the Alternate and Winding FillMode values affect the result when you fill a self-intersecting polygon. In many cases, the Alternate FillMode leaves holes in a self-intersecting polygon while the Winding FillMode fills many of those holes. Sometimes, however, even the Winding FillMode leaves holes.


[FillMode]

For example, the picture on the right shows a self-intersecting polygon that is not completely filled with either the Alternate or Winding FillMode.

This example explains how you can fill a polygon completely. I’ll call this the Contain FillMode be cause it fills all of the area contained within parts of the polygon.

The example program is fairly long and some of the steps are annoyingly complicated. The basic idea is simple and the algorithm is still more or less understandable with some work, so that’s what I’ll describe here. You can download the example program to see the programming details.

The Basic Idea

The basic idea is simple. Start at a point on the outside edge of the polygon and work your way around it clockwise, following its outside edges.

It’s easy to do this by hand, but there are a lot of details to consider when you want a program to do it.

Details

Before we can start at a point on the polygon’s outside edge, we need to know how to find such a point. It turns out that this is relatively easy. Just find the upper-leftmost point. Loop through the polygon’s vertices and pick the one with the smallest X coordinate. If there’s a tie, pick the one that has the smallest Y coordinate.

That vertex must be on the polygon’s outside edge because no other vertex can have a smaller X coordinate. Using the Y coordinate to break ties isn’t necessary for this first step, but it makes the next step easier.

Now that we’ve found a point on the polygon’s outside edge, start moving clockwise around the polygon. To do that, follow the edge that heads the most to the left from the current point. In a “normal” polygon, each vertex is part of exactly two edges, so it’s relatively easy to pick the one that is most “to the left.” In more complicated polygons, a vertex may be shared by several edges.

To determine how far to the left an edge lies, you can use the VectorAngle method described in my post Find the angle between two vectors in C#.

[FillMode]

If you entered the current point along segment S, then we define “to the left” to mean the leftmost edge leaving that point as see when looking down segment S. For example, consider the polygon on the right and suppose you just came from point 1 to point 5. (Point 2 is actually also at that, it’s just drawn under the 5.) There are four possible edges leaving point 5 and they lead to points 0, 1, 3, and 4. When you look down the edge that we just followed 1 โ†’ 5, the leftmost choice leads to vertex 3.

As you continue following the edges around the outside of the polygon in this example, you eventually reach vertex 5 again, this time coming from vertex 4. Now when you look down the 4 โ†’ 5 segment, the leftmost edge leaving vertex 5 heads to vertex 0.

If you follow leftmost edges in this example, you end up following the arrows shown in the picture.

When you follow an edge, one of two things happens. Either you reach the edge’s endpoint or the edge is intersected by another one of the polygon’s edges.

If you reach the edge’s endpoint, you simply repeat the process and head out along the leftmost edge.

If the edge you follow is intersected by another edge, you stop at the closest point of intersection. Then you repeat the process, this time following the leftmost piece of edge that meets at that position.

[FillMode]

For example, consider the polygon shown at the top of this post and repeated on the right. Suppose you are at vertex 1 and you follow the edge that leads toward vertex 7. That edge is intersected by three other edges. You stop at the first one (marked 2) and then head out along the leftmost edge fragment at that point, which leads to vertex 3.

Note that the edge fragment that you follow might itself be intersected by other edges.

Now you simply repeat the process until you have surrounded the polygon.

The last question is, “How do you know when to stop?”


[FillMode]

You might check to see if you have visited a vertex more than once. That would mean you had completed a loop, so maybe you should stop. As the picture on the right shows, however, that won’t always work. In this example you need to visit vertex 5 twice to completely enclose the polygon. That approach also won’t work if several edges all intersect at the same point and you end up visiting that point more than once.

Another idea would be to stop if you return to the start point. This is only slightly better than the preceding approach. The preceding approach fails if any vertex or intersection must be visited more than once. The new approach only fails if the start vertex must be visited multiple times.


[FillMode]

A better approach is to stop if the program reaches the start point and heads out along the same edge that it followed during its first move. For example, consider the picture on the right. The program starts at vertex 3. (Vertex 0 is also there, it’s just drawn underneath.) The algorithm initially heads toward vertex 1. Later we visit vertex 3 again but this time we head toward vertex 4. The program visits vertex 3 one more time and heads toward vertex 1 again. We started with the 3 โ†’ 1 edge, so we now know we are done. The program breaks out of its loop and we have finished wrapping the polygon.

Algorithm

  1. Find the upper-leftmost vertex. Set to_point to that point.
  2. Set from_point to a point 10 units above to_point. In other words:
        from_point = new PointF(to_point.X, to_point.Y - 10);
  3. Repeat:
    1. Travel along segment S = from_point โ†’ to_point. There are two cases.
      1. If S intersects one or more edges:
        1. Find the closest point of intersection P.
        2. For each edge that intersects S at P:
          1. Find the endpoint of the edge that is leftmost as seen from from_point โ†’ to_point.
          2. Save the edge that has the most leftmost endpoint of all of these edges.
        3. Prepare to follow the new edge. To do that:
          1. Set new_from_point equal to P.
          2. Set new_to_point equal to the leftmost endpoint of the best edge.
      2. If S does not intersect any edges:
        1. Prepare to move to to_point. To do that:
          1. Set new_from_point equal to to_point.
          2. Examine the edges that leave to_point and find the one that has the leftmost endpoint. Set new_to_point equal to that leftmost endpoint.
    2. If next_from_point โ†’ next_to_point is the same edge that we originally followed at the start, then we are done so break out of the loop.
    3. If the result list is empty, then next_to_point is the second point that we will try to visit. Save it so we can know later if we try to cross this edge again. (So we can break out of the loop in the preceding step.)
    4. Officially move to the next point. To do that:
      1. Set from_point = next_from_point.
      2. Set to_point = next_to_point.
  4. After the loop ends, return the result list.

It may take some thought to see how this all works, particularly with the initial conditions.

For example, initially we set to_point equal to the start point and we set from_point to be a point directly above the start point. When you pick the leftmost edge leaving from_point as seen along this artificial edge, you find the first edge clockwise from the start point.

Conclusion

[FillMode]

The algorithm seems to work pretty well. It can handle polygons that require you to visit the same point multiple times, even if that point is the start point. It can even handle at least some cases where two edges coincide as in the picture on the right.


[FillMode]

I won’t guarantee that the example program can handle every weird special case. In fact, I know it cannot handle edges that overlap but do not completely coincide as in the picture on the right. For that polygon the program gets confused about which vertex it should visit when it traverses the overlapping edges and crashes.

There may be other odd cases that the program can’t handle, but overall it does pretty well. Download the example program to see how the code works and to experiment with it. If you find other kinds of special cases that confuse the program, or if you take the time to fix any of those special cases, please post a comment below.



Download Example   Follow me on Twitter   RSS feed   Donate




Posted in algorithms, drawing, graphics | Tagged , , , , , , , , , , , | 2 Comments

Find the angle between two vectors in C#

[example]

This example shows how you can find the angle between two vectors. The program has three main parts: selecting the points that define the vectors, drawing the vectors, and calculating the angle between them. The last task is the most important, but they’re all interesting so I’ll cover them all.

Selecting Vectors

The program stores up to three points in a list named Points.

private List Points = new List();

When you click the mouse over the program’s PictureBox control, the following event handler adds the point that you clicked to the list.

private void picCanvas_MouseClick(object sender, MouseEventArgs e)
{
    if (Points.Count > 2) Points = new List<PointF>();
    Points.Add(e.Location);
    picCanvas.Refresh();

    if (Points.Count == 3)
    {
        double radians = VectorAngle(
            Points[0], Points[1],
            Points[1], Points[2]);
        double degrees = radians / Math.PI * 180;
        lblAngle.Text = radians.ToString("0.00") + " radians, " +
            degrees.ToString("0.00") + " degrees";
    }
    else
        lblAngle.Text = "";
}

If the Points list already holds three points, then it is full so the program starts over. It sets Points equal to a new, empty list.

Next the code adds the point that you clicked to the Points list. It also refreshes the PictureBox to draw the new situation.

If the list now contains three points, then the program needs to calculate the angle between the two vectors defined by the points.

[example]

Note that you can consider the angle between the extension of the first vector and the second vector, or you can consider the angle between the two vectors when they are moved to have a common starting point as shown in the picture on the right. The two angles are the same, so you can think about the problem in whichever way is easier for you to visualize.

If we have three points defined, the program calls the VectorAngle method described later to find the angle between the two vectors. It then displays the angle in radians and degrees in the label lblAngle.

If we do not have three points defined, the program clears the lblAngle label.

Drawing Vectors

When the program’s PictureBox control needs to repaint, the following event handler executes.

private const int Radius = 4;

private void picCanvas_Paint(object sender, PaintEventArgs e)
{
    e.Graphics.SmoothingMode = SmoothingMode.AntiAlias;

    if (Points.Count > 1)
    {
        e.Graphics.DrawLines(Pens.Red, Points.ToArray());
        for (int i = 1; i < Points.Count; i++)
            DrawArrowhead(e.Graphics, Pens.Red, Radius,
                Points[i - 1], Points[i]);
    }

    foreach (PointF point in Points)
    {
        RectangleF rect = new RectangleF(
            point.X - Radius, point.Y - Radius,
            2 * Radius, 2 * Radius);
        e.Graphics.FillEllipse(Brushes.LightBlue, rect);
        e.Graphics.DrawEllipse(Pens.Blue, rect);
    }
}

The constants Radius indicates the radius of the circles that the program draws for each of the selected points.

The Paint event handler does the drawing. After setting the Graphics object’s SmoothingMode property to produce smooth lined and circles, the code checks whether the Points list contains more than one point. If there are more than two points, the program uses the DrawLines method to connect them in a series of line segments. (Either one or two segments depending on whether the list contains two or three points.)

It then loops through the segments and calls the DrawArrowhead method to draw arrowheads on the segments. That method is similar to the one described in the post Draw lines with arrowheads in C#. The new version is modified to pull the arrowheads back distance Radius from the segment’s end point so the arrowhead doesn’t sit under the points, but it’s otherwise similar. See that post and download the example to see the details.

After it has drawn the segments, the code loops through the points and draws a circle at each.

Calculating Angles

Calculating the angle is the fun, mathy part. The calculation relies on two vector calculations: the dot product and the cross product. The following sections talk a bit about vectors, how you can use the dot and cross products to calculate an angle’s sine and cosine, and how you can use that information to find the angle.

Vectors

Before I get to dot and cross products, I should briefly explain what a vector is. A vector is an object that has a direction and length. For example, you can think of one as an instruction like, “Go 10 units in the direction 75 degrees.” It’s usually easier to work with a Cartesian representation. For example, the vector <5, -9> means, “Go 5 units in the X direction and then -9 units in the Y direction.”

Vector mathematics is pretty interesting. For example, if you add a point ro a vector, you basically start at that point and then move as directed by the vector. The result is the point where you end up. To calculate that final point, you simply add the starting point’s coordinates to the vector’s components. For example, (3, 6) + <5, -9> = (3 + 5, 6 + -9) = (8, -3).

To find the vector between two points, you subtract their components. For example, the vector starting at the point (-2, 4) and ending at the point (6, 3) is <6 – -2, 3 – 4> = <8, -1>.

There is a bit more to vector mathematics, but the only additional things we really need for this example are dot products and cross products.

Dot Products

The dot product is a scalar (numeric) value calculated for two vectors. In general, if the vectors are A = <a1, a2, a3, …, aN> and B = <b1, b2, b3, …, bN>, then their dot product written A ยท B is given by A ยท B = a1 * b1 + a2 * b2 + a3 * b3 + … + aN * bN. Because we’re working with two-dimensional vectors, this is just a1 * b1 + a2 * b2.

It turns out that the dot product is also given by A ยท B = |A| * |B| * cosine(angle) where |A| and |B| are the lengths of the vectors and angle is the angle between them.

This gives us a way to find the cosine of the angle: use the first formula to calculate the vectors’ dot product and then divide it by the vectors’ lengths.

    cosine(angle) = (a1 * b1 + a2 * b2) / |A| / |B|

[example]

You can use the Math.Acos method to find the angle with this cosine, but unfortunately that is not enough to determine the angle uniquely. It turns out that angle and -angle have the same cosine, as shown in the picture on the right. If the blue segments all have length 1, then the red bar shows the cosine of both angles. If you don’t remember this from your high school trigonometry class, don’t worry about it. Just take my word for it that angle and -angle have the same cosine.

This is where the cross product comes in.

Cross Products

The cross product of two vectors is a third vector that is perpendicular to the first two. As with the dot product, you can calculate the cross product in two different ways and use them to get some information about the angle between the two vectors.

The cross product is not defined for two-dimensional vectors. That may make some sense because the result will be a third vector that is perpendicular to the original vectors and you can’t have a vector perpendicular to two vectors with all three lying in the same plane. To work around this, we simply pretend the two vectors are lying in the X-Y plane in three-dimensional space.

You can calculate the cross product of two-dimensional vectors by using the following formula.

    A ร— B = < a2 * b3 - a3 * b2,
             -a1 * b3 + a3 * b1,
              a1 * b2 - a2 * b1>

Because we are working with two-dimensional vectors, the a3 and b3 components are zero, so this equation simplifies to the following.

    A ร— B = <0, 0, a1 * b2 - a2 * b1>

This makes sense because the result vector should be perpendicular to the first two vectors. If those vectors lie in the X-Y plane, then the result vector points either straight up or straight down. That means its X and Y components should be zero.

The second way you can define the cross product is to say that the new vector is perpendicular to the first two and that the new vector has length given by the formula A ร— B = |A| * |B| * sin(angle). Again |A| and |B| are the lengths of vectors A and B.

If you look at the earlier formula, it’s easy to see that the length of the result vector is a1 * b2 – a2 * b1, so now we can calculate the sine of the angle. Just use the first formula to calculate the cross product and then divide the result by the lengths of vectors A and B.

    sine(angle) = (a1 * b2 - a2 * b1) / |A| / |B|

[example]

As was the case with the cosine, the sine does not uniquely determine the angle. The picture on the right shows two angles with the same sine. If the blue segments have length 1, then the green bars show the angles’ sines. Again if you don’t remember this, don’t worry about it. The gist of it is that the values angle and ฯ€ – angle have the same sine.

Finding Angles

Separately the dot product and cross product cannot uniquely identify an angle, but together they can. Geometrically the dot product tells you whether the angle lies to the left or right of the Y axis and the cross product tells you whether it lies above or below the X axis.

A Quick Aside: The last two picture have assumed that the first vector is horizontal. That makes the pictures easier to understand but it is not necessary. Basically you can take the picture of the original vectors and rotate the whole thing until the first vector is horizontal. The end result will give us the angle between the two vectors whether or not you rotate them. Basically a rotated angle is still the same angle.

There’s one more issue that you should understand before you see the code. Because Y coordinates increase downward in Windows Forms, everything we have talked about so far is upside down. That means angles will increase clockwise instead of counterclockwise.

The program uses the following VectorAngle method to calculate the angle between the two vectors p11 –> p12 and p21 –> p22.

// Return the angle between vector p11 --> p12 and p21 --> p22.
// Angles less than zero are to the left. Angles greater than
// zero are to the right.
private double VectorAngle(PointF p11, PointF p12, PointF p21, PointF p22)
{
    // Find the vectors.
    PointF v1 = new PointF(p12.X - p11.X, p12.Y - p11.Y);
    PointF v2 = new PointF(p22.X - p21.X, p22.Y - p21.Y);

    // Calculate the vector lengths.
    double len1 = Math.Sqrt(v1.X * v1.X + v1.Y * v1.Y);
    double len2 = Math.Sqrt(v2.X * v2.X + v2.Y * v2.Y);

    // Use the dot product to get the cosine.
    double dot_product = v1.X * v2.X + v1.Y * v2.Y;
    double cos = dot_product / len1 / len2;

    // Use the cross product to get the sine.
    double cross_product = v1.X * v2.Y - v1.Y * v2.X;
    double sin = cross_product / len1 / len2;

    // Find the angle.
    double angle = Math.Acos(cos);
    if (sin < 0) angle = -angle;
    return angle;
}

The method first subtracts the points’ components to find the vectors v1 and v2. (A and B in the earlier discussion.) It stores the results in two PointF variables. (It would be nice to store the results in two actual Vector objects, but the Vector class wasn’t introduced until later versions of the .NET Framework, which includes the System.Numerics namespace. We don’t really need too much from that class, so I decided to write the code like this so it would work in older versions.)

The method then calculates the lengths of the vectors.

Next the code calculates the dot product and divides it by the vector lengths to get the angle’s cosine. Similarly it calculates the cross product and divides it by the lengths to get the angle’s sine.

Now the method uses Math.Acos to get an angle that has the calculated cosine. If you look at the earlier picture, the one with the red horizontal bar, you’ll see that wee now need to determine whether the angle is the one on top of the X axis or the one below the X axis. (And then flip everything upside down because Y coordinates increase downward.)

To decide which angle to use, the program looks at the sine. If the sine is negative, then the angle is the one below the X axis, so the program negates the value angle.

Conclusion

[example]

The vector dot and cross products let you determine the angle between two vectors. The vectors can be in any arrangement, but I’m going to use them to find the angle when you turn from one line segment to another. The picture on the right shows various angles when you turn from the red segment onto one of the blue ones.

As always, download the example to see additional details and to experiment with it. Hopefully I’ll be using the VectorAngle method soon in another post.


Download Example   Follow me on Twitter   RSS feed   Donate




Posted in algorithms, geometry, mathematics | Tagged , , , , , , , , , , | 1 Comment

Crop scaled images to specific sizes in C#


[crop scaled images]

This example lets you crop scaled images to specific sizes in C#. The post Crop images to specific sizes in C# lets you drag a rectangle of a specified size around on an image to pick the part of the image that you want to save into a new file. I wrote that example to make it easier to create images with specific sizes. For example, Google Business is designed to favor images that have a 4:3 aspect ratio. That tool lets you pick an area that has the correct aspect ratio.

That example works pretty well, but lately I’ve been working with large images that don’t fit on the screen without scaling. The previous example does not scale images so it will only let you select areas that fit on the screen.

This example lets you crop scaled images so you can pick parts of the image that may not fit on the screen.

The basic approach used by this example is similar to the approach used by the previous one, but the differences are scattered throughout the code so I’m going to cover most of the new example’s more interesting parts in this post.

The Scale Menu

To use the program, invoke the File menu’s Open command to select a file. Enter the width and height of the area that you want to select in the text boxes.

Now you can use the Scale menu’s commands to set the image’s scale factor. The program lets you set the scale to 100%, 75%, 66%, 50%, 25%, and 15%. When you invoke one of those menu items, the following event handler executes.

private float ImageScale = 1f;

private void mnuScale_Click(object sender, EventArgs e)
{
    // Get the scale factor.
    ToolStripMenuItem menu_item =
        sender as ToolStripMenuItem;
    string scale_text =
        menu_item.Text.Replace("&", "").Replace("%", "");
    ImageScale = float.Parse(scale_text) / 100f;
    ShowScaledImage();

    // Display the new scale.
    mnuScale.Text = "Scale (" + menu_item.Text.Replace("&", "") + ")";

    // Check the selected menu item.
    foreach (ToolStripMenuItem item in mnuScale.DropDownItems)
    {
        item.Checked = (item == menu_item);
    }
}

This code gets the menu item that raised the event. It then gets the item’s text (as in &75%). It removes the & and % characters, parses the result, and divides by 100 to get the scale factor as a fraction (as in 0.75). It saves the result in the form-level variable ImageScale.

The code then calls the ShowScaledImage method described shortly. It then sets the Scale menu’s text to the selected menu item’s text with any & characters removed. The method finishes by looping through the items in the Scale menu and setting their Checked properties so the item that was selected is the only one that is checked.

Note that this approach makes it easy to add new scales to the Scale menu. Just add the new menu item with a numeric caption to the menu and set its Click event handler to this method. The code will automatically parse the new item’s text to get the scale factor. The new item is included in the Scale menu’s DropDownItems collection so the code will also check and uncheck it correctly.

ShowScaledImage

The following code shows the ShowScaledImage method.

private Bitmap OriginalImage = null;
private Bitmap ScaledImage = null;

// Display the scaled image.
private void ShowScaledImage()
{
    if (OriginalImage == null) return;
    int scaled_width = (int)(OriginalImage.Width * ImageScale);
    int scaled_height = (int)(OriginalImage.Height * ImageScale);
    ScaledImage = new Bitmap(scaled_width, scaled_height);
    using (Graphics gr = Graphics.FromImage(ScaledImage))
    {
        Point[] dest_points =
        {
            new Point(0, 0),
            new Point(scaled_width - 1, 0),
            new Point(0, scaled_height - 1),
        };
        Rectangle src_rect = new Rectangle(
            0, 0,
            OriginalImage.Width - 1,
            OriginalImage.Height - 1);
        gr.DrawImage(OriginalImage, dest_points, src_rect,
            GraphicsUnit.Pixel);
    }
    picImage.Image = ScaledImage;
    picImage.Visible = true;
    picImage.Refresh();
}

When you open a file, the program saves its image in variable OriginalImage. That code is fairly straightforward so I won’t show it here.

The ShowScaledImage method first checks OriginalImage to see if a file has been loaded and returns if it has not.

If you have loaded an image, the code multiplies the image’s dimensions by the scale factor to get the size of the scaled image. It then creates an image with that size and copies the original image onto it.

The method sets the picImage PictureBox control’s Image property to display the scaled image, displays the control, and refreshes it.

The Selection Rectangle

The program uses the variable ULCorner to keep track of the upper left corner of the selection rectangle.

private Point ULCorner = new Point(0, 0);

Note that the ULCorner value is in the original image’s unscaled coordinate system. Whenever the program needs to use this value to work with the scaled image displayed in the PictureBox, it will need to scale the coordinates.

The following SelectionRectangle method uses ULCorner to return a rectangle representing the selection area.

// Return the currently selected area.
private Rectangle SelectionRectangle(bool scaled)
{
    int x, y, width, height;

    // Get the desired dimensions.
    // If there's a problem, return a zero-size rectangle.
    if (!int.TryParse(txtWidth.Text, out width))
        return new Rectangle();
    if (!int.TryParse(txtHeight.Text, out height))
        return new Rectangle();
    x = ULCorner.X;
    y = ULCorner.Y;

    // Return the rectangle.
    if (scaled)
    {
        x = (int)(x * ImageScale);
        y = (int)(y * ImageScale);
        width = (int)(width * ImageScale);
        height = (int)(height * ImageScale);
    }
    return new Rectangle(x, y, width, height);
}

This code parses the selection rectangle’s width and height that you entered in the program’s text boxes. It also uses variable ULCorner to define the X and Y coordinates for the selection rectangle.

If the method’s scaled parameter is true, the code multiples the X and Y coordinates and the dimensions by the scale factor stored in variable ImageScale.

The method then creates the rectangle and returns it.

The SelectionRectangle method is used in three places: in the Paint event handler, when moving the selection rectangle, and when saving the selected area into a new file. The following three sections describe those places.

The Paint Event Handler

PictureBox refreshes, the following Paint event handler uses the SelectionRectangle method.

// Draw the selection rectangle.
private void picImage_Paint(object sender, PaintEventArgs e)
{
    try
    {
        // Draw the selection rectangle.
        using (Pen pen = new Pen(Color.Red, 2))
        {
            Rectangle rect = SelectionRectangle(true);
            e.Graphics.DrawRectangle(pen, rect);

            pen.Color = Color.Yellow;
            pen.DashPattern = new float[] { 5, 5 };
            e.Graphics.DrawRectangle(pen, rect);
        }
    }
    catch
    {
    }
}

This code creates a thick red pen and draws the rectangle. It then changes the pen’s color to yellow, gives it a dash pattern, and redraws the rectangle. The result is a rad and yellow dashed rectangle.

Notice that the code passes the SelectionRectangle method the parameter true to indicate that the rectangle should be scaled. That makes the rectangle fit the scaled image that is displayed in the PictureBox.

Moving the Selection Rectangle

The program uses the PictureBox control’s MouseDown, MouseMove, and MouseUp event handlers to move the selection rectangle. The following code shows the MouseDown event handler.

// Start dragging.
private void picImage_MouseDown(object sender, MouseEventArgs e)
{
    // If the mouse is not inside the
    // selection rectangle, do nothing.
    Rectangle rect = SelectionRectangle(true);
    if (!rect.Contains(e.Location)) return;

    // Start the drag.
    LastPoint = e.Location;
    Dragging = true;
}

This code calls the SelectionRectangle method to get the scaled selection rectangle. It then checks whether the mouse has been pressed within the rectangle. If the mouse is outside of the rectangle, the method returns.

If the mouse is inside the selection rectangle, the code saves the mouse’s current location and sets Dragging to true.

When the mouse moves over the PictureBox, the following code executes.

// Continue dragging.
private void picImage_MouseMove(object sender, MouseEventArgs e)
{
    if (!Dragging) return;
    ULCorner.X += (int)((e.Location.X - LastPoint.X) / ImageScale);
    ULCorner.Y += (int)((e.Location.Y - LastPoint.Y) / ImageScale);
    LastPoint = e.Location;
    picImage.Refresh();
}

This code checks the Dragging variable and returns is no drag is in progress.

If a drag is in progress, the code subtracts the mouse’s last location from its current location to see how far the mouse has moved. Because that motion is on the scaled image displayed in the PictureBox, the code divides the distance by ImageScale to see how far the mouse has moved in unscaled coordinates. It then updates the ULCorner variable’s X and Y coordinates.

The method finishes by refreshing the picImage PictureBox so it can redraw the selection rectangle in its new location.

When you release the mouse button, the following event handler executes.

// Stop dragging.
private void picImage_MouseUp(object sender, MouseEventArgs e)
{
    Dragging = false;
}

This code simply sets Dragging to false to end the current drag.

Saving the Selected Area

When you invoke the File menu’s Save As command, the following code executes.

// Save the selected area.
private void mnuFileSaveAs_Click(object sender, EventArgs e)
{
    if (sfdImage.ShowDialog() == DialogResult.OK)
    {
        try
        {
            // Copy the selected area into a new Bitmap.
            Rectangle rect = SelectionRectangle(false);
            Bitmap bm = new Bitmap(rect.Width, rect.Height);
            using (Graphics gr = Graphics.FromImage(bm))
            {
                gr.DrawImage(OriginalImage, 0, 0, rect,
                    GraphicsUnit.Pixel);
            }

            // Save the new Bitmap.
            SaveImage(bm, sfdImage.FileName);
        }
        catch (Exception ex)
        {
            MessageBox.Show(ex.Message);
        }
    }
}

This code displays a SaveFileDialog to let you pick the file that should contain the selected part of the image. If you pick a file and click Save, the code calls the SelectionRectangle method to get the selection rectangle’s location and size. It creates a new Bitmap with that size and copies the original image onto it.

The code finishes by using the SaveImage method to save the bitmap into the file with the appropriate file format (JPG, PNG, BMP, etc.). For information on the SaveImage method, see my post Save images with an appropriate format depending on the file name’s extension in C#.

Conclusion

This example lets you crop scaled images to a given size. That’s a big improvement over the previous example when you’re working with large images, and it’s good enough for my current needs.

It would still be nice to be able to specify an aspect ratio and then drag the corners of the rectangle to change its size while preserving the aspect ratio, but I’ll leave that for another time. If you get that working, post a note in the comments below.

To learn about additional details, see the previous example. Download this example to experiment with it.


Download Example   Follow me on Twitter   RSS feed   Donate




Posted in drawing, graphics, image processing, tools | Tagged , , , , , , , , , , , | 2 Comments

Create a schedule for a round robin tournament with home teams in C#


[round robin]

My book Essential Algorithms, Second Edition describes an algorithm for creating a round robin schedule in detail. The following posts also explain how you can create a round robin schedule in slightly less detail.

This post explains how you can pick home and away teams for each matchup.

With an Odd Number of Teams

You could simply pick one of the teams in each of the round robin schedule’s matchups to be the home team. For example, you could let team1 be the home team if (team1 + team2 + round) % 2 == 0. That would work but it does not guarantee that every team has the same number of home games. In many sports the home team has a large advantage, so this is not a very good solution.

There’s a better approach that depends on the way we created the round robin schedule in the first place. If you have an odd number of teams, draw a polygon with that number of sides and place a team on each vertex. The following picture shows the polygon for the five teams A, B, C, D, and E.


[round robin]

Now draw horizontal lines connecting the vertices with the same Y coordinate as shown in the following picture.


[round robin]

Each of the horizontal lines defines a matchup for the round robin’s first round. Because we have an odd number of teams, there is one team at the uppermost vertex that is not matched with any other team. That team gets a bye in this round.

Now rotate the teams one position clockwise. Alternatively you can think of rotating the polygon and its horizontal lines. That’s the approach taken in Essential Algorithms. Here I’m going to rotate the teams, mostly because it’s easier to redraw the picture.

Each time you rotate the teams, the horizontal lines define a new set of matchups. If there are N teams and you rotate them N times, then the horizontal lines define N sets of matchups for the N rounds of the tournament. Each team plays every other team once and has a bye. The following picture shows the rotated teams for this example.


[round robin]

Here’s the round robin schedule for this example.

Round 1
    A has a bye
    E vs B
    D vs C
Round 2
    E has a bye
    D vs A
    C vs B
Round 3
    D has a bye
    C vs E
    B vs A
Round 4
    C has a bye
    B vs D
    A vs E
Round 5
    B has a bye
    A vs C
    E vs D

Now how do we assign a home team for each matchup? One method is to look at the horizontal lines again. During the rotations, each team visits at each end of every horizontal line exactly once. If we pick one end of each horizontal line to represent a home team, then every line defines a home team. Furthermore every team is a home team once for each horizontal line, so every team is home the same number of times.

You could simply say that the left end of each horizontal line represents a home team, but then each team will be home for several rounds in a row and then away for several rounds in a row. That might not be a problem, but it seems like it might be emotionally taxing. It might make it hard for a team to build momentum after a long string of being the away team.

To avoid that, we can alternate the directions of the horizontal lines a shown in the following picture.


[round robin]

Here the horizontal arrows point to the home team. Now as you rotate the teams through the rounds, each one alternates between being the home team and the away team. The following picture shows the round robin schedule with the home teams enclosed in brackets.

Round 1
    A has a bye
    [E] vs B
    D vs [C]
Round 2
    E has a bye
    [D] vs A
    C vs [B]
Round 3
    D has a bye
    [C] vs E
    B vs [A]
Round 4
    C has a bye
    [B] vs D
    A vs [E]
Round 5
    B has a bye
    [A] vs C
    E vs [D]

If you study the schedule you can see that each team is the home team twice. (The math also checks out. There are 10 matchups. Each team is home twice, so there are a total of 2 * 5 = 10 home teams, one for each matchup.)

With an Even Number of Teams

The method described in the previous section works if you have an odd number of teams, but it won’t work for an even number of teams. If you use a polygon with an even number of vertices, then each team ends up playing only half of the other teams and it plays them each twice.

The solution is to pull one of the teams out and make a schedule for the remaining odd number of teams. Then place the team you removed in the bye position.

Unfortunately the “bye” team always plays the team at the top of the polygon and that position has no horizontal line. That means the home and away teams are undefined for those matchups.

One solution is to simply alternate so the “bye” team is the home team half of the time. For example, if round % 2 == 0, then make the “bye” team be the home team. The following schedule shows this approach.

Round 1
    A vs [bye]
    [E] vs B
    D vs [C]
Round 2
    [E] vs bye
    [D] vs A
    C vs [B]
Round 3
    D vs [bye]
    [C] vs E
    B vs [A]
Round 4
    [C] vs bye
    [B] vs D
    A vs [E]
Round 5
    B vs [bye]
    [A] vs C
    E vs [D]

Counting Home Games

Unfortunately in this schedule the teams are no longer the home team the same number of times. Now teams A, B, and D are home two times and teams C, E, and bye are home three times.

Note also that the teams do not strictly alternate between being home and away. Some teams are home twice in a row and others are away twice in a row.

At least they are close to being home the same number of times. For example, we don’t have one team playing home six times and another team being home only twice.

The question now is, “Can we rearrange things so every team is home the same number of times?” We can answer this question with a tiny bit of simple number theory.

If we have N teams, then there are N * (N – 1) matchups. Each matchup must have a home team, so there are N * (N – 1) / 2 home slots to fill.

If the home games are evenly distributed, then each team get the same number of home slots. That can only be possible if N * (N – 1) / 2 is evenly divisible by N. Here’s where the tiny bit of number theory come in. Don’t panic! Number theory can be daunting, but in this example it’s fairly simple.

If N * (N – 1) / 2 is evenly divisible by N, that means there is some integer k such that:

    N * k = N * (N - 1) / 2

That’s just the definition of what it means for one number to be divisible by another.

If we divide both sides of the equation by N, we get the following.

    k = (N - 1) / 2

Now if N is even, then (N – 1) is odd so (N – 1) / 2 is not an integer. That means we cannot satisfy this equation if N is even. In other words, we cannot divide up the home slots evenly among the teams. In our current solution the number of times the teams are home varies by only one, so that is the best solution possible.

If N is odd, then (N – 1) is even so (N – 1) / 2 is an integer. That means the equation is satisfied so we can divide the number of home slots evenly among the teams. The earlier solution for an odd number of teams does that, so we have an ideal solution.

Conclusion

It took a while to get here, but the previous method for generating the round robin schedule also gives us a fairly simple way to assign home and away teams. Just look at the index of the horizontal lines used to generate the schedule. If a line’s index is even, make the line’s first team be the home team. If the line’s index is odd, make the line’s second team be the home team.

The new example program does that. It also counts the number of times each team is the home or away team and displays the counts in the Console window so you can verify that each time is home the correct number of times.

Download the example program and look in the GenerateRoundRobinOdd and GenerateRoundRobinEven methods to see where the program assigns the home teams.

If you find these kinds of algorithms interesting, check out my book Essential Algorithms, Second Edition. It explains a wide variety of algorithms for performing all sorts of interesting tasks including this one. (Although it doesn’t cover assigning home teams.)


Download Example   Follow me on Twitter   RSS feed   Donate




Posted in algorithms, combinatorics, mathematics | Tagged , , , , , , , , , , , | Leave a comment

Understand fill modes in C#

[example]

C# drawing routines have two fill modes. In Windows Forms they are called Alternate and Winding. In WPF they are called Odd/Even and Non-Zero.

This example lets you draw polygons and see how the two fill modes determine which points are colored when you fill the polygon.

Fill Modes

In both modes, you can determine whether a point should be considered as inside the polygon by drawing a ray starting at the point and extending infinitely in any direction.

With the Alternate fill mode, the point is considered inside the polygon if ray crosses an odd number of the polygon’s edges.

[example]

For example, consider the red point in picture on the right. The black ray extending to the right crosses three of the polygon’s edges so that point is considered part of the polygon and it is shaded. In contrast, the ray extending from the green point crosses two edges so it is not part of the polygon.

With the Winding fill mode, you consider a ray leaving the point as before. This time you add one for each clockwise intersection and you subtract one for each counterclockwise intersection. Or if you prefer, add one each time the edge crosses the ray from left to right and subtract one when the edge crosses the ray from right to left.

[example]

For example, consider the rays shown in the picture on the right. From the red point, the ray crosses three edges right-to-left (-1), left-to-right (+1), and left-to-right (+1). The final count is +1, so the red point lies inside the polygon.

Next consider the green point. It ray crosses two edges left-to-right (+1) and left-to-right (+1). The final count is +2, so the green point also lies inside the polygon.

Finally consider the purple point. It ray crosses four edges right-to-left (-1), left-to-right (+1), right-to-left (-1), and left-to-right (+1). The final count is 0, so the purple point lies outside the polygon.

Note that the edges are considered clockwise/counterclockwise or left/right-to-right/left depending on the order in which the edges are drawn. Because the Winding fill mode relies on the total count being zero, it doesn’t matter which order you use. If the total is zero using one direction, then it will also be zero using the other direction.

A Surprising Case

[example]

It seems like the winding mode should fill “the whole polygon,” but it does not always as shown in the picture on the right. You can follow rays from a few points inside the isolated areas within the polygon to verify that this is correct.

The Example Program

The following snippet shows how the example program stores the points that make up the polygon.

private List Points = new List<Point>();
private bool Drawing = false;

The Points list holds the points. The Drawing variable indicates whether the user is currently defining a new polygon.

The following MouseClick event handler lets the user add new points to the list.

private void picCanvas_MouseClick(object sender, MouseEventArgs e)
{
    // See if this is a left or right click.
    if (e.Button == MouseButtons.Left)
    {
        // Left click.
        if (!Drawing)
        {
            // Start a new polygon.
            Points = new List<Point>();
            Drawing = true;
        }

        // Add the point to the polygon.
        Points.Add(e.Location);
    }
    else
    {
        // Right click.
        Drawing = false;
    }

    // Redraw.
    picCanvas.Refresh();
}

If the user clicked the left mouse button, then the code adds a new point to the list. If the user is not currently drawing a new polygon, then the code creates a new points list and sets Drawing to true to indicate that we are now drawing a new polygon.

The code then adds the new point to the list.

If the user clicked the right mouse button, then the program sets Drawing to false to indicate that we are done creating the new polygon.

The event handler finishes by refreshing the picCanvas PictureBox to make the following Paint event handler execute.

private void picCanvas_Paint(object sender, PaintEventArgs e)
{
    e.Graphics.SmoothingMode = SmoothingMode.AntiAlias;
    e.Graphics.Clear(picCanvas.BackColor);

    // See if we are drawing a new polygon.
    if (Drawing)
    {
        // Draw the polygon so far.
        if (Points.Count > 1)
            e.Graphics.DrawLines(Pens.Blue, Points.ToArray());
        DrawLineArrows(e.Graphics, Pens.Blue, Points,
            Points.Count - 1);
    }
    else
    {
        // Draw the finished polygon.
        if (Points.Count > 2)
        {
            FillMode fill_mode;
            if (radWinding.Checked)
                fill_mode = FillMode.Winding;
            else
                fill_mode = FillMode.Alternate;
            e.Graphics.FillPolygon(Brushes.LightBlue,
                Points.ToArray(), fill_mode);
            e.Graphics.DrawPolygon(Pens.Blue, Points.ToArray());
        }

        DrawLineArrows(e.Graphics, Pens.Blue, Points, Points.Count);
    }

    foreach (Point point in Points)
    {
        DrawDot(e.Graphics, Brushes.White, Pens.Black, point);
    }
}

If the user is currently drawing a polygon, the code invokes the Graphics object’s DrawLines method to draw the polygon’s edges. It does not connect the final point to the first point, and it does not fill the result. The code then calls the DrawLineArrows method described shortly to draw arrow indicators on the edges.

If the user is not drawing a new polygon, the code examines the radio boxes to see which one is checked and sets the variable fill_mode accordingly. The program then calls the Graphics object’s FillPolygon method, passing it fill_mode to indicate how the polygon should be filled. The code then uses the DrawPolygon method to draw the polygon’s edges, and then uses DrawLineArrows to draw arrow indicators on the edges.

After it has drawn and/or filled the polygon, the code uses the DrawDot method to draw dots on the polygon’s vertices.

The following code shows the DrawLineArrows method.

// Draw a sequence of line arrowheads.
private void DrawLineArrows(Graphics gr, Pen pen,
    List<Point> points, int num_segments)
{
    for (int i = 0; i %lt; num_segments; i++)
    {
        int j = (i + 1) % points.Count;
        DrawArrowhead(gr, pen, points[i], points[j]);
    }
}

This method loops through adjacent pairs of points and calls the following DrawArrowhead method to draw a direction indicator in the middle of the segment connecting the points.

// Draw an arrowhead in the middle of the
// line segment showing its direction.
private void DrawArrowhead(Graphics gr, Pen pen, Point p1, Point p2)
{
    float dx = p2.X - p1.X;
    float dy = p2.Y - p1.Y;
    float dist = (float)Math.Sqrt(dx * dx + dy * dy);
    dx /= dist;
    dy /= dist;
    const float scale = 4;
    dx *= scale;
    dy *= scale;
    float p1x = -dy;
    float p1y = dx;
    float p2x = dy;
    float p2y = -dx;
    float cx = (p1.X + p2.X) / 2f;
    float cy = (p1.Y + p2.Y) / 2f;
    PointF[] points =
    {
        new PointF(cx - dx + p1x, cy - dy + p1y),
        new PointF(cx, cy),
        new PointF(cx - dx + p2x, cy - dy + p2y),
    };
    gr.DrawLines(pen, points);
}

This method calculates the vector <dx, dy> between the start and end points. It finds the distance between the points and normalizes dx and dy so the vector has length 1. It the multiples those values by 4 to scale the result to length 4.

Next the code calculates two perpendicular vectors <p1x, p1y> and <p2x, p2y>. One of those vectors points to the line’s left and the other to the right.

The program then find the point (cx, cy) that is halfway between the two original points. It then adds the components of the vector along the segment <dx, dy> and the perpendicular vectors to find the points that define the arrowhead. The method finishes by drawing the lines that make up the arrowhead.

The last helper method used in the earlier code is the following DrawDot method.

// Draw a dot at this point.
private void DrawDot(Graphics gr, Brush brush, Pen pen, PointF point)
{
    const float radius = 3;
    RectangleF rectf = new RectangleF(
        point.X - radius,
        point.Y - radius,
        2 * radius, 2 * radius);
    gr.FillEllipse(brush, rectf);
    gr.DrawEllipse(pen, rectf);
}

This method simply fills and then outlines a circle at a specified point.

Conclusion

This post explains the difference between the Alternate (Odd/Even) and Winding (Non-Zero) fill modes. You can use the example program to draw polygons and then trace rays from points to see whether those points should be be shaded depending on the fill modes that you select.

It seems like there should be an addition to the fill modes that fills “the whole polygon.” When I have time I may try to write a method to do that.


Download Example   Follow me on Twitter   RSS feed   Donate




Posted in drawing, graphics | Tagged , , , , , , , , | 1 Comment

Display COVID-19 data for US states in C#


[COVID-19]

The example Graph world total COVID-19 cases, deaths, and recoveries in C# lets you view and compare COVID-19 data for countries around the world. This example lets you compare data for the US states and territories.

I asked in previous posts for people to let me know if they found time-sequence data for the states, and Adam Kelly did on The COVID Tracking Project.

Not surprisingly their data is not in the exact same format as the data used by my earlier examples, so this example needs to load and process its data differently. The same basic technique or loading the data in a CSV file still works, however, so I won’t describe the process here in detail.

I also don’t have time right now to explain how this program works in detail. Even worse, I have not had time to thoroughly test the program so it may contain more than my usual number of bugs. ๐Ÿ˜‰ If you find a bug, please note it in the comments below.

The program downloads its data from this URL: https://covidtracking.com/api/v1/states/daily.csv. Like the previous programs, it saves today’s data in a file named after the date (as in state_data2020_05_16.csv) and it doesn’t download the data if a file with that name already exists.

This program is different from the earlier ones because it lets you display multiple kinds of data simultaneously. For example, it lets you display the number of positive and negative test results at the same time. For example, the following picture shows positive (bottom) and negative (top) tests for New York.


[COVID-19]

Notice how the negative tests curve is slightly upward curving. That indicates that New York is continuing to expand testing, producing a greater number of tests each day.

Also notice that the positive tests curve is downward curving, showing that New York is recording a smaller number of new COVID-19 cases each day. The two curves together are a sign that New York is starting to stabilize.

This picture also shows an artifact of the data. Notice that the top curve ends with a small horizontal section. That could be due to the last two days having exactly the same values, but it may also be due to the fact that the data has not been updated for the last day. I would not assume that the curve is actually flat, particularly if the rest of the curve does not seem to be approaching horizontal.

Note also that the data may be spotty or unreliable. In fact, the CSV file containing the data even has a dataQualityGrade column that indicates the quality of the data for each row. The example program does not do anything with those values, but you might want to look at them if you find a result that you want to study more closely.

Right now it looks like the only states where the number of confirmed cases is starting to slow are VT, AK, HI, MT, NJ, and NY. The following picture shows the numbers of confirmed COVID-19 cases per million in those states except NY and NJ. (Those two states have had so many cases that including them skews the scale so much that you can’t really see the others.)


[COVID-19]

Most of the other states don’t look like their curves are leveling out. For example, the following picture shows the number of confirmed COVID-19 cases per million for WI, one of the states that has been most vocal about loosening restrictions.


[COVID-19]

You can use the example program to see how different states are doing.

One topic that I also think interesting is how the numbers of cases or fatalities relates to the restrictions in place in each state. For example, Hawaii has tight restrictions and an extremely low case rate. In contrast, Indiana has relatively loose restrictions and a much higher death rate.

The web site WalletHub posted the following picture showing ranking of state restriction level plotted against deaths.


[COVID-19]

You can go to this WalletHub page to see the actual chart, which is interactive and has tooltips.

Some parts of the picture make sense. I suspect the states in the upper right corner, such as NY and NJ, are there because they got hit hard early on and then introduced strict restrictions to fight their ongoing emergencies.

Hawaii’s position is also understandable. They have some very tight restrictions and very few deaths.

I might guess that some of the states closer to the lower left corner are there because of geography. For example, MT and UT are less densely populated than many other states so the coronavirus may not spread as quickly there. Similarly AK and WY are sparsely populated and they, too, have relatively low death rates.

I would like to see a version of the WalletHub plot with deaths per million rather than “Death Rate Ranking.” If the ranking simply means which country is best, second best, etc., then we might be able to learn a bit more by plotting actual death rates. For example, on the plot PA and NY are so close that they touch, but their numbers of deaths per million are very different with 1,147 deaths per million in NY and 339 deaths per million in PA. Maybe I’ll try to build a program that makes this comparison when I have time.

Meanwhile, download the example, experiment with it, and post any interesting findings in the comments below.


Download Example   Follow me on Twitter   RSS feed   Donate




Posted in drawing, graphics | Tagged , , , , , , , , , , , , , , , , , , , | Leave a comment

Make a random tree of generic TreeNode objects in C#

[random tree]

The example Handle generic TreeNode mouse events in C# explains how to build a tree where each node is represent by a TreeNode object. Each TreeNode contains its own object that determines how the node is drawn. This example the previous one to draw random trees.

The idea is simple. The program adds the tree’s nodes to a list. When it needs to add a new node to the tree, it picks a random node from the list to be the new node’s parent.

When the program starts, it uses the following code to build the random tree.

// The root node.
private TreeNode<CircleNode> Root;

// Make a tree.
private void Form1_Load(object sender, EventArgs e)
{
    // Make a list of all nodes.
    List<TreeNode<CircleNode>> nodes =
        new List<TreeNode<CircleNode>>();

    // Make the root node.
    Root = new TreeNode<CircleNode>(new CircleNode("Root"));
    nodes.Add(Root);

    // Make random child nodes.
    Random rand = new Random();
    for (char letter = 'A'; letter <= 'Z'; letter++)
    {
        // Make a new node.
        TreeNode<CircleNode> new_node =
            new TreeNode<CircleNode>(new CircleNode(letter.ToString()));

        // Pick a random parent node.
        int i = rand.Next(0, nodes.Count - 1);

        // Add the new node to the parent's children.
        nodes[i].AddChild(new_node);

        // Add the new node to the nodes list.
        nodes.Add(new_node);
    }

    // Arrange the tree.
    ArrangeTree();
}

This code declares the Root variable at the class level outside of any methods.

The form’s Load event handler creates a list of TreeNode objects named nodes. This list will hold references to all of the tree’s nodes.

Next the code creates the root node and adds it to the nodes list. It then loops over the letter A to Z. For each letter it creates a new node to display that letter. It then uses a Random object to pick a random index in the nodes list. It adds the new node to the children of the randomly selected node. It also adds the new node to the nodes list so it might have children later.

After it has finished building the tree, the event handler calls the ArrangeTree method just as the previous version of the program does.

The rest of the program is the same as the previous version. Download the example and see the previous post to see details such as how the program lays out and draws the tree.


Download Example   Follow me on Twitter   RSS feed   Donate




Posted in classes, generic, OOP | Tagged , , , , , , , , , , , , | Leave a comment

Quick COVID-19 update


[COVID-19]

Recently President Trump claimed that the United States and Germany were tied for the fewest COVID-19 deaths per capita in the world. The example Graph world total COVID-19 cases, deaths, and recoveries in C# allows you to check that claim in a matter of seconds.

The picture above shows the example program displaying the graphs of deaths per million for the United States and all countries with fewer deaths per million. There are only 10 countries that have a higher number of deaths per million. Of those, San Marino (population 33,785) and Andorra (77,006) have such small populations that a single event may dominate their results. Each of those countries has reported only between 40 and 50 deaths.

It is possible that some other countries have higher numbers of deaths per million than the United States, but their reporting isn’t reliable. For example, Eritrea has only reported 39 cases, has not reported a new case in almost a month, and had reported no deaths. There’s little hope of knowing what’s going on in that country.

In addition to seeing that the United States ranks 11th-from-last in the picture above, you can also see that Germany is only 7 spots better off. That puts them far below the United States in terms of deaths per million, but still higher than the majority of other countries.

Download the earlier example to study the data yourself.


Follow me on Twitter   RSS feed   Donate




Posted in drawing, graphics | Tagged , , , , , , , , , , , , , , , , | Leave a comment

Prevent “underlying connection was closed” errors in C#


[underlying connection was closed]

This example shows how to fix the error “The underlying connection was closed” when downloading a response from a web page.

Background

The basic approach for downloading a result from a web page is simple. Create a new WebClient object and use its DownloadString to download a URL result as a string. The following code snippet shows this technique.

using (WebClient client = new WebClient())
{
    return client.DownloadString(url);
}

This works fine for some web sites, but for others you get one of the following error messages.


[underlying connection was closed]

This seems to be caused by the web site using one of the newer security protocols. The solution is to set the ServicePointManager class’s static SecurityProtocol property to an appropriate value.

In older versions of .NET, that enumeration has two values, Ssl3 (Secure Socket Layer 3.0) and Tls (Transport Layer Security 1.0). Newer versions of the enumeration also include the values Tls11 (TLS 1.1), Tls12 (TLS 1.2), and Tls13 (TLS 1.3).

In Visual Studio 2019 with .NET Framework 4.5, I managed to get the earlier code snippet to work by setting SecurityProtocol to SecurityProtocolType.SystemDefault. That value has the numeric value 0, but for some reason setting this property to 0 doesn’t seem to work in Visual Studio 2008. Presumably that’s because of some difference in the Framework versions.

Fortunately explicitly setting the value to allow the TLS 1.1 and TLS 1.2 protocols seems to work.

A Fake Enumeration

To avoid using magic numbers, I wanted to create an enumeration holding the possible protocol values. Unfortunately the SecurityProtocol property expects a value of type SecurityProtocolType. If you set it equal to an enumeration that you define, Visual Studio complains that it cannot convert your enumeration into the necessary type.

In C# you can specify an enumeration’s type, but it must be an integral type such as int, uint, or short, so you cannot make it have the type SecurityProtocolType.

To work around that, I created the following class to define the possible values.

public class Protocols
{
    public const SecurityProtocolType
        protocol_SystemDefault = 0,
        protocol_Ssl3 = (SecurityProtocolType)48,
        protocol_Tls = (SecurityProtocolType)192,
        protocol_Tls11 = (SecurityProtocolType)768,
        protocol_Tls12 = (SecurityProtocolType)3072;
}

This class simply defines the protocol values listed on Microsoft’s web page SecurityProtocolType Enum. (Interestingly this is one of the pages that will not return a result unless you set the SecurityProtocol property.)

The example’s Form1_Load event handler uses the following statement to set the SecurityProtocol.

ServicePointManager.SecurityProtocol =
    Protocols.protocol_Tls11 | Protocols.protocol_Tls12;

The SecurityProtocol is a mask, so you can use the | operator to allow multiple protocols. This code allows TLS 1.2 and TLS 1.3.

Conclusion

So that’s the technique. Set ServicePointManager.SecurityProtocol to a combination of the protocols that you want to allow when downloading a web result. The Protocols class defines values that you can use almost as if Protocols were an enumeration.

Download the example to see additional details and to experiment on your own.


Download Example   Follow me on Twitter   RSS feed   Donate




Posted in internet, web | Tagged , , , , , , , , , , , , | 3 Comments