Let the user edit polygons in WPF and C#

[polygons]

The post Let the user draw a polygon in WPF and C# shows how you can let the user draw polygons in a WPF application. This post shows how you can let the user edit them.

Individually the program’s pieces aren’t too complicated, but there are a lot of them so the final result is somewhat involved.

XAML Code

The following XAML code builds the program’s interface.

<Window x:Class="howto_wpf_polygon_editor.Window1"
    xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
    xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
    Title="howto_wpf_polygon_editor" Height="300" Width="300">
    <Grid>
        <Grid.RowDefinitions>
            <RowDefinition Height="20"/>
            <RowDefinition Height="*"/>
        </Grid.RowDefinitions>
        <StackPanel Orientation="Horizontal">
            <RadioButton Content="New" Margin="5"
                Name="radNew" IsChecked="True" />
            <RadioButton Content="Edit" Margin="5"
                Name="radEdit" Click="radEdit_Click" />
        </StackPanel>
        <Border Grid.Row="1" Grid.Column="0" 
            Margin="10" BorderBrush="Gray" BorderThickness="1">
            <Canvas Name="canDraw" Background="Transparent"
                ClipToBounds="True"
                MouseDown="canDraw_MouseDown"
                MouseMove="canDraw_MouseMove"
                MouseUp="canDraw_MouseUp"/>
        </Border>
    </Grid>
</Window>

This is fairly similar to the code used by the previous example with just a couple of changes. The most obvious changes are that this example displays two radio buttons in a stack panel. This code also references a MouseUp event handler that the previous example didn’t need.

This example also sets the canDraw Canvas control’s ClipToBounds property to true. The earlier example didn’t need this because any mouse down events occurred within the canDraw control so the polygon had to stay inside the control.

However, when you’re editing in the new example, you can drag a polygon or one of its vertices off of the control. In that case the polygon will draw partly outside of the canvas and that just looks weird. (Actually you can see a similar weird effect in the previous program if you create a polygon and then resize the window so the polygon lies partly outside of the Canvas control. Set the ClipToBounds property if you want to prevent that.)

Setting ClipToBounds to true makes the program only draw the parts of the polygon that fit within the control.

Drawing Polygons

This program uses radio buttons to let you decide whether you’re drawing or editing polygons. When you move the mouse or press a mouse button, the program checks the radio buttons to see which mode it should use.

The following code shows the program’s MouseDown and MouseMove event handlers.

private void canDraw_MouseDown(object sender, MouseButtonEventArgs e)
{
    if (radNew.IsChecked.Value) ModeNew_MouseDown(sender, e);
    else ModeEdit_MouseDown(sender, e);
}
private void canDraw_MouseMove(object sender, MouseEventArgs e)
{
    if (radNew.IsChecked.Value) ModeNew_MouseMove(sender, e);
    else ModeEdit_MouseMove(sender, e);
}

When you press a mouse button, the code checks the radNew radio button to see whether you are trying to draw a new polygon. It then calls ModeNew_MouseDown or ModeEdit_MouseDown accordingly.

Similarly when you move the mouse, the program checks the radio button and calls ModeNew_MouseMove or ModeEdit_MouseMove.

The code that draws new polygons is similar to the code used by the earlier post so I won’t show it here. Look at that post for more information.

Editing Variables

The program uses the following variables to keep track of the polygon that it is editing.

private bool Editing = false;
private Extensions.PolygonHitTypes
    EditPolygonHitType =
        Extensions.PolygonHitTypes.None;
private Polygon EditPolygon = null;
private int EditPolygonPartIndex = -1;
private Point EditLastPoint = new Point(
    double.NegativeInfinity, double.NegativeInfinity);

These variables have the following purposes.

  • Editing – This is true while we are editing a polygon.
  • EditPolygonHitType – This enumerated value indicates whether we are editing a polygon’s vertex, edge, or nothing.
  • EditPolygon – This is the polygon that we are editing.
  • EditPolygonPartIndex – This gives the index of the polygon vertex or edge that we are editing.
  • EditLastPoint – This stores the last position of the mouse while we are moving a vertex or edge.

Mouse Movement

The following code executes when the user moves the mouse while the program is in editing mode.

private void ModeEdit_MouseMove(object sender, MouseEventArgs e)
{
    if (Editing)
    {
        if (EditPolygonHitType == Extensions.PolygonHitTypes.Vertex)
        {
            // Move the vertex.
            MoveVertex(e);
        }
        else if (EditPolygonHitType == Extensions.PolygonHitTypes.Edge)
        {
            // Move the polygon.
            MovePolygon(e);
        }
    }
    else
    {
        Cursor new_cursor = null;

        // See if we're over a Polygon.
        SetEditPolygon(e.GetPosition(canDraw));
        if (EditPolygonHitType == Extensions.PolygonHitTypes.Vertex)
        {
            new_cursor = Cursors.Cross;
        }
        else if (EditPolygonHitType == Extensions.PolygonHitTypes.Edge)
        {
            new_cursor = Cursors.SizeAll;
        }

        // Update the cursor.
        if (canDraw.Cursor != new_cursor)
            canDraw.Cursor = new_cursor;
    }
}

If variable Editing is true, then the user is currently editing a polygon. In that case, the program checks the EditPolygonHitType variable to see whether it is editing a polygon vertex or edge. It then calls the MoveVertex or MovePolygon method accordingly. I’ll describe those methods shortly.

If Editing is false, then the program is not currently editing a polygon. In that case, the code should display an appropriate cursor. The code sets the new cursor to a default value of null. It then calls SetEditPolygon (described later) to see what the mouse is over. If the mouse is over a polygon vertex or edge, the code updates the new cursor accordingly. Finally, if the drawing Canvas control is not already displaying the desired cursor, the code sets its cursor to the new one.

MoveVertex

If the user is editing a polygon vertex and the mouse moves, the program calls the following MoveVertex method.

// Move the editing vertex.
private void MoveVertex(MouseEventArgs e)
{
    Point cur_point = e.GetPosition(canDraw);
    double dx = cur_point.X - EditLastPoint.X;
    double dy = cur_point.Y - EditLastPoint.Y;
    Point new_point = new Point(
        EditPolygon.Points[EditPolygonPartIndex].X + dx,
        EditPolygon.Points[EditPolygonPartIndex].Y + dy);
    EditPolygon.Points[EditPolygonPartIndex] = new_point;
    EditLastPoint = cur_point;
}

This method calls e.GetPosition to get the mouse’s current position with respect to the canDraw Canvas control that contains the polygons. It then subtracts the X and Y coordinates of the mouse’s previously recorded position stored in variable EditLastPoint from the mouse’s new position to see how far the mouse has moved.

The code then updates the position of the vertex that the user is moving. The polygon is stored in variable EditPolygon. The polygon stores its vertices in its Points collection. Finally, the variable EditPolygonPartIndex holds the index of the vertex that the user is moving. So the program needs to update EditPolygon.Points[EditPolygonPartIndex].

Unfortunately you cannot modify the points in the polygon’s Points collection. If you try, you get the following compile-time error.

Cannot modify the return value of ‘System.Windows.Media.PointCollection.this[int]’ because it is not a variable

Fortunately you can set the Points entry equal to a new Point that has the correct coordinates, so that’s what this method does. It calculates the new X and Y coordinates that the vertex should have, uses them to make a new Point, and sets the Points entry.

The method finishes by saving the current mouse position in variable EditLastPoint so it is ready for the next mouse move.

