Алгоритм создания закругленных углов в многоугольнике

Я ищу алгоритм, который позволяет мне создавать закругленные углы из многоугольника. В Input я получаю массив точек, представляющий многоугольник (красная линия) и на выходе, массив точек, представляющий многоугольник с закругленным углом (черная линия).

Я также хотел бы иметь возможность контролировать радиус каждого угла. Я уже пытался использовать Bezier и Subdivision, но это не то, что я ищу. Безье и подразделение сглаживают весь многоугольник. То, что я хочу, это только делает углы округлыми.

Кто-нибудь знает какой-нибудь хороший алгоритм для этого? Я работаю на С#, но код должен быть независимым от каких-либо .NET-библиотек.

Ответ 1

Некоторая геометрия с помощью Paint:

0. У вас есть угол:

1. Вы знаете координаты угловых точек, пусть это будет P ₁, P ₂ и P:

2. Теперь вы можете получить векторы от точек и угла между векторами:

angle = atan(P_Y - P_{1_Y}, P_X - P_{1_X}) - atan(P_Y - P_{2_Y}, P_X - P_{2_X})

3. Получите длину сегмента между точкой angular и точками пересечения с кругом.

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

4. Здесь вам нужно проверить длину сегмента и минимальную длину от PP ₁ и PP ₂:

Длина PP ₁:

PP₁ = sqrt((P_X - P_{1_X})² + (P_Y - P_{1_Y})²)

Длина PP ₂:

PP₂ = sqrt((P_X - P_{2_X})² + (P_Y - P_{2_Y})²)

Если сегмент > PP ₁ или сегмент > PP ₂, вам нужно уменьшить радиус:

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

5. Получите длину PO:

PO = sqrt(radius² + segment²)

6. Получите C _{1 _X} и C _{1 _Y} на долю между координатами вектора, длиной вектора и длины сегмента:

Пропорция:

(P_X - C_{1_X}) / (P_X - P_{1_X}) = PC₁ / PP₁

Итак:

C_{1_X} = P_X - (P_X - P_{1_X}) * PC₁ / PP₁

То же самое для C _{1 _Y}:

C_{1_Y} = P_Y - (P_Y - P_{1_Y}) * PC₁ / PP₁

7. Получите C _{2 _X} и C _{2 _Y} тем же способом:

C_{2_X} = P_X - (P_X - P_{2_X}) * PC₂ / PP₂
C_{2_Y} = P_Y - (P_Y - P_{2_Y}) * PC₂ / PP₂

8. Теперь вы можете использовать добавление векторов PC ₁ и PC ₂, чтобы найти центр круга таким же образом по пропорции:

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

Здесь:

C_X = C_{1_X} + C_{2_X} - P_X
C_Y = C_{1_Y} + C_{2_Y} - P_Y
PC = sqrt((P_X - C_X)² + (P_Y - C_Y)²)

Пусть:

dx = P_X - C_X = P_X * 2 - C_{1_X} - C_{2_X}
dy = P_Y - C_Y = P_Y * 2 - C_{1_Y} - C_{2_Y}

Итак:

PC = sqrt(dx² + dy²)

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

9. Здесь вы можете нарисовать дугу. Для этого вам нужно получить начальный угол и угол конца дуги:

Найденный здесь:

startAngle = atan((C_{1_Y} - O_Y) / (C_{1_X} - O_X))
endAngle = atan((C_{2_Y} - O_Y) / (C_{2_X} - O_X))

10. Наконец, вам нужно получить угол развертки и сделать некоторые проверки для него:

sweepAngle = endAngle - startAngle

Если sweepAngle < 0, то swap startAngle и endAngle и инвертировать sweepAngle:

sweepAngle < 0 ?    
    sweepAngle = - sweepAngle
    startAngle = endAngle

Проверьте, если sweepAngle > 180 градусов:

sweepAngle > 180 ?    
    sweepAngle = 180 - sweepAngle

11. И теперь вы можете нарисовать округленный угол:

Некоторая геометрия с С#:

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

Чтобы получить точки дуги, вы можете использовать это:

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

Ответ 2

Вы ищете дугу, касающуюся двух связанных сегментов линии, заданного радиуса, заданного некоторым последовательным массивом точек. Алгоритм для поиска этой дуги выглядит следующим образом:

