用于在多边形中创建圆角的算法

Question

我正在寻找一种允许我从多边形创建圆角的算法.在Input中,我得到一个表示多边形(红线)和输出的点数组,一个点数组,表示带圆角的多边形(黑线).

我还想有办法控制每个角落的半径.我已经尝试过使用Bezier和Subdivision,但这不是我想要的.Bezier和Subdivision正在平滑所有多边形.我想要的是,它只是使角落圆润.

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

Answer 1

使用Paint的几何几何:

你有一个角落:


你知道角点的坐标,让它为P ₁,P ₂和P:


2.现在你可以从矢量之间的点和角度得到矢量:

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

3.获得角点与圆的交点之间的段长度.

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

4.在这里你需要检查段的长度和PP ₁和PP ₂的最小长度:

PP _1的长度:

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

PP _2的长度:

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

如果segment> PP ₁或segment> PP ₂则需要减小半径:

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的长度:

PO = sqrt(radius2 + segment2)

6. 通过向量坐标,向量长度和段长度之间的比例得到C _{1 X}和C _{1 Y}:

比例:

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

所以:

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

对于C _{1 Y来说也是如此}:

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

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

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

8.现在你可以使用向量PC ₁和PC _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

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

Answer 2

您正在寻找与给定半径的两个连接线段相切的圆弧,由一些连续的点阵列给出.找到此弧的算法如下:

1. 对于每个片段,构建法向量.

   1. 如果您在2d工作,则可以减去两个端点以获得切线向量(X,Y).在这种情况下,法向量将是正或负(-Y,X). 将法向量标准化为长度1.最后,选择具有正点积的方向和下一段的切线向量.(见下面的更新).

   2. 如果您在3d而不是2d中工作,要获得法线,请在要舍入的顶点处交叉两个线段的切线向量,以获得到线平面的垂直向量.如果垂线的长度为零,则这些段是平行的,不需要圆形.否则,将其标准化,然后与切线交叉垂直以获得法线.)

2. 使用法线向量,将每个线段朝向多边形内部偏移所需的半径.要偏移一个段,使用刚才计算的法向量N来偏移其端点,如下所示:P'= P + r*N(线性组合).

3. 将两条偏移线相交以找到中心.(这是因为圆的半径矢量始终垂直于其切线.)

4. 要找到圆与每个线段相交的点,请将圆心向后偏移到每个原始线段.这些将是您的弧的端点.

5. 确保圆弧端点位于每个线段内,否则您将创建一个自相交的多边形.

6. 通过两个端点创建弧,并确定中心和半径.

我手边没有任何合适的绘图软件,但这个图表显示了这个想法:

此时,您需要引入类来表示由线段和弧段组成的图形,或者将弧多边形化为适当的精度,并将所有段添加到多边形.

更新:我更新了图像,标记了点P1,P2和P3,以及法线向量Norm12和Norm23.标准化法线仅在翻转方向上是唯一的,您应该按如下方式选择翻转:

• Norm12与(P3-P2)的点积必须为正.如果是负数,则将Norm12乘以-1.0.如果它为零,则点是共线的,不需要创建圆角.这是因为你想要向P3偏移.

• Norm23与(P1-P2)的点积也必须为正,因为您偏向P1.

Answer 3

我可以提供一种简单且非常可计算和可编程的方法，该方法使用最少的计算，包括“仅”3 个平方根，并且没有任何反三角函数。

不要对我所写的故意详尽的解释感到畏惧，因为我这样写的目的是为了确保可以理解绝对微不足道的（与撰写本文时这里的所有其他解决方案相比）算法。事实上，我只是在承认替代方案所需的算法和计算复杂性之后才设计了它，即多次调用反三角函数（在其看似良性的名称背后隐藏了大量计算复杂性）和大量的操作。

（我已经通过使用 JavaScript 和 SVG 对其进行编程来验证了所提出方法的有效性。我将使用以前的编程语言来帮助说明该方法）

假设您想要“圆化”的某个角由已知点A、B和C组成，其中B是“角”。

该解决方案可以通过以下步骤来描述：