MovePolygon

When the user clicks and drags over a polygon edge, the program does not move only the edge. Instead it moves the whole polygon. (You could modify it to move only the edge if you prefer.) The following MovePolygon method moves the editing polygon.

// Move the editing polygon.
private void MovePolygon(MouseEventArgs e)
{
    Point cur_point = e.GetPosition(canDraw);
    double dx = cur_point.X - EditLastPoint.X;
    double dy = cur_point.Y - EditLastPoint.Y;

    int num_points = EditPolygon.Points.Count;
    for (int i = 0; i < num_points; i++)
    {
        Point new_point = new Point(
            EditPolygon.Points[i].X + dx,
            EditPolygon.Points[i].Y + dy);
        EditPolygon.Points[i] = new_point;
    }
    EditLastPoint = cur_point;
}

Like the MoveVertex method, this code finds the mouse’s current position and determines how far the mouse has moved since the last time it was recorded. It then loops through the polygon’s Points collection and sets each vertex equal to a new Point with an updated position. As in the MoveVertex method, this code cannot modify the points’ X and Y coordinates, so it sets the entries equal to new points.

SetEditPolygon

When the user moves the mouse across the drawing canvas, the program calls the following SetEditPolygon method to see what is under the mouse.

// See if a polygon is at this point.
// Set EditPolygon, EditPolygonHitType, and
// EditPolygonPartIndex.
private void SetEditPolygon(Point point)
{
    EditPolygon = null;
    EditPolygonHitType = Extensions.PolygonHitTypes.None;
    EditPolygonPartIndex = -1;

    // See if we're over a Polygon.
    foreach (UIElement element in canDraw.Children)
    {
        Polygon polygon = element as Polygon;
        if (polygon == null) continue;

        if (polygon.IsAt(point, out EditPolygonHitType,
            out EditPolygonPartIndex))
        {
            EditPolygon = polygon;
            return;
        }
    }
}

This code assumes that the mouse is not over any polygon. It then loops through the elements inside the canDraw Canvas control’s Children collection. Note that a Polygon is not a control, it is a UIElement.

For each item in the Children collection, the code tries to convert the item into a Polygon. If the item is not a Polygon, then the conversion fails and variable polygon is null. In that case the code uses a continue statement to skip the rest of the loop and continue with the next item.

If the item is a Polygon, the code calls the IsAt extension method described shortly to see whether the mouse is over the item. If the mouse is over the item, the code saves the item in the EditPolygon variable and returns.

When the SetEditPolygon method is finished, the variables EditPolygon, EditPolygonHitType, and EditPolygonPartIndex are set to indicate the object under the mouse.

Extension Methods

The SetEditPolygon method described in the preceding section calls the IsAt extension method. That method is part of the public static class Extensions.

The following code shows the PolygonHitTypes enumerated type defined by that class.

public enum PolygonHitTypes
{
    None,
    Vertex,
    Edge,
};

This enumeration indicates the part of a polygon that lies below the mouse.

The following code shows the IsAt method.

public static bool IsAt(this Polygon polygon,
    Point point, out PolygonHitTypes hit_type,
    out int item_index)
{
    const double hit_radius = 2;
    int num_points = polygon.Points.Count;

    // See if the point is at a vertex.
    for (int i = 0; i < num_points; i++)
    {
        if (point.DistanceToPoint(polygon.Points[i]) < hit_radius)
        {
            hit_type = PolygonHitTypes.Vertex;
            item_index = i;
            return true;
        }
    }

    // See if the point is on an edge.
    Point closest;
    for (int i = 0; i < num_points; i++)
    {
        int j = (i + 1) % num_points;
        if (point.DistanceToSegment(
            polygon.Points[i],
            polygon.Points[j],
            out closest) < hit_radius)
        {
            hit_type = PolygonHitTypes.Edge;
            item_index = i;
            return true;
        }
    }
    hit_type = PolygonHitTypes.None;
    item_index = -1;
    return false;
}

This method extends the Polygon class. It first sets the constant hit_radius equal to 2. If the mouse is within two pixels of a polygon vertex or edge, then it is considered above that vertex or edge. You can make this constant larger if you want to make it easier to grab parts of the polygons.

The code then loops through the polygon’s vertices and uses the DistanceToPoint extension method to see how far the vertex is from the mouse position. If the vertex is within distance hit_radius of the mouse, the code sets the hit type and item index, and then returns true.

If none of the vertices is close enough to the mouse position, the method loops through the vertices again, this time looking at the edge that leads out of each vertex. For each edge, the code calls the DistanceToSegment extension method to see how far the mouse’s position is from the edge. If the mouse is close enough to the edge, the code sets the hit type and edge index, and then returns true.

If none of the vertices or edges is close enough to the mouse’s position, the method returns false.

The following code showos the DistanceToPoint extension method.

public static double DistanceToPoint(this Point from_point, Point to_point)
{
    double dx = to_point.X - from_point.X;
    double dy = to_point.Y - from_point.Y;
    return Math.Sqrt(dx * dx + dy * dy);
}

This method extends the Point structure. (Point is a struct not a class.) It simply calculates the distance between the start point and another point and returns the result.

The DistanceToSegment method also extends the Point structure. It uses the method described in the post Find the shortest distance between a point and a line segment in C# to find the distance between the point and a line segment. See that post and download this example to see the details.

MouseDown and MouseUp

The previous sections explain how the program moves a polygon or a vertex when you move the mouse. Those movements start and stop when you press and release the mouse.

The following code executes when you press the mouse button while in editing mode.

private void ModeEdit_MouseDown(object sender, MouseButtonEventArgs e)
{
    // See if we are over a polygon.
    if (EditPolygon == null) return;

    EditLastPoint = e.GetPosition(canDraw);
    Editing = true;
    canDraw.CaptureMouse();
}

This code checked the EditPolygon variable to see if the mouse is over a polygon. (That variable will have been set by the ModeEdit_MouseMove method.) If the mouse is not over a polygon, the MouseDown event handler returns.

If the mouse is over a polygon, the event handler saves the mouse’s current position in variable EditLastPoint and sets Editing = true.

The code also captures the mouse for the canDraw to make future mouse events go to that control. If you don’t do that, then weird things can happen when you move the mouse off of the control. First, the MouseMove event does not fire so the program stops editing the polygon until the mouse returns to the control.

That’s a bit strange, but not a big deal. A worse problem occurs if you release the mouse button while the mouse is not over the control. In that case, the mouse button is up, but the MouseUp event didn’t fire so the program thinks it is still in editing mode. That means you cannot stop editing until you press and release the mouse again, this time over the control.

Capturing the mouse makes the MouseUp event go to the control even if the mouse is not over it so the program can finish editing.

This has the annoying side effect that you can drag a polygon off of the top or left side of the control where you cannot get it back. You can restrict the positions where you can move a polygon and its vertices if you like.

When the user moves the mouse after this point, the ModeEdit_MouseMove method adjusts the polygon. When the user releases the mouse button, the following event handler stops editing the polygon.

private void canDraw_MouseUp(object sender, MouseButtonEventArgs e)
{
    Editing = false;
    canDraw.ReleaseMouseCapture();
}

This code sets Editing = false and releases its earlier mouse capture. After this point the EditMode_MouseMove method no longer edits a polygon and instead updates the cursor if necessary to show what’s under the mouse.

Switching Modes

