c# - How to calculate rounded corners for a polygon?

Question

I'm looking for an algorithm that allows me to create rounded corners from a polygon.

I have an array of points that represents the polygon (outlined in red) and on output I want an array of points that represents the polygon with rounded corners (outlined in black).

I would also like to have a way to control the radius of each corner.

I tried to use Bézier curves and subdivision but it's not what I'm looking for. Bézier curves and subdivision are smoothing the polygon.

What I want is to only make the corners rounded.

Does somebody know any good algorithm for doing that?

I'm working with C# but the code has to be independent from any .NET libraries.

Answer 1

Some geometry with Paint:

0. You have a corner:


1. You know the coordinates of corner points, let it be P₁, P₂ and P:


2. Now you can get vectors from points and angle between vectors:

angle = atan(P

_Y - P_1Y, P_X - P_1X) - atan(P_Y - P_2Y, P_X - P_2X)

3. Get the length of segment between angular point and the points of intersection with the circle.

segment = PC

₁ = PC₂ = radius / |tan(angle / 2)|

4. Here you need to check the length of segment and the minimal length from PP₁ and PP₂:

Length of PP₁:

PP

₁ = sqrt((P_X - P_1X)² + (P_Y - P_1Y)²)

Length of PP₂:

PP

₂ = sqrt((P_X - P_2X)² + (P_Y - P_2Y)²)

If segment > PP₁ or segment > PP₂ then you need to decrease the radius:

min = Min(PP

₁, PP₂) (for polygon is better to divide this value by 2) segment > min ? segment = min radius = segment * |tan(angle / 2)|

5. Get the length of PO:

PO = sqrt(radius

² + segment²)

6. Get the C_1X and C_1Y by the proportion between the coordinates of the vector, length of vector and the length of the segment:

Proportion:

(P

_X - C_1X) / (P_X - P_1X) = PC₁ / PP₁

So:

C

_1X = P_X - (P_X - P_1X) * PC₁ / PP₁

The same for C_1Y:

C

_1Y = P_Y - (P_Y - P_1Y) * PC₁ / PP₁

7. Get the C_2X and C_2Y by the same way:

C

_2X = P_X - (P_X - P_2X) * PC₂ / PP₂ C_2Y = P_Y - (P_Y - P_2Y) * PC₂ / PP₂

8. Now you can use the addition of vectors PC₁ and PC₂ to find the centre of circle by the same way by proportion:

(P

_X - O_X) / (P_X - C_X) = PO / PC (P_Y - O_Y) / (P_Y - C_Y) = PO / PC

Here:

C

_X = C_1X + C_2X - P_X C_Y = C_1Y + C_2Y - P_Y PC = sqrt((P_X - C_X)² + (P_Y - C_Y)²)

Let:

dx = P

_X - C_X = P_X * 2 - C_1X - C_2X dy = P_Y - C_Y = P_Y * 2 - C_1Y - C_2Y

So:

PC = sqrt(dx

² + dy²) O_X = P_X - dx * PO / PC O_Y = P_Y - dy * PO / PC

9. Here you can draw an arc. For this you need to get start angle and end angle of arc:

Found it here:

startAngle = atan((C

_1Y - O_Y) / (C_1X - O_X)) endAngle = atan((C_2Y - O_Y) / (C_2X - O_X))

10. At last you need to get a sweep angle and make some checks for it:

sweepAngle = endAngle - startAngle

If sweepAngle < 0 then swap startAngle and endAngle, and invert sweepAngle:

sweepAngle < 0 ?    
    sweepAngle = - sweepAngle
    startAngle = endAngle

Check if sweepAngle > 180 degrees:

sweepAngle > 180 ?    
    sweepAngle = 180 - sweepAngle

11. And now you can draw a rounded corner:

Some geometry with c#:

