Connect two line segments with a circular arc in C#


[circular arc]

Recently I wanted to make a circular arc that connected two line segments. The .NET DrawCurve method lets you connect points with a smooth curve relatively easily, but the curve is a spline and not a circular arc. (I’ll post examples showing both versions of the program I was making a bit later.) This example explains how you can find a circular arc that connects two line segments.

First suppose the line segments are tangent to some circle as shown in the following picture.


[circular arc]

In this case, you can use some geometry (which I’ll described later) to find the circular arc. Unfortunately if you let the user define the line segments by clicking with the mouse, it’s very likely that the line segments won’t be tangents of any circle. In that case you will need to extend one of the segments as shown in the following picture.


[circular arc]

Shortly I’ll show how you can extend one of the segments to make it tangent to a circle. However, first notice that it is not always possible to extend a segment to a tangent, at least in the way that we want. For example, the following picture shows two line segments that cannot be extended in a simple way so they become tangents of a circle. You can make these segments tangents, but not in the simple way that I want.


[circular arc]

I won’t talk further about these stranger arcs, although you could find them if you want to connect segments with that kind of circular arc.

The following three sections explain:

  • How to extend one of the segments so both segments are tangent to a circle
  • How to find the circle
  • How to find the circular arc
  • The program’s C# code

Extending a Segment

Extend the two line segments until they intersect as shown in the following picture.


[circular arc]

There are infinitely many circles tangent to the two extended line segments. The circle that we want is the one that is tangent at one of the original segments’ end points. That end point will be the one that is closer to the lines’ point of intersection (POI). The other tangent point is the same distance away from the POI, and its line segment must be extended to that point.

Here’s the algorithm for extending one of the line segments until they are both tangent to a circle.

  1. Find the POI between the two extended line segments.
  2. On each segment, find the end point that is closer to the POI.
  3. Of the two closer points, find the one that is closer to the POI. Call that point P1. Let D be the distance from point P1 to the POI.
  4. Find the point on the other extended line segment that is distance D from the POI. Call that point P2.

If the two line segments are parallel, then they do not intersect. You can still find a circular arc to connect the segments, but you’ll need to use a slightly different method, which I won’t cover here. Again, this isn’t the kind of circular arc I need.

Finding the Circle

Now that you have the points P1 and P2, the following picture shows how you can find the circle.


[circular arc]

The two segments are tangent to the circle so lines that are pependicular to those segments at the tangent points will pass through the center of the circle. Make two lines that are perpendicular to points P1 and P2, and find the intersection of those two lines. That is the circle’s center.

Now calculate the distance between the center and either point P1 or P2 to get the circle’s radius.

Together the circle’s center and radius define the circle.

Finding the Circlular Arc

After you know the circle’s center, you can calculate the start angle and sweep angle for the circular arc. (The DrawArc method uses a start angle and sweep angle so that’s what we need to find.)

First, subtract P1s X and Y coordinates from the coordinates of the circle’s center to get the distances dx and dy from the circle’s center to point P1. Now use Math.ATan2(dy, dx) to find the angle from the circle’s center to point P1.

Use similar steps to find the angle to point P2. Finally, subtract the two angles to get the sweep angle for the circular arc.

The circle’s center and radius gives us the bounding rectangle that should contain the circular arc. The start and sweep angles tell where the circular arc should start and how far it should extend. Those are all of the values that we need to draw the circular arc.

C# Code

STOP: Be sure you understand the previous sections before you look at the code. The code just implements the techniques described in the previous discussion, so it will be a lot easier to follow if you understand that discussion.

Saving Points

When you click on the program’s form, the following code springs into action.

private Listlt;PointF> Seg1Points = new List();
private Listlt;PointF> Seg2Points = new List();

// Save a new point.
private void Form1_MouseClick(object sender, MouseEventArgs e)
{
    if (e.Button == MouseButtons.Left)
    {
        if (Seg1Points.Count == 2) Seg1Points = new List();
        Seg1Points.Add(e.Location);
        Refresh();
    }
    else
    {
        if (Seg2Points.Count == 2) Seg2Points = new List();
        Seg2Points.Add(e.Location);
        Refresh();
    }
}