That concludes the polygon editing code, but there’s one more odd case to handle. If you are in the middle of creating a new polygon and you check the Edit radio button, the program must stop drawing the new polygon so it can enter editing mode. To make that possible, this example moved the code used by the previous example to finish creating a polygon into a new FinishPolygon method. When you right-click to stop drawing a new polygon, or when you click the Edit radio button, the program calls this method.

For example, when you click the Edit radio button, the following event handler executes.

// If we're making a new Polygon, finish it.
private void radEdit_Click(object sender, RoutedEventArgs e)
{
    FinishPolygon();
}

// Remove the temporary polyline.
canDraw.Children.Remove(NewPolyline);
NewPolyline = null;
}

The FinishPolygon method uses code similar to the code used by the previous example so I won’t show it here. Download this example or read the previous post to see the details.

Conclusion

Individually the pieces of this example aren’t too complicated, but it does take a bit of work to see how all of the pieces fit together. Download the example to experiment with it and to see additional details.

You can also enhance the program if you like. For example, you could add a trashcan icon and delete any polygons that you drag over the icon. Or you could allow the user to drag polygon edges instead of entire polygons. You could even let the user right-click a polygon to display a popup menu where the user could change the polygon’s stroke and fill colors and styles. If you build something interesting and post it somewhere, let us know in a comment below.


Download Example   Follow me on Twitter   RSS feed   Donate




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

Let the user draw a polygon in WPF and C#

[polygon]

In a Windows Forms application, you can let the user draw a polygon by tracking mouse movement and redrawing the picture whenever necessary to draw the partially completed polygon. A WPF program normally does not do its own drawing. Instead it uses classes such as Ellipse, Rectangle, and Polygon to display shapes.

This example shows how you can let the user draw a polygon. In my next post, I’ll show how you can let the user edit polygons.

XAML Code

This example uses the following XAML code to define its user interface.

<Window x:Class="howto_wpf_draw_polygon.Window1"
    xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
    xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
    Title="howto_wpf_draw_polygon" Height="300" Width="300">
    <Grid>
        <Border Margin="10" BorderBrush="Gray" BorderThickness="1">
            <Canvas Name="canDraw" Background="Transparent" Cursor="Cross"
                MouseDown="canDraw_MouseDown" MouseMove="canDraw_MouseMove"/>
        </Border>
    </Grid>
</Window>

The main Grid control contains a single Border, which holds the Canvas on which the user draws.

This code includes three properties of interest for this example. The two most obvious are that it declares event handlers for the Canvas control’s MouseDown and MouseMove events.

The less obvious important property is the Canvas control’s Background property. By default that property is null, and when that property is null, the control cannot receive mouse events. This example sets the property to Transparent. You can set it to some other value such as white, but you must set it to something or the program won’t work.

NewPolyline

[example]

When you draw a new polygon, you click to define its vertices. Each time the user clicks a point, you could connect the points so far to form a polygon. If you try that, you’ll see that the result seems really awkward.

It’s more natural to connect the points that you have clicked so far but not close the shape to form a polygon. The result is a polyline like the one in the picture on the right, which is similar to a polygon except the final point is not connected to the first point.

This example uses a Polyline object to show the points that the user has clicked. When the user is finished picking points, it replaces the Polyline object with a Polygon.

The following variable, which is declared at the form level, keeps track of the new Polyline while the user is drawing.

private Polyline NewPolyline = null;

When the user presses the left mouse button, the program adds a new point to this polyline. When the user clicks the right button, the program converts the polyline into the final polygon.

The program keeps an extra point at the end of the polyline to keep track of the mouse’s position as the user moves it. For example, suppose the user has left-clicked twice to define two points. In that case, the polyline contains three points, the two that the user clicked and a third that tracks the mouse position. When the user moves the mouse, the program updates that third point’s location so the polyline shows where the next point would be if the user left-clicked again.

When the user right-clicks, the program discards that extra point and converts the remaining points into a Polygon.

MouseDown

Most of this example’s interesting code occurs in the following MouseDown event handler.

private void canDraw_MouseDown(object sender, MouseButtonEventArgs e)
{
    // See which button was pressed.
    if (e.RightButton == MouseButtonState.Pressed)
    {
        // See if we are drawing a new polygon.
        if (NewPolyline != null)
        {
            if (NewPolyline.Points.Count > 3)
            {
                // Remove the last point.
                NewPolyline.Points.RemoveAt(NewPolyline.Points.Count - 1);

                // Convert the new polyline into a polygon.
                Polygon new_polygon = new Polygon();
                new_polygon.Stroke = Brushes.Blue;
                new_polygon.StrokeThickness = 2;
                new_polygon.Points = NewPolyline.Points;
                canDraw.Children.Add(new_polygon);
            }
            canDraw.Children.Remove(NewPolyline);
            NewPolyline = null;
        }
        return;
    }

    // If we don't have a new polygon, start one.
    if (NewPolyline == null)
    {
        // We have no new polygon. Start one.
        NewPolyline = new Polyline();
        NewPolyline.Stroke = Brushes.Red;
        NewPolyline.StrokeThickness = 1;
        NewPolyline.StrokeDashArray = new DoubleCollection();
        NewPolyline.StrokeDashArray.Add(5);
        NewPolyline.StrokeDashArray.Add(5);
        NewPolyline.Points.Add(e.GetPosition(canDraw));
        canDraw.Children.Add(NewPolyline);
    }

    // Add a point to the new polygon.
    NewPolyline.Points.Add(e.GetPosition(canDraw));
}

If the right button was pressed and NewPolygon is not null, then the user is trying to finalize the polygon.

Remember that the program is going to discard the polyline’s final point, which tracks the mouse position. If the polyline contains three or fewer points, then it does not include enough points to discard one and still define a polygon.

If NewPolyline contains more than three points, the code removes the last point from the polyline’s Points collection. It then creates a new Polygon object, sets its Point collection equal to the collection used by the Polyline, and adds it to the canDraw Canvas control.

Note that the code gives the new Polygon a Stroke and StrokeThickness. If you don’t do that, the Polygon will exist, but it will not be visible.

The event handler then removes NewPolyline from the canDraw control’s Children collection, sets NewPolyline = null, and returns.

When the code sets NewPolyline = null, that object is no longer in use so it can be garbage collected. However, its Points collection is now being used by the new Polygon object, so that collection will not be garbage collected.

If the user pressed the right mouse button, then it gets no farther than this. If left button was pressed, then the user is trying to add a new point at the end of the polyline.

If NewPolyline is null, the program sets NewPolyline to a new Polyline object. It sets some stroke properties so the object will be visible and adds it to the canDraw control’s Children collection.

The code also uses e.GetPosition to get the mouse’s current position with relative to the canDraw control. This is one of the larger differences between Windows Forms and WPF mouse events. In Windows Forms the event handler’s parameters give you the mouse’s location. In WPF you need to call e.GetPosition, passing it the control whose coordinate system you want to use to get the location. The code adds the mouse’s current position to the new polyline.

After it has created the new polyline if necessary, the code adds the mouse’s current location to the polyline. If this is a new polyline, then that location is added twice. The first instance is the polyline’s first point. The second instance is the one that gets updated as the user moves the mouse. That happens in the MouseMove event handler described next.

MouseMove

The MouseMove event handler shown in the following code is relatively simple.

private void canDraw_MouseMove(object sender, MouseEventArgs e)
{
    if (NewPolyline == null) return;
    NewPolyline.Points[NewPolyline.Points.Count - 1] =
        e.GetPosition(canDraw);
}

