Вопрос по c#, objective-c, algorithm, polygon, rounded-corners – Алгоритм создания закругленных углов в многоугольнике

40

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

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

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

По заданному R найдите круг, касающийся двух соседних отрезков. Центр находится на углу биссектрисы,t=R/sin(a/2), гдеt расстояние от центра до угловой точки,a это угол. xiaofeng.li

Ваш Ответ

5   ответов
59
Немного геометрии с помощью Paint:


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


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


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


angle = atan(PY - P1Y, PX - P1X) - atan(PY - P2Y, PX - P2X)


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

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


4. Здесь нужно проверить длину отрезка и минимальную длину по ПП1 и ПП2:

Длина ПП1:

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

Длина ПП2:

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

Если сегмент> PP1 или сегмент> PP2 тогда вам нужно уменьшить радиус:

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


5. Получить длину ПО:

PO = sqrt(radius2 + segment2)


6. Получить C1X и C1Y по соотношению между координатами вектора, длиной вектора и длиной отрезка:

Пропорция:

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

Так:

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

То же самое для C1Y:

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


7. Получить C2X и C2Y таким же образом:

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


8. Теперь вы можете использовать добавление векторов ПК1 и ПК2 таким же образом найти центр круга пропорционально:

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

Вот:

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

Позволять:

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

Так:

PC = sqrt(dx2 + dy2)

OX = PX - dx * PO / PC
OY = PY - dy * PO / PC


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

Нашел этоВот:

startAngle = atan((C1Y - OY) / (C1X - OX))
endAngle = atan((C2Y - OY) / (C2X - OX))


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

sweepAngle = endAngle - startAngle

Если sweepAngle <0, тогда поменяйте местами startAngle и endAngle и инвертируйте sweepAngle:

sweepAngle < 0 ?    
    sweepAngle = - sweepAngle
    startAngle = endAngle

Проверьте, развертка> 180 градусов:

sweepAngle > 180 ?    
    sweepAngle = 180 - sweepAngle


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

Немного геометрии с помощью 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));
}

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

//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);
}
@ZouBi Я обновил свой ответ с объяснением моего алгоритма. nempoBu4
@FrankK Извините, у меня нет идей, потому что я не вижу ваш код. Вы можете создать новый вопрос в StackOverflow и задать свою проблему там. nempoBu4
На случай, если кто-то вернется и у меня будет такая же проблема, как у меня Я должен был изменитьif (sweepAngle > Math.PI) sweepAngle = Math.PI - sweepAngle; вif (sweepAngle > Math.PI) sweepAngle = -(2 * Math.PI - sweepAngle); исправить некоторые изгибы недостающей части. Martin
Кажется, есть небольшая проблема с последней функцией, которая рисует дугу: если знак отрицательный, PointsCount должен быть рассчитан другим способом. Кстати, для исходных точек (20, 0) и (20, 20) дуга будет отрисована частично, так как pointCount будет рассчитан как 45, но нам нужно 135 (180 - 45) Ilya Builuk
0

две линии касаются окружностиНормаль к касательной встречается в центре круга.Пусть угол между линиями будет 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г = (л / 2) / грех (к / 2)но K = 180-X, поэтому r = (1/2) / sin (90-X / 2) = (1/2) / cos (X / 2)следовательно, r = (x2-x1) / (2 * cos (X / 2))Теперь просто нарисуйте дугу от (x1, y) до (x2, y), используя радиус r

Заметка:-

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

Извините, я не могу объяснить без изображения, но постараюсь добавить его. Vikram Bhat
Спасибо, что нашли время, но я едва понимаю ваш путь и как это реализовать ... ZouBi
Решение - это постоянное время, если вы его понимаете, кроме того, вы можете вращать и переводить другие вершины, а также выполнять шаги и реверсировать перевод и вращение. Vikram Bhat
попробуйте представить свою угловую вершину в начале координат и направить ее к положительной оси y, ось Y делит пополам угол между ними. Vikram Bhat
25

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

Для каждого сегмента постройте нормальный вектор.

Если вы работаете в 2d, вы можете просто вычесть две конечные точки, чтобы получить касательный вектор (X, Y). В этом случае нормальные векторы будут плюс или минус (-Y, X).нормировать вектор нормали к длине один. Наконец, выберите направление с положительным точечным произведением с касательным вектором следующего сегмента. (Смотрите обновление ниже).

Если вы работаете в 3d, а не 2d, чтобы получить нормальный,пересекать касательные векторы двух сегментов в вершине, которую вы хотите округлить, чтобы получить перпендикулярный вектор к плоскости линий. Если перпендикуляр имеет нулевую длину, сегменты параллельны, и никакие раунды не требуются. В противном случае нормализуйте его, затем пересечь перпендикуляр с касательной, чтобы получить нормаль.)

Используя векторы нормалей, сместите каждый отрезок в направлении внутренней части многоугольника на желаемый радиус. Чтобы сместить сегмент, сместите его конечные точки, используя только что вычисленный нормальный вектор N, например: P '= P + r * N (линейная комбинация).

Пересечь две линии смещения найти центр. (Это работает, потому что радиус-вектор круга всегда перпендикулярен его касательной.)

Чтобы найти точку, в которой круг пересекает каждый сегмент, сместите центр круга назад к каждому исходному сегменту. Это будут конечные точки вашей дуги.

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

Создайте дугу через обе конечные точки с центром и радиусом, которые вы определили.

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

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

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

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

Точечное произведение Norm23 с (P1 - P2) также должно быть положительным, поскольку вы смещаетесь в сторону P1.

Спасибо, я понимаю, как вы хотите, чтобы я это сделал. Но у меня пока есть один вопрос: как мне сместить линию к внутренней части многоугольника? ZouBi
dbc, спасибо за редактирование. Я думаю, что это лучший ответ, и я постараюсь написать код для этого. ZouBi
@ZouBi В основном эта линия всегда пересекается с двумя другими линиями. Может быть, вы могли бы проверить это. チーズパン
@JakeStelman - я заметил, что ваши изменения были отклонены, но вы можете добавить свой код Matlab в качестве отдельного ответа, если хотите. Это выглядит довольно полезно! dbc
1

Вот моя реализация идеи dbc на 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;
}
6

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;
}
Моя адаптация вносит небольшие изменения в оригинальный алгоритм: 1) углы преобразуются в положительные значения; 2) iOs использует другой способ определения дуг (начальный, конечный угол и флаг по часовой стрелке) против .Net (начальный, угол разворота). 3) Мой алгоритм строит полностью замкнутый графический контур с закругленными углами вместо рисования дуг в углах. Michael Vlasov
@ Tepeemm, вы правы насчет C #, но блестящий ответ от nempoBu4 помогает мне в разработке iOS. Многие разработчики iOS и Mac OS, как и я, посещают эту страницу с помощью поиска Google. Думаю, наша цель - помочь им. Michael Vlasov
meta.stackoverflow.com/q/290046/2336725 может быть полезной ссылкой. Я не знаю ни одного языка, чтобы знать, насколько отличаются Objective C и C #. Ваша реализация добавляет что-то кроме простой смены языка программирования? Кроме того, вы можете удалить все лишние пустые строки. Teepeemm
Это вопрос C #, а не объективный вопрос C. Teepeemm

Похожие вопросы