Algorithm for creating rounded corners in a polygon

Question

I'm looking for an algorithm that allows me to create rounded corners from a polygon. In Input, I get an array of points that represents the polygon (red line) and in output, an array of points that represents the polygon with rounded corner (black line).

I would also like to have a way to control the radius of each corner. I already tried to use Bezier and Subdivision but it's not what I'm looking for. Bezier and Subdivision are smoothing all the polygon. What I want, it's only make the corners rounded.

Somebody knows any good algorithm for doing that? I'm working in 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(PY - P1Y, PX - P1X) - atan(PY - P2Y, PX - P2X)

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

segment = PC1 = PC2 = 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₁:

PP1 = sqrt((PX - P1X)2 + (PY - P1Y)2)

Length of PP₂:

PP2 = sqrt((PX - P2X)2 + (PY - P2Y)2)

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

min = Min(PP1, PP2) (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(radius2 + segment2)

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:

(PX - C1X) / (PX - P1X) = PC1 / PP1

So:

C1X = PX - (PX - P1X) * PC1 / PP1

The same for C_1Y:

C1Y = PY - (PY - P1Y) * PC1 / PP1

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

C2X = PX - (PX - P2X) * PC2 / PP2
C2Y = PY - (PY - P2Y) * PC2 / PP2

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

(PX - OX) / (PX - CX) = PO / PC
(PY - OY) / (PY - CY) = PO / PC

Here:

CX = C1X + C2X - PX
CY = C1Y + C2Y - PY
PC = sqrt((PX - CX)2 + (PY - CY)2)

Let:

dx = PX - CX = PX * 2 - C1X - C2X
dy = PY - CY = PY * 2 - C1Y - C2Y

So:

PC = sqrt(dx2 + dy2)

OX = PX - dx * PO / PC
OY = PY - 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((C1Y - OY) / (C1X - OX))
endAngle = atan((C2Y - OY) / (C2X - OX))

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);
}