If NewPolygon is null, this code simply returns. Otherwise the code sets the polyline’s last point equal to the mouse’s current location. (Notice how the code uses e.GetPosition again.) That updates the polyline’s final point so it lies under the mouse. The polyline automatically redraws itself to show the new shape.

Conclusion

Drawing a new polygon in WPF is very different from the way you draw a new polygon in Windows Forms, but it’s not too hard. The MouseDown event handler creates a Polyline, adds points to it, or converts it into a Polygon object. The MouseMove event handler updates the polyline’s last point to show progress.

Download the example to experiment with it. In my next post I’ll show how you can let the user edit Polygon objects.


Download Example   Follow me on Twitter   RSS feed   Donate




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

Fill a target area found by trilateration in C#

[trilateration]

The post Perform trilateration in C# explains how a C# program can use trilateration to find an area where a target point lies. This post explains how you can draw that area.


The Target Area

[trilateration]

The target area found by trilateration is similar to a triangle except each of its sides is a circular arc. The picture on the right shows three circles with the target area found by trilateration drawn in bold arcs.

To draw that area, we must solve two problems. First, we must find the arcs. Second, we must arrange the arcs so they are joined end-to-end in the right order.

Finding Arcs

To keep track of the arcs that define the target area, this example uses a new ArcInfo class. The following code shows the class declaration, its fields, and its constructor. (I’ll show the rest shortly.)

public class ArcInfo
{
    public PointF Point1, Point2, Center;
    public RectangleF Rect;
    public float StartAngle, SweepAngle;

    public ArcInfo(PointF center, PointF point1, PointF point2)
    {
        Center = center;
        Point1 = point1;
        Point2 = point2;

        float dx1 = Point1.X - Center.X;
        float dy1 = Point1.Y - Center.Y;
        float dx2 = Point2.X - Center.X;
        float dy2 = Point2.Y - Center.Y;

        // Get the radius and rectangle.
        float radius = (float)Math.Sqrt(dx1 * dx1 + dy1 * dy1);
        Rect = new RectangleF(
            Center.X - radius,
            Center.Y - radius,
            2 * radius, 2 * radius);

        // Calculate the angles.
        double angle1 = Math.Atan2(dy1, dx1);
        double angle2 = Math.Atan2(dy2, dx2);

        // Make angle2 > angle1.
        if (angle1 > angle2) angle2 += 2 * Math.PI;

        // If the sweep is more thn 180 degrees, swap them.
        double sweep = angle2 - angle1;
        if (sweep > Math.PI)
        {
            Swap(ref angle1, ref angle2);
            Swap(ref Point1, ref Point2);
            angle2 += 2 * Math.PI;
            sweep = angle2 - angle1;
        }

        StartAngle = (float)(angle1 * 180 / Math.PI);
        SweepAngle = (float)((angle2 - angle1) * 180 / Math.PI);
    }
    ...
}

The trilateration code described in the earlier post finds the points at the ends of the arcs that define the target area. The ArcInfo class stores those points in its Point1 and Point2 fields. It also stores the center of the arc’s circle in the Center field.

To draw an arc in .NET, we need a bounding rectangle, a start angle, and a sweep angle. The ArcInfo class stores those values in its Rect, StartAngle, and SweepAngle fields.

The class’s constructor takes as parameters the circle’s center and the two points at the ends of the arc. The code saves those values and then calculates the horizontal and vertical (dx and dy) differences between those points and the circle’s center.

Next the code finds the distance between the circle’s center and the first arc end point to get the circle’s radius. From the center point and the radius, the code defines the circle’s bounding rectangle.

The constructor then uses the two points’ dx and dy values and the Math.Atan2 function to calculate the points’ angles with respect to the center point.

Note that Math.Atan returns an angle in radians, but the .NET arc drawing method uses degrees. This code works in radians for a while but then converts the results to degrees so drawing is easier later.

For definiteness, I want the class to store the points so the arc from Point1 to Point2 is clockwise and the smaller of the two possible arcs so it spans no more than π radians (180 degrees). To achieve those goals, the code first guarantees that angle1 <= angle2. If that is not initially true, the code adds 2 π radians (360 degrees) to angle2. After that angle2 must be larger than angle1.

Now that angle1 < angle2, we know that the arc from Point1 to Point2 is clockwise, but we don’t know if the arc is the larger or smaller arc between the two points. To find out whether or not this is a large arc, the code subtracts the two angles to get the sweep angle and then tests whether it is greater than π radians (180 degrees).

If the sweep angle is greater than π radians, then we want the arc to sweep from point2 to point1. That will give us a clockwise arc that is no larger than π radians.

To do that, we swap the two angles. The code uses the Swap helper method described shortly to interchange the two angles and the two points. We originally adjusted the angles if necessary so the second angle was greater than the first. After swapping those values, that is no longer true. To make that true again, so the arc sweeps clockwise, the code adds 2 π to the new value of angle2 so that it is greater than angle1. The program then recalculates the sweep angle for the new angles.

Finally, the constructor saves the start and sweep angles in fields StartAngle and SweepAngle.

The following code shows the Swap helper method.

public void Swap<T>(ref T a, ref T b)
{
    T temp = a;
    a = b;
    b = temp;
}

This method simply uses a temporary variable to swap two values. The only interesting thing about it is that it uses a type parameter so it can swap two items of just about any type including float and PointF values.

The ArcInfo class’s final method, Draw, uses the following code to draw the arc.

public void Draw(Graphics gr, Pen pen)
{
    gr.DrawArc(pen, Rect, StartAngle, SweepAngle);
}

This method simply calls a Graphics object’s DrawArc method, passing it the arc’s bounding rectangle, start angle, and sweep angle.

Arranging Arcs

After the program has found the three arcs that define the target area, it needs to arrange them so they bound the area. To do that correctly, the arcs must all be oriented in the same direction, either clockwise or counterclockwise. The ArcInfo class automatically orients arcs so they are clockwise, so that part is done.

[trilateration]

Now we just need to arrange the arcs so they connect end-to-end in the right order. This is fairly easy, but you can’t just assume that any order will do. If you do this incorrectly, you’ll get the arrangement shown in the picture on the right. If you use the incorrectly ordered arcs to build a GraphicsPath and then fill the path, it will look normal because the fill mode used by the FillPath method fills all of the area inside the arcs. However, if you draw the path instead of filling it, you’ll see the odd shape shown in the picture.

The program orders the arcs in its Trilaterate method, which is shown below. Most of that method is similar to the version used by the previous example. The new code is highlighted in blue.

