用于在多边形中创建圆角的算法(Algorithm for creating rounded corners in a polygon)

用于在多边形中创建圆角的算法(Algorithm for creating rounded corners in a polygon)

我正在寻找一种算法，可以让我从多边形创建圆角。 在输入中，我得到一个表示多边形（红线）和输出的点阵列，它表示具有圆角（黑线）的多边形。

我也想有办法控制每个角落的半径。 我已经试过使用Bezier和细分，但它不是我想要的。 Bezier和细分正在平滑所有的多边形。 我想要的，只是使角落变圆。

有人知道这样做的好算法吗？ 我正在使用C＃，但代码必须独立于任何.NET库。

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.

最满意答案

使用Paint的几何几何：

0.你有一个角落： 你知道角点的坐标，让它为P ₁ ，P ₂和P： 2.现在，您可以从矢量之间的点和角度获取矢量：

angle = atan(P_Y - P_1Y, P_X - P_1X) - atan(P_Y - P_2Y, P_X - P_2X)

3.获取角点和与圆的交点之间的线段长度。

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

4.在这里您需要检查段_1的长度和PP ₁和PP ₂的最小长度： PP _1的长度：

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

PP _2的长度：

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

如果分段> PP ₁或分段> PP _2，则需要减小半径：

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_1X) / (P_X - P_1X) = PC₁ / PP₁

所以：

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

C _{1 Y}相同：

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

7.以相同的方式获取C _{2 X}和C _{2 Y} ：

C_2X = P_X - (P_X - P_2X) * PC₂ / PP₂ C_2Y = P_Y - (P_Y - P_2Y) * 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_1X + C_2X - P_X C_Y = C_1Y + C_2Y - P_Y PC = sqrt((P_X - C_X)² + (P_Y - C_Y)²)

让：

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

所以：

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

9.在这里你可以绘制一条弧线。 为此，您需要获取弧的起始角和终止角： 在这里找到它：

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

10.最后你需要得到一个扫描角度并对它进行一些检查：

sweepAngle = endAngle - startAngle
 
 如果sweepAngle <0，则交换startAngle和endAngle，并反转sweepAngle： 
 
sweepAngle < 0 ?    
    sweepAngle = - sweepAngle
    startAngle = endAngle
 
 检查sweepAngle> 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);
}
Some geometry with Paint:
 
 0. You have a corner:   1. You know the coordinates of corner points, let it be P1, P2 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 PP1 and PP2:  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: 
 
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: 
 
(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);
}