This code adds the clicked point to either the Seg1Points or Seg2Points list, depending on whether you left- or right-click. If the correct list already contains two points, the code replaces it with a new list. It then adds the new point and refreshes to redraw the picture.

Drawing the Picture

The following Paint event handler draws the picture.

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

    // See if both segments are defined.
    if ((Seg1Points.Count == 2) &&
        (Seg2Points.Count == 2))
    {
        // Both segments are defined.
        // Find the arc.
        RectangleF rect;
        float start_angle, sweep_angle;
        PointF s1_far, s1_close, s2_far, s2_close;
        FindArcFromSegments(
            Seg1Points[0], Seg1Points[1],
            Seg2Points[0], Seg2Points[1],
            out rect, out start_angle, out sweep_angle,
            out s1_far, out s1_close, out s2_far, out s2_close);

        using (Pen thick_pen = new Pen(Color.Green, 2))
        {
            // Draw the revised segments.
            e.Graphics.DrawLine(thick_pen, s1_far, s1_close);
            e.Graphics.DrawLine(thick_pen, s2_far, s2_close);

            // Draw the arc.
            thick_pen.Color = Color.Red;
            e.Graphics.DrawArc(thick_pen, rect, start_angle, sweep_angle);

            // Draw the returned points that connect to the arc.
            e.Graphics.FillPoint(Brushes.Red, s1_far, 5);
            e.Graphics.FillPoint(Brushes.Red, s1_close, 5);
            e.Graphics.FillPoint(Brushes.Red, s2_far, 5);
            e.Graphics.FillPoint(Brushes.Red, s2_close, 5);
        }
    }
    else
    {
        // Both segments are not defined.
        using (Pen thick_pen = new Pen(Color.Green, 2))
        {
            // Draw the segments.
            if (Seg1Points.Count == 2)
                e.Graphics.DrawLine(thick_pen,
                    Seg1Points[0], Seg1Points[1]);
            if (Seg2Points.Count == 2)
                e.Graphics.DrawLine(thick_pen,
                    Seg2Points[0], Seg2Points[1]);
        }
    }

    // Draw the user-selected points. This will
    // overwrite all but one of the returned points.
    foreach (PointF point in Seg1Points)
        e.Graphics.FillPoint(Brushes.Green, point, 5);
    foreach (PointF point in Seg2Points)
        e.Graphics.FillPoint(Brushes.Green, point, 5);
}

The code first determines whether both lists contain two points. If they do, then you have fully specified both line segments so the code can connect them with a circular arc.

If both lists contain two points, then the code calls the FindArcFromSegments method to get the circular arc parameters. The code then draws the picture. First it draws the line segments returned by the FindArcFromSegments method. That method sets its s1_far, s1_close, s2_far, and s2_closeparameters to the updated end points of the two segments. Three of those points are points that the user clicked. The fourth is the one labeled P2 in the earlier picture that was moved so its segment was tangent to the circle.

Next the code draws the arc. This piece of code finishes by drawing dots at the revised segments’ end points. Note that the code uses the FillPoint extension method to draw the points. That extension method and a few others are useful but not very complicated or interesting, so I won’t describe them here. Download the example to see how they work.

If the two point lists are not both full, the program draws either of the two line segments that are defined.

The code finishes by drawing any points that were selected by the user. If all four points are defined, then that will draw over three of the four points drawn earlier; all except the one labeled P2 earlier.

FindArcFromSegments

The following FindArcFromSegments method performs the calculations described earlier.