// Trilaterate.
// Throw an exception if there is a problem.
private PointF[] Trilaterate(RectangleF circle1,
    RectangleF circle2, RectangleF circle3,
    out ArcInfo[] arc_infos)
{
    // Convert the circles from bounding rectangles
    // to centers and radii.
    float cx1 = circle1.X + circle1.Width / 2f;
    float cy1 = circle1.Y + circle1.Height / 2f;
    float cx2 = circle2.X + circle2.Width / 2f;
    float cy2 = circle2.Y + circle2.Height / 2f;
    float cx3 = circle3.X + circle3.Width / 2f;
    float cy3 = circle3.Y + circle3.Height / 2f;
    float r1 = circle1.Width / 2f;
    float r2 = circle2.Width / 2f;
    float r3 = circle3.Width / 2f;

    // Find the points of intersection.
    PointF
        intersection12a, intersection12b,
        intersection23a, intersection23b,
        intersection31a, intersection31b;
    if (FindCircleCircleIntersections(
            cx1, cy1, r1, cx2, cy2, r2,
            out intersection12a, out intersection12b) == 0)
        throw new Exception("circle1 and circle2 do not intersect.");
    if (FindCircleCircleIntersections(
            cx2, cy2, r2, cx3, cy3, r3,
            out intersection23a, out intersection23b) == 0)
        throw new Exception("circle2 and circle3 do not intersect.");
    if (FindCircleCircleIntersections(
            cx3, cy3, r3, cx1, cy1, r1,
            out intersection31a, out intersection31b) == 0)
        throw new Exception("circle3 and circle1 do not intersect.");

    // Find the points that make up the target area.
    PointF[] triangle = new PointF[3];
    PointF center1 = new PointF(cx1, cy1);
    PointF center2 = new PointF(cx2, cy2);
    PointF center3 = new PointF(cx3, cy3);
    if (Distance(intersection12a, center3) <
        Distance(intersection12b, center3))
            triangle[0] = intersection12a;
    else
        triangle[0] = intersection12b;
    if (Distance(intersection23a, center1) <
        Distance(intersection23b, center1))
            triangle[1] = intersection23a;
    else
        triangle[1] = intersection23b;
    if (Distance(intersection31a, center2) <
        Distance(intersection31b, center2))
            triangle[2] = intersection31a;
    else
        triangle[2] = intersection31b;

    // Make ArcInfo data.
    ArcInfo arc_infos1 = new ArcInfo(
        center1,
        triangle[0],
        triangle[2]);
    ArcInfo arc_infos2 = new ArcInfo(
        center2,
        triangle[0],
        triangle[1]);
    ArcInfo arc_infos3 = new ArcInfo(
        center3,
        triangle[1],
        triangle[2]);

    // Order the ArcInfo data.
    arc_infos = new ArcInfo[3];
    arc_infos[0] = arc_infos1;
    if (arc_infos1.Point2 == arc_infos2.Point1)
    {
        arc_infos[1] = arc_infos2;
        arc_infos[2] = arc_infos3;
    }
    else
    {
        arc_infos[1] = arc_infos3;
        arc_infos[2] = arc_infos2;
    }

    return triangle;
}

This method finds the points where the three circles intersect as before. For each pair of intersections, it determines which point is closer to the remaining circle and adds that closer point to the triangle array.

That defines the triangular target area. Now we just need to convert the triangle into arc data.

The program creates three ArcInfo objects to define the sides of the target area. The ArcInfo class constructor arranges each object’s Point1 and Point2 values so the arcs are oriented clockwise.

Next the code creates a new arc_infos array to hold the ArcInfo objects in their proper order and adds the first arc to the array.

The method then compares the first arc’s end point to the second arc’s starting point. If they are the same point, then the second arc should follow the first. In that case, the code adds the second arc to the arc_infos array’s second position and places the third arc in the third position.

If the first arc does not end where the second arc begins, then the code places the third arc in the arc_infos array’s second position and puts the second arc in the last position.

The method finishes by returning the triangle that defines the target area. At this point you might not even need that triangle any more because the arc_infos array defines the target area more precisely. You can even use the ArcInfo objects’ Point1 values to retrieve the corners of the triangle if you want them. I left the method as it is to minimize changes.

Building the Path

The last really interesting piece of this example is the following MakeArcPath method, which uses the ArcInfo objects to create a GraphicsPath.

// Make the arc path.
private GraphicsPath MakeArcPath(ArcInfo[] arc_infos)
{
    GraphicsPath path = new GraphicsPath();

    foreach (ArcInfo arc_info in arc_infos)
    {
        path.AddArc(arc_info.Rect,
            arc_info.StartAngle, arc_info.SweepAngle);
    }
    return path;
}

This method creates a new GraphicsPath object. It then loops through the arcs in the arc_infos array and adds each of them to the path. The method finishes by returning the path.

Later the program’s Paint event handler fills the target area by calling the Graphics object’s FillPath method, passing it the path saved in the variable ArcPath.

// Fill the area.
e.Graphics.FillPath(Brushes.Pink, ArcPath);

Conclusion

This method seems to work fairly well. If the three circles intersect, the trilateration finds the target area and the program creates a GraphicsPath to draw that area. There are a lot of other details that this post doesn’t cover, such as allowing the user to select the three circles, and drawing various circles, arcs, and points of intersection. See the earlier post and download this example program to see additional details.


Download Example   Follow me on Twitter   RSS feed   Donate




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

Perform trilateration in C#

[trilateration]

This post explains how a C# program can use trilateration to locate a point that is known distances from three other points.

Trilateration is somewhat similar to triangulation, so following two sections begin by explaining what triangulation and trilateration are.

Triangulation

In triangulation, you know the directions from two or more points toward an unknown location. You draw rays leaving the known points in their directions, and the place where those rays intersect gives you the unknown location.

[trilateration]

For example, suppose you have a directional antenna. You go to point A in the picture on the right, and it tells you that the transmitter (point T) is in the direction of the red arrow. You then move to another point, this time B, and the antenna tells you that the transmitter is in the direction of the green arrow. The place where the red and green arrows intersect is the (approximate) location of the transmitter.

You can take more than two readings if you like. If you do, the new arrows may not all intersect at exactly the same point, but they should give you an area where the transmitter is likely to be.

This technique is called triangulation because you’re using a triangle (defined by the points A, B, and C) to location one of the points.

Trilateration

In trilateration you use distances instead of angles to find an unknown location.

[trilateration]

For example suppose you know that a target point T is some distance Ra away from point A. In that case you know that T lies on a circle with radius Ra centered at point A.

If you also know that the target is distance Rb away from point B, then it also lies on a circle with radius Rb centered at point B. Ideally those circles should intersect at one or two places. If they intersect at a single point, then the target should be at that point. If they intersect at two points, then the target lies at one of those points and you need a third measurement to figure out which.

If you have a third point and distance, then it defines a third circle. Ideally the three circles intersect at a single point, and that it where the target lies.

The circles may not intersect at a single point. In that case they define a triangular area (where the sides of the triangle are actually arcs of the circles) and the target should be somewhere in that area.

This technique is called trilateration because it involves three lengths, in this example the segments AT, BT, and CT.

The Algorithm

To find the area where the target should be, find the points where each pair of circles intersect. Then for each pair of circles, find the point of intersection that is closest to the center of the third circle. That point of intersection is part of the triangle that defines the target area.

If you want a specific point near the target, you can average the triangles’ vertex coordinates to find the triangle’s centroid.

The Code

The following Trilaterate method finds the triangle defined by three intersecting circles.