Для каждого сегмента построим нормальный вектор.
- Если вы работаете в 2d, вы можете просто вычесть две конечные точки, чтобы получить касательный вектор (X, Y). В этом случае нормальные векторы будут равны плюс или минус (-Y, X). Normalize нормальный вектор в длину один. Наконец, выберите направление с положительным точечным произведением с касательным вектором следующего отрезка. (См. Обновление ниже).
- Если вы работаете в 3d not 2d, чтобы получить нормальный, cross, касательные векторы двух сегментов в вершину, которую вы хотите округлить, чтобы получить перпендикулярный вектор к плоскости линий. Если перпендикуляр имеет длину нуль, сегменты параллельны, и раунд не требуется. В противном случае, нормализуйте его, затем переместите перпендикуляр с касательной, чтобы получить нормальную.)
Используя нормальные векторы, смещайте каждый отрезок линии в сторону многоугольника на нужный радиус. Чтобы компенсировать сегмент, смещайте его конечные точки, используя обычный вектор N, который вы просто вычислили, например: P '= P + r * N (линейная комбинация).
Перейдите к двум линиям смещения, чтобы найти центр. (Это работает, потому что радиус-вектор окружности всегда перпендикулярен его касательной.)
Чтобы найти точку, в которой круг пересекает каждый сегмент, смещайте центр круга назад на каждый исходный сегмент. Это будут конечные точки вашей дуги.
Убедитесь, что конечные точки дуги находятся внутри каждого сегмента, иначе вы создадите самопересекающийся многоугольник.
Создайте дугу через обе конечные точки с определенным центром и радиусом.

У меня нет подходящего редакционного программного обеспечения, но эта схема показывает идею:

В этот момент вам нужно либо ввести классы, чтобы представить фигуру, состоящую из сегментов линии и дуги, либо полигонизировать дугу с соответствующей точностью и добавить все сегменты в многоугольник.

Обновление: я обновил изображение, обозначив точки P1, P2 и P3, и нормальные векторы Norm12 и Norm23. Нормализованные нормали уникальны только до направления листания, и вы должны выбрать флипс следующим образом:

dot product нормы 12 с (P3 - P2) должен быть положительным. Если он отрицательный, несколько норм12 на -1.0. Если он равен нулю, точки коллинеарны и не нужно создавать округленный угол. Это связано с тем, что вы хотите компенсировать P3.
Точечное произведение Norm23 с (P1 - P2) также должно быть положительным, поскольку вы смещаете по отношению к P1.

Ответ 3

Objective-C адаптация ответ nempoBu4:

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

Ответ 4

Ниже приведен пример использования некоторой геометрии: -

две линии касаются круга с надписью

Нормаль к касательной встречается в центре круга.

Пусть угол между линиями равен X

Угол, расположенный в центре круга, будет K = 360-90 * 2-X = 180-X

Давайте рассмотрим две точки касательных как (x1, y) и (x2, y)

Хорда, соединяющая точки, имеет длину l = (x2-x1)

Внутри круга хорда и две нормали длины r (радиус) образуют равнобедренный треугольник

Пендикулярный разделитель трайлинга равен равным половинчатым прямоугольным треугольникам.

Один из углов - K/2, а сторона - l/2

с использованием свойств прямоугольного треугольника sin (K/2) = (l/2)/r

r = (l/2)/sin (K/2)

но K = 180-X, поэтому r = (l/2)/sin (90-X/2) = (l/2)/cos (X/2)

следовательно, r = (x2-x1)/(2 * cos (X/2))

Теперь просто нарисуйте дугу от (x1, y) до (x2, y) с помощью радиуса r

Примечание: -

Вышеизложенное объясняется только для линий, которые встречаются в начале координат, а ось Y делит угол между ними на половину. Но в равной степени применимо для всех углов просто нужно применить поворот и перевод перед применением вышеизложенного. Кроме того, вам нужно выбрать некоторые значения x пересечения, из которых вы хотите нарисовать дугу. Значения не должны быть слишком далеки или близки к исходному.

Ответ 5

Вот моя реализация идеи dbc на С#:

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