// Find a circular arc connecting the segments.
// Return the arc's parameters. Also return new points
// to define the segments so you can draw
// s1_far -> s1_close -> arc -> s2_close -> s2_far.
// Three os those points will be original segments points.
private void FindArcFromSegments(
    PointF s1p1, PointF s1p2,
    PointF s2p1, PointF s2p2,
    out RectangleF rect,
    out float start_angle, out float sweep_angle,
    out PointF s1_far, out PointF s1_close,
    out PointF s2_far, out PointF s2_close)
{
    // See where the segments intersect.
    PointF poi;
    bool lines_intersect, segments_intersect;
    PointF close1, close2;
    FindIntersection(s1p1, s1p2, s2p1, s2p2,
        out lines_intersect, out segments_intersect,
        out poi, out close1, out close2);

    // See if the lines intersect.
    if (!lines_intersect)
    {
        // The lines are parallel. Find the 180 degree arc.
        throw new NotImplementedException("The segments are parallel.");
    }

    // Find the point on each segment that is closest to the poi.
    float close_dist1, close_dist2, far_dist1, far_dist2;

    // Make s1_close be the closer of the points.
    if (s1p1.Distance(poi) < s1p2.Distance(poi))
    {
        s1_close = s1p1;
        s1_far = s1p2;
        close_dist1 = s1p1.Distance(poi);
        far_dist1 = s1p2.Distance(poi);
    }
    else
    {
        s1_close = s1p2;
        s1_far = s1p1;
        close_dist1 = s1p2.Distance(poi);
        far_dist1 = s1p1.Distance(poi);
    }

    // Make s2_close be the closer of the points.
    if (s2p1.Distance(poi) < s2p2.Distance(poi))
    {
        s2_close = s2p1;
        s2_far = s2p2;
        close_dist2 = s2p1.Distance(poi);
        far_dist2 = s1p2.Distance(poi);
    }
    else
    {
        s2_close = s2p2;
        s2_far = s2p1;
        close_dist2 = s2p2.Distance(poi);
        far_dist2 = s1p1.Distance(poi);
    }

    // See which of the close points is closer to the poi.
    if (close_dist1 < close_dist2)
    {
        // s1_close is closer to the poi than s2_close.
        // Find the point on seg2 that is distance
        // close_dist1 from the poi.
        s2_close = PointAtDistance(poi, s2_far, close_dist1);
        close_dist2 = close_dist1;
    }
    else
    {
        // s2_close is closer to the poi than s1_close.
        // Find the point on seg1 that is distance
        // close_dist2 from the poi.
        s1_close = PointAtDistance(poi, s1_far, close_dist2);
        close_dist1 = close_dist2;
    }

    // Find the arc.
    FindArcFromTangents(
        s1_close, s1_far,
        s2_close, s2_far,
        out rect, out start_angle, out sweep_angle);
}

The code first calls the FindIntersection method to find the point where the lines containing the line segments intersect. You can learn about that method in my post Determine where two lines intersect in C#.

If the lines do not intersect, then the segments are parallel. You can write code to handle that situation if you like. This example just throws an exception.

Next, the method determines for each segment which end point is closer and which is farther from the POI. To do that, the code uses the Distance extension method. (Download the example to see how it works.)

The code then determines which of the segments’ close end points is closest to the POI. The distance from that point to the POI is the value D shown on the earlier pictures. The code moves the other segment’s close point so it is that same distance D from the POI. The code uses the PointAtDistance helper method described shortly to move the point.

Now the points s1_close, s1_far, s2_close, and s2_far define two segments that are tangent to the circle so we can find the arc. The code does that by calling the FindArcFromTangents method that is described in the following section. that method returns the values that this method (FindArcFromSegments) needs to return, so this method is finished.

The following PointAtDistancehelper method returns a point along a segment that is a specified distance away from the segment’s first end point. (The program uses this method to find a point distance D away from the segments’ POI.)

// Find a point on the line p1 --> p2 that
// is distance dist from point p1.
private PointF PointAtDistance(PointF p1, PointF p2, float dist)
{
    float dx = p2.X - p1.X;
    float dy = p2.Y - p1.Y;
    float p1p2_dist = (float)Math.Sqrt(dx * dx + dy * dy);
    return new PointF(
        p1.X + dx / p1p2_dist * dist,
        p1.Y + dy / p1p2_dist * dist);
}

This method calculates the horizontal and vertical distances dx and dy between the segment’s two end points. It divides those distances by the segment’s length and multiples by the desired distance from the first end point. The method adds the result to the first end point’s coordinates and that gives the desired point.

FindArcFromTangents