// Trilaterate.
// Throw an exception if there is a problem.
private PointF[] Trilaterate(RectangleF circle1,
    RectangleF circle2, RectangleF circle3)
{
    // Convert the circles from bounding rectangles
    // to centers and radii.
    float cx1 = circle1.X + circle1.Width / 2f;
    float cy1 = circle1.Y + circle1.Height / 2f;
    float cx2 = circle2.X + circle2.Width / 2f;
    float cy2 = circle2.Y + circle2.Height / 2f;
    float cx3 = circle3.X + circle3.Width / 2f;
    float cy3 = circle3.Y + circle3.Height / 2f;
    float r1 = circle1.Width / 2f;
    float r2 = circle2.Width / 2f;
    float r3 = circle3.Width / 2f;

    // Find the points of intersection.
    PointF
        intersection12a, intersection12b,
        intersection23a, intersection23b,
        intersection31a, intersection31b;
    if (FindCircleCircleIntersections(
            cx1, cy1, r1, cx2, cy2, r2,
            out intersection12a, out intersection12b) == 0)
        throw new Exception("circle1 and circle2 do not intersect.");
    if (FindCircleCircleIntersections(
            cx2, cy2, r2, cx3, cy3, r3,
            out intersection23a, out intersection23b) == 0)
        throw new Exception("circle2 and circle3 do not intersect.");
    if (FindCircleCircleIntersections(
            cx3, cy3, r3, cx1, cy1, r1,
            out intersection31a, out intersection31b) == 0)
        throw new Exception("circle3 and circle1 do not intersect.");

    // Find the points that make up the target area.
    PointF[] triangle = new PointF[3];
    PointF center1 = new PointF(cx1, cy1);
    PointF center2 = new PointF(cx2, cy2);
    PointF center3 = new PointF(cx3, cy3);
    if (Distance(intersection12a, center3) <
            Distance(intersection12b, center3))
        triangle[0] = intersection12a;
    else
        triangle[0] = intersection12b;
    if (Distance(intersection23a, center1) <
            Distance(intersection23b, center1))
        triangle[1] = intersection23a;
    else
        triangle[1] = intersection23b;
    if (Distance(intersection31a, center2) <
            Distance(intersection31b, center2))
        triangle[2] = intersection31a;
    else
        triangle[2] = intersection31b;

    return triangle;
}

The method takes as parameters three RectangleF structures that define the three triangles. The code first finds the centers and radii of those circles.

It then calls the FindCircleCircleIntersections method to see where the circles intersect each other. (You can learn more about that method in my earlier post Determine where two circles intersect in C#.)

For each pair of circles, the code determines which of the pair’s points of intersection is closest to the center of the third circle and adds that point to the triangles list.

The following code shows how the program calculates the triangle’s centroid.

// Return the triangle's centroid.
private PointF FindTriangleCentroid(PointF p1, PointF p2, PointF p3)
{
    return new PointF(
        (p1.X + p2.X + p3.X) / 3f,
        (p1.Y + p2.Y + p3.Y) / 3f);
}

This method simply averages the coordinates of the triangle’s vertices.

Conclusion

This method works in a “normal” situation, but there are several odd situations where it won’t work. For example, if the three circles do not all intersect each other, then you can’t find three points of intersection to define the target area and the method does not produce a result. In that case you may be able to gradually increase the circles’ radii until they do intersect and still get a meaningful target area.

[trilateration]

This algorithm also doesn’t produce a good result if the triangles’ centers lie roughly along a line, as shown in the picture on the right. In that case, the intersections define two areas where the target point may lie.

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


Download Example   Follow me on Twitter   RSS feed   Donate




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

Draw many circles that intersect two points in C#

[circles]

As I mentioned in my earlier post Connect two points with elliptical arcs in C#, an infinite number of circles (or ellipses) can pass through two points. This example draws some of them to produce an interesting pattern.

This example only draws one kind of the circles that intersect two points. These circles have centers that lie along the perpendicular bisector of the line connecting the two points.

The following section explains the algorithm for finding these circles. The section after that shows the example program’s circle-finding code.

The Algorithm

[circles]
The picture on the right shows the geometry of the situation.

In this picture, we have selected the two points A and B. To find a circle passing through the two points, follow these steps.

  1. Find the dashed green segment connecting points A and B.
  2. Find the midpoint M of the dashed green segment.
  3. Find a perpendicular bisector (the dashed blue segment) of the green segment passing through point M.
  4. Pick any point C on the perpendicular bisector. This is the center of the circle.
  5. Calculate the distance from point C to point A to get the radius of the circle.

(If you’re particularly mathy, note that there are not only an infinite number of such circles, but there are uncountably many such circles. You can use any point on the blue dashed line as the circle’s center and there are uncountably many points on a line. If you don’t know what any of that means, don’t worry about it.)

The Code

The following FindCircles method returns a list of RectangleF structures that define circles that intersect two given points.

// Find circles centered on a line perpendicular to the segment
// between the two points and that intersect those points.
private List<RectangleF> FindCircles(
    PointF point1, PointF point2, int num_circles)
{
    // Get a scaled vector between the two points.
    float dx = point2.X - point1.X;
    float dy = point2.Y - point1.Y;
    float length = Distance(point1, point2);
    const float scale = 10;
    dx *= scale / length;
    dy *= scale / length;

    // Get the perpendicular vector.
    float p1x = -dy;
    float p1y = dx;
    float p2x = dy;
    float p2y = -dx;

    // Find the center point.
    float cx = (point1.X + point2.X) / 2f;
    float cy = (point1.Y + point2.Y) / 2f;

    // Generate circles.
    List<RectangleF> rects = new List<RectangleF>();
    for (int i = 0; i < num_circles; i++)
    {
        float new_cx = cx + i * p1x;
        float new_cy = cy + i * p1y;
        float radius = Distance(new PointF(new_cx, new_cy), point1);
        rects.Add(new RectangleF(
            new_cx - radius, new_cy - radius,
            2 * radius, 2 * radius));
    }
    return rects;
}

This method simply follows the algorithm described earlier. First it subtracts the two points’ X and Y coordinates to get a vector <dx, dy> pointing from point2 to point1. It divides dx and dy by the length of the vector to get a vector with length 1.

For any vector <dx, dy>, the two vectors <dy, -dx> and <-dy, dx> are perpendicular to it. The method calculates those two vectors and saves them as <p1x, p1y> and <p2x, p2y>. (Although the program only uses the vector <p1x, p1y>.)

The method then averages the coordinates of points point1 and point2 to find the midpoint M = (cx, cy).

The code then loops through the desired number of circles. For each circle the loop adds the vector <p1x, p1y> times the circle number to the center point M to find the center of this circle. The program then calls the Distance helper method to find the distance from the new center to point1 and uses it as the circle’s radius. The method uses the new circle’s center point and radius to define its bounding rectangle and adds it to the rects list.

After it has found all of the circles, the method returns the rects list.

Conclusion

That’s the only really interesting part of the program. Download the example to see the rest.

If you like, try making the program find another set of circles by using the other perpendicular vector <p2x, p2y>. See if you can figure out what those circles will look like first. Then try drawing them in green.


Download Example   Follow me on Twitter   RSS feed   Donate




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

Connect two points with elliptical arcs in C#

[arcs]

As I mentioned in my earlier post Connect two points with arcs of midpoint circles in C#, two points alone cannot uniquely define a circle. An infinite number of circles (or ellipses) can pass through two points and therefore they can be connected by an infinite number of arcs. If you add extra information, however, two points can uniquely define a circle and hence arcs connecting the points.

The previous example added the information that the circle’s center should be at the midpoint between the two points. This example takes a different approach. It creates two ellipses with sides that have the two points as midpoints, as shown in the picture at the top of the post. This isn’t too hard. It’s mostly a matter of examining the arrangement of the two points.

Finding Arcs

The following FindArcs method finds the two arcs that connect the points.

// Find 90 degree arcs connecting the two points.
private void FindArcs(PointF point1, PointF point2,
    out RectangleF rect1, out RectangleF rect2,
    out float start_angle1, out float start_angle2,
    out float sweep_angle1, out float sweep_angle2)
{
    // Find the rectangles' dimensions.
    float x_radius = Math.Abs(point1.X - point2.X);
    float y_radius = Math.Abs(point1.Y - point2.Y);

    // If the points have the same X or Y coordinate,
    // use midpoint circular arcs.
    if ((x_radius == 0) || (y_radius == 0))
    {
        FindMidpointArcs(point1, point2,
            out rect1, out rect2,
            out start_angle1, out start_angle2,
            out sweep_angle1, out sweep_angle2);
        return;
    }

    // Make point1 be on the left.
    if (point2.X < point1.X)
    {
        // Swap them.
        PointF temp = point1;
        point1 = point2;
        point2 = temp;
    }

    // See whether point1 is above or below point2.
    if (point1.Y < point2.Y)
    {
        // point1 is above point2.
        rect1 = new RectangleF(
            point1.X - x_radius,
            point1.Y,
            2 * x_radius,
            2 * y_radius);
        rect2 = new RectangleF(
            point1.X,
            point1.Y - y_radius,
            2 * x_radius,
            2 * y_radius);
        start_angle1 = -90;
        start_angle2 = 90;
    }
    else
    {
        // point1 is below point2.
        rect1 = new RectangleF(
            point1.X - x_radius,
            point1.Y - 2 * y_radius,
            2 * x_radius,
            2 * y_radius);
        rect2 = new RectangleF(
            point1.X,
            point1.Y - y_radius,
            2 * x_radius,
            2 * y_radius);
        start_angle1 = 0;
        start_angle2 = 180;
    }
    sweep_angle1 = 90;
    sweep_angle2 = 90;
}

The method first gets the horizontal and vertical distances between the two points. Those will become the ellipses’ half axes lengths. (See the picture at the top of the post again to see how those values make sense.)

If either the X or Y radius is zero, then the points have the same X or Y coordinate. In that case you cannot make ellipses as shown in the picture to provide arcs to connect the points. We know that there are an infinite number of circles that touch the points, however, so wee can pick one. For this example I decided to use the FindMidpointArcs method used by the previous example to make arcs of a circle centered at the points’ midpoint. See the previous example for details.

If the X and Y radii are not zero, the method switches point1 and point2 if necessary so point1 has the smaller X coordinate.

Now there are two cases.

Case 1: Point1 Lies Above Point2

In the first case, point1 has a smaller Y coordinate than point2. That situation is shown in the picture at the top of the post. In that case, the code uses geometry of the situation to construct the rectangles defining the ellipses.

In the picture at the top of the post, rect1 defines the red ellipse. The red arc starts at -90 degrees (at the top of the red ellipse) and sweeps clockwise for 90 degrees.

The second rectangle rect2 defines the green ellipse. The green arc starts at 90 degrees (at the bottom of the green ellipse) and also sweeps clockwise for 90 degrees.

Case 2: Point1 Lies Below Point2

[arcs]

In the second case, point1 has a larger Y coordinate than point2. That situation is shown in the picture on the right. The method again uses geometry of the situation to construct the rectangles defining the ellipses.

The rectangle rect1 again defines the red ellipse. This time the red arc starts at 0 degrees (at the right side of the red ellipse) and sweeps clockwise for 90 degrees.

The second rectangle rect2 defines the green ellipse. The green arc starts at 180 degrees (at the left side of the green ellipse) and also sweeps clockwise for 90 degrees.

The method’s code finishes by setting both of the sweep angles to 90 degrees. Those angles are 90 degrees in all cases, except when the points’ X or Y coordinates are the same. (In those cases the program uses circles centered at the points’ midpoint, and the sweep angles are 180.)

Conclusion

The example’s code that draws the bounding rectangles, ellipses, and arcs is similar to the code used by the previous example. See that example and download the code for this one to see additional details.


Download Example   Follow me on Twitter   RSS feed   Donate




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

Connect two points with arcs of midpoint circles in C#

[arcs]

Two points alone cannot uniquely define a circle because an infinite number of circles can pass through two points and therefore they can be connected by an infinite number of arcs. If you add extra information, however, two points can uniquely define a circle and hence arcs connecting the points. This example finds the circle that intersects two points and that has a center at the points’ midpoint.

The example performs two main tasks: letting the user pick the two points and finding the arcs.

Picking Points

The following code shows how the program lets the user pick two points.

private List<PointF> Points = new List<PointF>();

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

The program stores the points in the Points list. When the user clicks on the program’s PictureBox, the MouseClick event handler sees how many points are already in the list. If the list is full, the program creates a new list.

The event handler then saves the new point into the list and refreshes the PictureBox.

The program uses the following Paint event handler to draw the points and their connecting arcs.

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

    // Find the arcs.
    if (Points.Count == 2)
    {
        // Find the arcs' bounding rectangles.
        RectangleF rect1, rect2;
        float start_angle1, start_angle2, sweep_angle1, sweep_angle2;
        FindMidpointArcs(Points[0], Points[1],
            out rect1, out rect2,
            out start_angle1, out start_angle2,
            out sweep_angle1, out sweep_angle2);

        // Draw the bounding rectangles.
        using (Pen pen = new Pen(Color.Red, 0))
        {
            // Draw the bounding rectangles.
            pen.DashPattern = new float[] { 1, 2 };
            e.Graphics.DrawRectangle(pen, rect1);
            pen.Color = Color.Green;
            e.Graphics.DrawRectangle(pen, rect2);

            // Draw the bounding ellipses.
            pen.DashPattern = new float[] { 5, 5 };
            e.Graphics.DrawEllipse(pen, rect1);
            pen.Color = Color.Green;
            e.Graphics.DrawEllipse(pen, rect2);
        }

        // Draw the arcs.
        using (Pen pen = new Pen(Color.Red, 2))
        {
            e.Graphics.DrawArc(pen, rect1, start_angle1, sweep_angle1);
            pen.Color = Color.Green;
            e.Graphics.DrawArc(pen, rect2, start_angle2, sweep_angle2);
        }
    }

    // Draw the points.
    foreach (PointF point in Points)
        DrawPoint(e.Graphics, Brushes.Green, point);
}