private void DrawRoundedCorner(Graphics graphics, PointF angularPoint, 
                                PointF p1, PointF p2, float radius)
{
    //Vector 1
    double dx1 = angularPoint.X - p1.X;
    double dy1 = angularPoint.Y - p1.Y;

    //Vector 2
    double dx2 = angularPoint.X - p2.X;
    double dy2 = angularPoint.Y - p2.Y;

    //Angle between vector 1 and vector 2 divided by 2
    double angle = (Math.Atan2(dy1, dx1) - Math.Atan2(dy2, dx2)) / 2;

    // The length of segment between angular point and the
    // points of intersection with the circle of a given radius
    double tan = Math.Abs(Math.Tan(angle));
    double segment = radius / tan;

    //Check the segment
    double length1 = GetLength(dx1, dy1);
    double length2 = GetLength(dx2, dy2);

    double length = Math.Min(length1, length2);

    if (segment > length)
    {
        segment = length;
        radius = (float)(length * tan);
    }

    // Points of intersection are calculated by the proportion between 
    // the coordinates of the vector, length of vector and the length of the segment.
    var p1Cross = GetProportionPoint(angularPoint, segment, length1, dx1, dy1);
    var p2Cross = GetProportionPoint(angularPoint, segment, length2, dx2, dy2);

    // Calculation of the coordinates of the circle 
    // center by the addition of angular vectors.
    double dx = angularPoint.X * 2 - p1Cross.X - p2Cross.X;
    double dy = angularPoint.Y * 2 - p1Cross.Y - p2Cross.Y;

    double L = GetLength(dx, dy);
    double d = GetLength(segment, radius);

    var circlePoint = GetProportionPoint(angularPoint, d, L, dx, dy);

    //StartAngle and EndAngle of arc
    var startAngle = Math.Atan2(p1Cross.Y - circlePoint.Y, p1Cross.X - circlePoint.X);
    var endAngle = Math.Atan2(p2Cross.Y - circlePoint.Y, p2Cross.X - circlePoint.X);

    //Sweep angle
    var sweepAngle = endAngle - startAngle;

    //Some additional checks
    if (sweepAngle < 0)
    {
        startAngle = endAngle;
        sweepAngle = -sweepAngle;
    }

    if (sweepAngle > Math.PI)
        sweepAngle = Math.PI - sweepAngle;

    //Draw result using graphics
    var pen = new Pen(Color.Black);

    graphics.Clear(Color.White);
    graphics.SmoothingMode = SmoothingMode.AntiAlias;

    graphics.DrawLine(pen, p1, p1Cross);
    graphics.DrawLine(pen, p2, p2Cross);

    var left = circlePoint.X - radius;
    var top = circlePoint.Y - radius;
    var diameter = 2 * radius;
    var degreeFactor = 180 / Math.PI;

    graphics.DrawArc(pen, left, top, diameter, diameter, 
                     (float)(startAngle * degreeFactor), 
                     (float)(sweepAngle * degreeFactor));
}

private double GetLength(double dx, double dy)
{
    return Math.Sqrt(dx * dx + dy * dy);
}

private PointF GetProportionPoint(PointF point, double segment, 
                                  double length, double dx, double dy)
{
    double factor = segment / length;

    return new PointF((float)(point.X - dx * factor), 
                      (float)(point.Y - dy * factor));
}

To get points of arc you can use this:

//One point for each degree. But in some cases it will be necessary 
// to use more points. Just change a degreeFactor.
int pointsCount = (int)Math.Abs(sweepAngle * degreeFactor);
int sign = Math.Sign(sweepAngle);

PointF[] points = new PointF[pointsCount];

for (int i = 0; i < pointsCount; ++i)
{
    var pointX = 
       (float)(circlePoint.X  
               + Math.Cos(startAngle + sign * (double)i / degreeFactor)  
               * radius);

    var pointY = 
       (float)(circlePoint.Y 
               + Math.Sin(startAngle + sign * (double)i / degreeFactor) 
               * radius);

    points[i] = new PointF(pointX, pointY);
}