The following code shows the FindArcFromTangents method.

// Find the arc that connects points s1p2 and s2p2.
private void FindArcFromTangents(
    PointF s1_close, PointF s1_far,
    PointF s2_close, PointF s2_far,
    out RectangleF rect,
    out float start_angle, out float sweep_angle)
{
    // Find the perpendicular lines.
    PointF perp_point1, perp_point2;

    float dx1 = s1_close.X - s1_far.X;
    float dy1 = s1_close.Y - s1_far.Y;
    perp_point1 = new PointF(
        s1_close.X - dy1,
        s1_close.Y + dx1);

    float dx2 = s2_close.X - s2_far.X;
    float dy2 = s2_close.Y - s2_far.Y;
    perp_point2 = new PointF(
        s2_close.X + dy2,
        s2_close.Y - dx2);

    // Find the point of intersection between segments
    // s1_close --> perp_point1 and
    // s2_close --> perp_point2.
    bool lines_intersect, segments_intersect;
    PointF poi, close_p1, close_p2;
    FindIntersection(
        s1_close, perp_point1,
        s2_close, perp_point2,
        out lines_intersect, out segments_intersect,
        out poi, out close_p1, out close_p2);

    // Find the radius.
    float dx = s1_close.X - poi.X;
    float dy = s1_close.Y - poi.Y;
    float radius = (float)Math.Sqrt(dx * dx + dy * dy);

    // Create the rectangle.
    rect = new RectangleF(
        poi.X - radius,
        poi.Y - radius,
        2 * radius, 2 * radius);

    // Find the start, end, and sweep angles.
    start_angle = (float)(Math.Atan2(dy, dx) * 180 / Math.PI);
    dx = s2_close.X - poi.X;
    dy = s2_close.Y - poi.Y;
    float end_angle = (float)(Math.Atan2(dy, dx) * 180 / Math.PI);

    // Make the angle less than 180 degrees.
    sweep_angle = end_angle - start_angle;
    if (sweep_angle > 180)
        sweep_angle = sweep_angle - 360;
    if (sweep_angle < -180)
        sweep_angle = 360 + sweep_angle;
}

The method first finds two line segments that are perpendicular to the original segments at the points P1 and P2 as shown in the earlier pictures. If a segment has X and Y components <dx, dy>, then the two sets of components <dy, -dx> and <-dy, dx> define two perpendicular segments. The code finds the original vectors’ components and switches them to get perpendicular components. It adds those components to the two points P1 and P2 to get the ends of the desired perpendicular segments. For example, the first perpendicular segment starts at point s1_close and ends at point perp_point1.

Next, the method uses the FindIntersection method to see where the two perpendicular lines intersect. That point is the center of the circle.

Now the code finds the distance from the center of the circle to the point P1. that gives the circle’s radius. Now that we know the circle’s center and radius, we can define the bounding rectangle for the circular arc.

The last thing the method needs to do is to calculate the start and sweep angles. It uses Meth.Atan2 to calculate the start angle (for point P1) and the end angle (for point P2). It then sets the sweep angle equal to the difference.

Because we want to use the smaller arc around the circle, the code then checks that the sweep angle is less than 180 degrees. If the angle is greater than 180 degrees, the code resets it to that angle minus 360 to make the arc go the right direction around the circle.

Similarly if the sweep angle is less than -180 degrees, the code resets it to 360 plus the angle, again to make the arc go the right direction around the circle. (try commenting out those if statements and experimenting to see what they do.)

Summary

This program still only draws one kind of circular arc. For example, it doesn’t draw any of the kinds of circular arcs shown in the following picture.


[circular arc]

With some work, you may be able to use the techniques described in this post to find those other kinds of circular arc if you need them some day. Meanwhile, download the example program and give it a try.


Download Example   Follow me on Twitter   RSS feed   Donate




About RodStephens

Rod Stephens is a software consultant and author who has written more than 30 books and 250 magazine articles covering C#, Visual Basic, Visual Basic for Applications, Delphi, and Java.
This entry was posted in drawing, graphics and tagged , , , , , , , , . Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.