The Paint event handler is relatively straightforward. If the Points list contains two points, the code calls the FindMidpointArcs method to get the arc data. It then draws the arcs’ bounding rectangles with dotted lines, the ellipses that contain the arcs with dashed lines, and finally the arcs with solid lines.

After it has drawn the arcs, the code loops through any points in the Points list and draws them.

Download the example program for additional details.

Finding the Arcs

Finding the circle that intersects the points is easy. First find the midpoint between the two points. The distance from that midpoint to either of the original points gives the circle’s radius. Alternatively you can calculate the distance between the two original points and divide by two.

You can then use the arctangent of the angle from the midpoint to the original points to find the angles.

The example program uses the following FindMidpointArcs method to find the arcs connecting the points.

// Find the arcs connecting two points
private void FindMidpointArcs(PointF point0, PointF point1,
    out RectangleF rect1, out RectangleF rect2,
    out float start_angle1, out float start_angle2,
    out float sweep_angle1, out float sweep_angle2)
{
    // Find the midpoint.
    float cx = (point0.X + point1.X) / 2f;
    float cy = (point0.Y + point1.Y) / 2f;

    // Find the radius.
    float radius = (float)(Distance(point0, point1) / 2.0);

    // Create the rectangles.
    rect1 = new RectangleF(
        cx - radius, cy - radius,
        2 * radius, 2 * radius);
    rect2 = rect1;

    // Find the start angles.
    start_angle1 = (float)(180 / Math.PI * Math.Atan2(
        point1.Y - point0.Y,
        point1.X - point0.X));
    start_angle2 = (start_angle1 + 180) % 360;
    sweep_angle1 = 180;
    sweep_angle2 = 180;
}