1. 计算BF向量的长度：

   长度等于圆的半径 ( FO )（您自己选择的已知值）除以向量BF和BO之间的角度的正切。这是因为由B、O和F点组成的三角形是“直角”三角形（向量BF和FO之间的角度为 90 度）。

   矢量BF和BO之间的角度是矢量BA和BC之间的角度的一半。这听起来可能很明显，也可能不那么明显，请放心，它是可以证明的，但我省略了证明。

   角度之间的关系很有用，因为恰好有一个相当简单的方程来表达角度的正切和两倍角度的余弦之间的关系：Math.tan(a/2) == Math.sqrt((1 - Math.cos(a)) / (1 + Math.cos(a))。

   碰巧向量BA和BC ( Math.cos(a)) 之间的角度的余弦是两个向量的点积除以它们的长度的乘积（请参阅维基百科上向量点积的定义）。

   因此，计算出角度的余弦后，您可以计算半角的正切，然后计算BF的长度：

   BA（图例：我将向量（ 、等）建模BC为具有属性的对象x以及y它们在屏幕空间中各自的坐标（X 向右增加，Y 向下）；radius是所需的圆角半径，BF_length是长度BF （显然））

   /// Helper functions
   const length = v => Math.sqrt(v.x * v.x + v.y * v.y);
   const dot_product = (v1, v2) => v1.x * v2.x + v1.y * v2.y;
   const cosine_between = (v1, v2) => dot_product(v1, v2) / (length(v1) * length(v2));
   
   const cos_a = cosine_between(BA, BC);
   const tan_half_a = Math.sqrt((1 - cos_a) / (1 + cos_a));
   const BF_length = radius / tan_half_a;
   

2. 计算BF向量。我们现在知道它的长度（BF_length上面），并且由于BF与向量BA位于同一条线上，前者（并且隐含地，点F相对于点B的坐标）可以通过进行标量乘法来计算BF的长度等于BA的单位向量：

   /// Helper functions
   const unit = v => {
       const l = length(v);
       return { x: v.x / l, y: v.y / l };
   };
   const scalar_multiply = (v, n) => ({ x: v.x * n, y: v.y * n });
   
   const BF = scalar_multiply(unit(BA), BF_length);
   

3. 现在您已经获得了上一步中的F坐标，您可以计算FO向量或O坐标。这是通过将与radius向量BA位于同一直线上的某个长度向量旋转90 度（两个向量都指向同一方向）并移动它以使其从F开始来完成的。

   现在，旋转是顺时针还是逆时针取决于向量 BA 和 BC 之间的角度的符号，更具体地说，如果各个角度之间的差值（每个角度都针对相同的参考进行计数，在本例中为 X 轴）BA、BC为正则逆时针旋转，否则顺时针旋转。

   如果可以避免的话，我们就不想计算角度——毕竟，这是我们想要的差异的符号。长话短说，角( sign)的符号可以用表达式计算出来Math.sign(BA.x * BC.y - BA.y * BC.x)。

   这里是O ( O)坐标的计算，其中FF是井的坐标：

   /// Helper functions
   const add = (v1, v2) => ({ x: v1.x + v2.x, y: v1.y + v2.y });
   const rotate_by_90_degrees = (v, sign) => ({ x: -v.y * sign, y: v.x * sign });
   
   const sign = Math.sign(BA.x * BC.y - BA.y * BC.x);
   const O = add(F, rotate_by_90_degrees(scalar_multiply(unit(BA), radius), sign));
   
   

就这样——因为您已经获得了点O ，其坐标与原始点（ A、B和C ）在同一空间中，所以您可以放置​​一个以O为中心、所用半径的圆。

选修的

计算从点F到某个F'（在向量上）的相应圆弧BC应该相对简单，但我不会包括它，除非有人表示希望这样做。

术语

对于大多数使用这个答案的人来说，这可能是显而易见的，但为了安全起见：请记住，在这个答案中，我通常将向量和坐标称为同一种度量——向量的数量是它拥有的组件数量；对于二维坐标系，元数显然是 2。因此，向量对象不会专门编码其“开始”，而仅编码“结束”——因为只有两个分量，这意味着向量“开始”在坐标系原点。例如，向量BA确实是点B和之间的向量A，但由于程序仅存储向量的两个分量（x以及y在片段中），因此就好像向量被移动，使得该点B现在位于坐标系。点也由两个部分组成，因此“矢量”和“点”可以互换。你必须非常清楚地理解这一点，否则我提供的一些计算有时可能会显得很奇怪。如果您仅将此答案中的向量视为每个包含两个元素的“一维”数组，可能会更容易。事实上，这就是我最初对它们进行编程的方式，但为了用代码表达解决方案，我切换到具有x和属性的对象。y

Answer 4

NempoBu4的 Objective-C适应答案:

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