Algorithm for creating rounded corners in a polygon

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.

  • UIView with rounded corners and drop shadow?
  • Using UIBezierPath:byRoundingCorners: with Swift 2 and Swift 3
  • Iphone Custom UITabBarItem without rounded edges
  • How do I create a round cornered UILabel on the iPhone?
  • Rounded corners in a UITableView (iOS7)
  • Setting Corner Radius on UIImageView not working
  • Somebody knows any good algorithm for doing that?
    I’m working in C# but the code has to be independent from any .NET libraries.

    Example

    5 Solutions Collect From Internet About “Algorithm for creating rounded corners in a polygon”

    Some geometry with Paint:

    0. You have a corner:
    Corner

    1. You know the coordinates of corner points, let it be P1, P2 and P:
    Points of corner

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

    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

    segment = PC1 = PC2 = radius / |tan(angle / 2)|

    4. Here you need to check the length of segment and the minimal length from PP1 and PP2:
    Minimal length
    Length of PP1:

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

    Length of PP2:

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

    If segment > PP1 or segment > PP2 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 C1X and C1Y by the proportion between the coordinates of the vector, length of vector and the length of the segment:
    Coordinates of PC1

    Proportion:

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

    So:

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

    The same for C1Y:

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

    7. Get the C2X and C2Y 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 PC1 and PC2 to find the centre of circle by the same way by proportion:
    Addition of vectors

    (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:
    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:
    Sweep angle

    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:
    The result

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

    You are looking for an arc tangent to two connected line segments, of a given radius, given by some sequential array of points. The algorithm to find this arc is as follows:

    1. For each segment, construct a normal vector.

      1. If you are working in 2d, you can just subtract the two endpoints to get a tangent vector (X, Y). In that case, normal vectors will be plus or minus (-Y, X). Normalize the normal vector to length one. Finally, choose the direction with a positive dot product with the tangent vector of the next segment. (See update below).

      2. If you are working in 3d not 2d, to get the normal, cross the tangent vectors of the two segments at the vertex you wish to round to get a perpendicular vector to the plane of the lines. If the perpendicular has length zero, the segments are parallel and no round can be required. Otherwise, normalize it, then cross the perpendicular with the tangent to get the normal.)

    2. Using the normal vectors, offset each line segment towards the interior of the polygon by your desired radius. To offset a segment, offset its endpoints using the normal vector N you just computed, like so: P’ = P + r * N (a linear combination).

    3. Intersect the two offset lines to find the center. (This works because a radius vector of a circle is always perpendicular to its tangent.)

    4. To find the point at which the circle intersects each segment, offset the circle center backwards to each original segment. These will be the endpoints of your arc.

    5. Make sure the arc endpoints are inside each segment, otherwise you will be creating a self-intersecting polygon.

    6. Create an arc through both endpoints with center & radius you determined.

    I don’t have any proper drafting software at hand, but this diagram sort of shows the idea:

    enter image description here

    At this point you will need either to introduce classes to represent a figure consisting of line and arc segments, or polygonize the arc to an appropriate accuracy and add all the segments to the polygon.

    Update: I have updated the image, labeling the points P1, P2, and P3, and normal vectors Norm12 and Norm23. The normalized normals are unique only up to flipping direction, and you should choose the flips as follows:

    • The dot product of Norm12 with (P3 – P2) must be positive. If it is negative, multiple Norm12 by -1.0. If it is zero, the points are collinear and no rounded corner need be created. This is because you want to offset towards P3.

    • The dot product of Norm23 with (P1 – P2) must also be positive since you are offsetting towards P1.

    Objective-C adaptation of nempoBu4 answer:

    typedef enum {
        path_move_to,
        path_line_to
    } Path_command;
    
    
    
    
    
    static inline CGFloat sqr (CGFloat a)
    {
        return a * a;
    }
    
    
    
    
    
    static inline CGFloat positive_angle (CGFloat angle)
    {
        return angle < 0 ? angle + 2 * (CGFloat) M_PI : angle;
    }
    
    
    
    
    
    static void add_corner (UIBezierPath* path, CGPoint p1, CGPoint p, CGPoint p2, CGFloat radius, Path_command first_add)
    {
        // 2
        CGFloat angle = positive_angle (atan2f (p.y - p1.y, p.x - p1.x) - atan2f (p.y - p2.y, p.x - p2.x));
    
        // 3
        CGFloat segment = radius / fabsf (tanf (angle / 2));
        CGFloat p_c1 = segment;
        CGFloat p_c2 = segment;
    
        // 4
        CGFloat p_p1 = sqrtf (sqr (p.x - p1.x) + sqr (p.y - p1.y));
        CGFloat p_p2 = sqrtf (sqr (p.x - p2.x) + sqr (p.y - p2.y));
        CGFloat min = MIN(p_p1, p_p2);
        if (segment > min) {
            segment = min;
            radius = segment * fabsf (tanf (angle / 2));
        }
    
        // 5
        CGFloat p_o = sqrtf (sqr (radius) + sqr (segment));
    
        // 6
        CGPoint c1;
        c1.x = (CGFloat) (p.x - (p.x - p1.x) * p_c1 / p_p1);
        c1.y = (CGFloat) (p.y - (p.y - p1.y) * p_c1 / p_p1);
    
        //  7
        CGPoint c2;
        c2.x = (CGFloat) (p.x - (p.x - p2.x) * p_c2 / p_p2);
        c2.y = (CGFloat) (p.y - (p.y - p2.y) * p_c2 / p_p2);
    
        // 8
        CGFloat dx = p.x * 2 - c1.x - c2.x;
        CGFloat dy = p.y * 2 - c1.y - c2.y;
    
        CGFloat p_c = sqrtf (sqr (dx) + sqr (dy));
    
        CGPoint o;
        o.x = p.x - dx * p_o / p_c;
        o.y = p.y - dy * p_o / p_c;
    
        // 9
        CGFloat start_angle = positive_angle (atan2f ((c1.y - o.y), (c1.x - o.x)));
        CGFloat end_angle = positive_angle (atan2f ((c2.y - o.y), (c2.x - o.x)));
    
    
        if (first_add == path_move_to) {
            [path moveToPoint: c1];
        }
        else {
            [path addLineToPoint: c1];
        }
        [path addArcWithCenter: o radius: radius startAngle: start_angle endAngle: end_angle clockwise: angle < M_PI];
    }
    
    
    
    
    
    UIBezierPath* path_with_rounded_corners (NSArray<NSValue*>* points, CGFloat corner_radius)
    {
        UIBezierPath* path = [UIBezierPath bezierPath];
        NSUInteger count = points.count;
        for (NSUInteger i = 0; i < count; ++i) {
            CGPoint prev = points[i > 0 ? i - 1 : count - 1].CGPointValue;
            CGPoint p = points[i].CGPointValue;
            CGPoint next = points[i + 1 < count ? i + 1 : 0].CGPointValue;
            add_corner (path, prev, p, next, corner_radius, i == 0 ? path_move_to : path_line_to);
        }
        [path closePath];
        return path;
    }
    

    Here is a way using some geometry :-

    1. the two lines are tangent to circle inscribed
    2. The normal to the tangent meet at centre of the circle.
    3. Let angle between lines be X
    4. Angle subtended at centre of the circle will be K = 360-90*2-X = 180-X
    5. Lets decide the two point of tangents as (x1,y) and (x2,y)
    6. The chord joining the points has length l = (x2-x1)
    7. Inside the circle, the chord and two normals of length r (radius) form isosceles triangle
    8. The pendicular divide the traingle in to equal halved right angled triangles.
    9. One of angle is K/2 and side is l/2
    10. using properties of right angle triangle sin(K/2) = (l/2)/r
    11. r = (l/2)/sin(K/2)
    12. but K = 180-X so r = (l/2)/sin(90-X/2) = (l/2)/cos(X/2)
    13. hence r = (x2-x1)/(2*cos(X/2))
    14. Now simply draw a arc from (x1,y) to (x2,y) using radius r

    Note:-

    The above is explained for only for lines which meet at origin and the Y axis divides the angle between them into half. But it is equally applicable for all corner just need to apply a rotation and translation before applying the above. Moreover you need to select some x values of intersection from where you want to draw the arc . The values should not be too far or close to origin

    Here is my realisation of dbc’s idea on c#:

    /// <summary>
    /// Round polygon corners
    /// </summary>
    /// <param name="points">Vertices array</param>
    /// <param name="radius">Round radius</param>
    /// <returns></returns>
    static public GraphicsPath RoundCorners(PointF[] points, float radius) {
        GraphicsPath retval = new GraphicsPath();
        if (points.Length < 3) {
            throw new ArgumentException();
        }
        rects = new RectangleF[points.Length];
        PointF pt1, pt2;
        //Vectors for polygon sides and normal vectors
        Vector v1, v2, n1 = new Vector(), n2 = new Vector();
        //Rectangle that bounds arc
        SizeF size = new SizeF(2 * radius, 2 * radius);
        //Arc center
        PointF center = new PointF();
    
        for (int i = 0; i < points.Length; i++) {
            pt1 = points[i];//First vertex
            pt2 = points[i == points.Length - 1 ? 0 : i + 1];//Second vertex
            v1 = new Vector(pt2.X, pt2.Y) - new Vector(pt1.X, pt1.Y);//One vector
            pt2 = points[i == 0 ? points.Length - 1 : i - 1];//Third vertex
            v2 = new Vector(pt2.X, pt2.Y) - new Vector(pt1.X, pt1.Y);//Second vector
            //Angle between vectors
            float sweepangle = (float)Vector.AngleBetween(v1, v2);
            //Direction for normal vectors
            if (sweepangle < 0) { 
                n1 = new Vector(v1.Y, -v1.X);
                n2 = new Vector(-v2.Y, v2.X);
            }
            else {
                n1 = new Vector(-v1.Y, v1.X);
                n2 = new Vector(v2.Y, -v2.X);
            }
    
            n1.Normalize(); n2.Normalize();
            n1 *= radius; n2 *= radius;
            /// Points for lines which intersect in the arc center
            PointF pt = points[i];
            pt1 = new PointF((float)(pt.X + n1.X), (float)(pt.Y + n1.Y));
            pt2 = new PointF((float)(pt.X + n2.X), (float)(pt.Y + n2.Y));
            double m1 = v1.Y / v1.X, m2 = v2.Y / v2.X;
            //Arc center
            if (v1.X == 0) {// first line is parallel OY
                center.X = pt1.X;
                center.Y = (float)(m2 * (pt1.X - pt2.X) + pt2.Y);
            }
            else if (v1.Y == 0) {// first line is parallel OX
                center.X = (float)((pt1.Y - pt2.Y) / m2 + pt2.X);
                center.Y = pt1.Y;
            }
            else if (v2.X == 0) {// second line is parallel OY
                center.X = pt2.X;
                center.Y = (float)(m1 * (pt2.X - pt1.X) + pt1.Y);
            }
            else if (v2.Y == 0) {//second line is parallel OX
                center.X = (float)((pt2.Y - pt1.Y) / m1 + pt1.X);
                center.Y = pt2.Y;
            }
            else {
                center.X = (float)((pt2.Y - pt1.Y + m1 * pt1.X - m2 * pt2.X) / (m1 - m2));
                center.Y = (float)(pt1.Y + m1 * (center.X - pt1.X));
            }
            rects[i] = new RectangleF(center.X - 2, center.Y - 2, 4, 4);
            //Tangent points on polygon sides
            n1.Negate(); n2.Negate();
            pt1 = new PointF((float)(center.X + n1.X), (float)(center.Y + n1.Y));
            pt2 = new PointF((float)(center.X + n2.X), (float)(center.Y + n2.Y));
            //Rectangle that bounds tangent arc
            RectangleF rect = new RectangleF(new PointF(center.X - radius, center.Y - radius), size);
            sweepangle = (float)Vector.AngleBetween(n2, n1);
            retval.AddArc(rect, (float)Vector.AngleBetween(new Vector(1, 0), n2), sweepangle);
        }
        retval.CloseAllFigures();
        return retval;
    }