This method returns information needed to draw arcs connecting two points. To draw an arc, the Graphics class’s DrawArc method uses a rectangle bounding the ellipse that contains the arc, a start angle, and a sweep angle. The method returns those values through output parameters.

This method first averages the points’ X and Y coordinates to find the midpoint between the two points. To find the circle’s radius, the code calculates the distance between the two original points and divides by two. (The Distance method simply calculates the distance between two points. It’s straightforward so it isn’t shown here.)

The code then uses the midpoint and radius to define the rectangle that bounds the midpoint circle. The two arcs that connect the points lie on the same circle, so the two bounding rectangles are the same.

The method then uses Math.Atan2 to find the angle from the circle’s center to the first point. The Math.Atan2 method returns the angle in radians but the Graphics.DrawArc method uses degrees, so the code converts the result into degrees.

To calculate the second angle, the code adds 180 degrees and takes the result modulus 360 so the final angle lies between 0 and 360. (It actually lies between

The last piece of information that the Graphics.DrawArc method needs to draw an arc is the arc’s sweep angle. For midpoint circles, that angle is always 180 degrees, so the method sets sweep_angle1 and sweep_angle2 equal to 180.

Conclusion

Although you cannot uniquely define arcs connecting two points, you can define arcs that lie on a circle with center at the points’ midpoint. In my next post I’ll show another way to define arcs that connect two points. Meanwhile download the example to see additional details and to experiment with it.


Download Example   Follow me on Twitter   RSS feed   Donate




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

Improve the program that displays COVID-19 data for US states in C#


[COVID-19]

This post describes two improvements to the earlier example that displays COVID-19 data for US states. The first change is a basic software engineering improvement. The second displays daily changes in COVID-19 case, hospitalization, and death numbers.

Software Engineering Notes

While I was working on the second change to this program, I noticed that some of the data made no sense. The program shows that some states were getting tens of thousands of new COVID-19 deaths in a single day. That was obviously wrong. After a little digging, I discovered that the website where the program was downloading its data had changed the data’s format. It had inserted an extra column in the middle of the CSV data so the columns that came after that one were in the wrong positions.

This raises two important software engineering issues: program lifespan and magic numbers.

Program Lifespan

Never assume that even the most trivial program won’t be in use much later than you expect. In this case, I intended my original COVID-19 posts to be simple programs that you could use to examine the available data. I didn’t think they were very important programs so I was a bit lazy about things like using magic numbers. I knew which columns contained the data, so I just plugged the column numbers into the program.

If you think this is an isolated problem, you’re most definitely wrong. Remember the whole Y2K panic? That was caused because engineers (they didn’t have programmers back then) back in the 60s assumed that there software wouldn’t still be running 40 years later. I’ve also written quick throw-away programs that were used years after I thought they would be discarded.

If a program does something useful, people will continue to use it. They could write a newer version, but that would take work so why bother?

The point of this is, don’t be lazy. If you expect a program to be useful for only a short period or only for your use, you don’t need to give the full assortment or error handling, logging, printing, reporting, and other features that you would include in a commercial application, but don’t be lazy. Take a little extra time to make the code as robust as you reasonably can.

Magic Numbers

In the original example, used the following constants to indicate the columns that contain different pieces of COVID-19 data.

const int colDate = 1;
const int colState = 2;
const int colPositive = 3;
const int colNegative = 4;
const int colPending = 5;
const int colHospitalizedNow = 6;
const int colHospitalizedTotal = 7;
const int colIcuNow = 8;
const int colIcuTotal = 9;
const int colVentNow = 10;
const int colVentTotal = 11;
const int colRecovered = 12;
const int colDeaths = 17;

Later the code can refer to a column as in colNegative rather than 4. That’s an excellent first step, but I should have taken things one step farther. Rather than hard-coding the column numbers into the program, I should have made the program find the column numbers at runtime.

This brings up another important piece of software engineering advice. If you do not have total control over the sources of your data you cannot be sure that the data format won’t change over time. In this example, there was no reason to think that the data format would change. Why should it? Well apparently the data provider thought there was a good reason.

Along with the realization that the data can change is the secondary idea that there’s no reason why it cannot change again. Fool me once, shame on you. Fool me twice, shame on me!

The new program uses the following FindColumn method to find the columns for the various pieces of COVID-19 data.

// See which column contains the indicated column header.
private int FindColumn(object[,] fields, string header)
{
    for (int i = fields.GetLowerBound(1);
        i <= fields.GetUpperBound(1); i++)
    {
        if (fields[1, i].ToString().ToLower() == header.ToLower())
            return i;
    }
    throw new Exception("Cannot find column " + header);
}

This method loops through the column headers in the CSV file’s first row until it finds the desired column header. It then returns the column number.

Now the program can handle it if the data provider inserts or removes columns.

Note that it would still have problems if the provider renames one of the columns that the program uses. Hopefully that won’t happen. I think that’s a less common change than adding or removing a column.

Notice also that the code now throws an exception if it cannot find the desired column. The earlier version of the program used a hard-coded column number so it didn’t realize that it was using the wrong data. Now if there is a problem, the program will immediately make it obvious so I can fix it.

I want to make one final note here before moving on. For similar reasons, it is generally better if you use keys, column names, and other identifying names rather than indices. For example, when you fetch data from a database, you can index the columns by name instead of number. Then if the columns are reordered, the program still works. If a column that you use is renamed, the program will fail rather than using the wrong data and producing incorrect results that may be hard to detect.

Daily Changes

The previous versions of this program let you visualize COVID-19 data. For example, the following picture shows the previous version showing COVID-19 death data for the state of Colorado.


[COVID-19]

What we want to see is a flattening of this curve. That would indicate that the number of deaths is leveling off, hopefully eventually becoming horizontal indicating no new COVID-19 deaths. But it’s a bit hard to see how effectively the curve is flattening.

If we look at the curve’s slope, that may make it easier to see if the number of cases is declining. You could calculate that value by subtracting one day’s number from the previous day’s value, but the data already includes daily increases in positive tests, hospitalizations, and deaths, so displaying those values is relatively easy. I just modified the program to display the new columns much as it displays the other columns. See my previous COVID-19 posts and download the example to see the details.

If you look again at the picture at the top of this post, you’ll see how the death data has changed daily in Colorado. You can see that the deaths reached a peak on April 25 and have been more or less decreasing since then.

It’s a bit easier to see the general shape of the data if you connect the peaks. It’s a bit easier to visualize if you resize the program so it’s relatively short and wide, although then it wouldn’t fit on the web page very well. (I did slip in one other useful change to the code. If you resize the form, the program redraws the currently selected data. In the previous versions you needed to change your selections to make the program redraw.)

Conclusion

The main software engineering lesson to be learned from this example is, don’t be lazy. Make your programs use named columns, keys, or other identifiers instead of indexes when you can.

This example also lets you see the daily increase in positive tests, hospitalizations, and deaths from COVID-19 in the United States.

I haven’t been able to find an explanation or even a mention of the general spikiness of the data. In Colorado, for example, the death data seems to have a spike every 3 days or so. I suspect this is a reporting artifact.

The following picture shows the combined values for the whole country.


[COVID-19]

In this picture the peaks are remarkably close to once per week, for some reason on Thursdays. This is almost surely an artifact of the way the data is gathered and reported.


Download Example   Follow me on Twitter   RSS feed   Donate




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

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