wake-up-neo.com

Algorithmus zum Erstellen abgerundeter Ecken in einem Polygon

Ich bin auf der Suche nach einem Algorithmus, mit dem ich aus einem Polygon abgerundete Ecken erstellen kann .. In Input bekomme ich ein Array von Punkten, das das Polygon (rote Linie) darstellt, und in der Ausgabe ein Array von Punkten, die das Polygon darstellen mit abgerundeter Ecke (schwarze Linie). 

Ich möchte auch eine Möglichkeit haben, den Radius jeder Ecke zu kontrollieren. Ich habe bereits versucht, Bezier und Subdivision zu verwenden, aber es ist nicht das, wonach ich suche. Bezier und Unterteilung glätten das gesamte Polygon. Was ich will, es werden nur die Ecken abgerundet.

Jemand kennt einen guten Algorithmus dafür. Ich arbeite in C #, aber der Code muss unabhängig von .NET-Bibliotheken sein.

Example

39
ZouBi

Einige Geometrie mit Paint:


0. Du hast eine Ecke:
Corner

1. Sie kennen die Koordinaten von Eckpunkten, lassen Sie es P sein1, P2 und P:
Points of corner

2. Jetzt können Sie Vektoren aus Punkten und Winkeln zwischen Vektoren erhalten:
Vectors and angle

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


3. Liefert die Länge des Segments zwischen dem Winkelpunkt und den Schnittpunkten mit dem Kreis.
Segment

segment = PC1  = PC2  = Radius/tan (Winkel/2) |


4. Hier müssen Sie die Länge des Segments und die minimale Länge aus PP überprüfen1 und PP2:
Minimal length
Länge des PP1:

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

Länge von PP2:

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

Wenn Segment> PP1 oder Segment> PP2 dann müssen Sie den Radius verringern:

min = min (pp1, PP2) (für Polygone ist es besser, diesen Wert durch 2 zu teilen) 
 segment> min? 
 Segment = min 
 Radius = Segment * | tan (Winkel/2) |


5. Länge der Bestellung abrufen:

PO = Quadrat (Radius)2  + segment2)


6. Holen Sie sich das C1X und C1Y durch das Verhältnis zwischen den Koordinaten des Vektors, der Länge des Vektors und der Länge des Segments:
Coordinates of PC1

Anteil:

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

So:

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

Dasselbe gilt für C1Y:

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


7. Holen Sie sich das C2X und C2Y auf die gleiche Weise:

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


8. Jetzt können Sie die Addition von Vektoren PC verwenden1 und PC2 um den Kreismittelpunkt auf die gleiche Weise proportional zu finden:
Addition of vectors

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

Hier:

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

Lassen:

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. Hier können Sie einen Bogen zeichnen. Dazu müssen Sie den Anfangswinkel und den Endwinkel des Bogens ermitteln:
Arc
Fand es hier :

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


10. Zum Schluss müssen Sie einen Schwenkwinkel erhalten und einige Überprüfungen durchführen:
Sweep angle

sweepAngle = endAngle - startAngle

Wenn sweepAngle <0 ist, tauschen Sie startAngle und endAngle aus und invertieren Sie sweepAngle:

sweepAngle < 0 ?    
    sweepAngle = - sweepAngle
    startAngle = endAngle

Prüfen Sie, ob sweepAngle> 180 Grad ist:

sweepAngle > 180 ?    
    sweepAngle = 180 - sweepAngle


11. Und jetzt können Sie eine abgerundete Ecke zeichnen:
The result

Einige Geometrie mit 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));
}

Um Bogenpunkte zu erhalten, können Sie Folgendes verwenden:

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

Sie suchen nach einem Arkustangens zu zwei verbundenen Liniensegmenten mit einem bestimmten Radius, die durch ein aufeinanderfolgendes Array von Punkten gegeben werden. Der -Algorithmus zum Finden dieses Bogens lautet wie folgt:

  1. Konstruieren Sie für jedes Segment einen normalen Vektor.

    1. Wenn Sie in 2d arbeiten, können Sie einfach die beiden Endpunkte abziehen, um einen Tangentenvektor (X, Y) zu erhalten. In diesem Fall sind normale Vektoren Plus oder Minus (-Y, X). Normalisieren Der Normalenvektor auf Länge eins. Wählen Sie schließlich die Richtung mit einem positiven Punktprodukt mit dem Tangentenvektor des nächsten Segments. (Siehe Update unter). 

    2. Wenn Sie in 3d und nicht in 2d arbeiten, erhalten Sie die Normalen, Kreuz Tangentialvektoren der beiden Segmente am Scheitelpunkt, die Sie abrunden möchten, um einen senkrechten Vektor zur Ebene der Linien zu erhalten. Wenn das Lot eine Länge von Null hat, sind die Segmente parallel und es kann keine Runde erforderlich sein. Andernfalls normalisieren Sie es und kreuzen Sie dann das Lot mit der Tangente, um die Normalen zu erhalten.)

  2. Versetzen Sie jedes Liniensegment mit Hilfe der Normalenvektoren um den gewünschten Radius zum Inneren des Polygons. Um ein Segment zu versetzen, verschieben Sie seine Endpunkte mit dem gerade berechneten Normalvektor N: P '= P + r * N (eine lineare Kombination).

  3. Überschneide die beiden Versatzlinien , um die Mitte zu finden. (Dies funktioniert, weil ein Radiusvektor eines Kreises immer senkrecht zu seiner Tangente ist.)

  4. Um den Punkt zu finden, an dem der Kreis jedes Segment schneidet, verschieben Sie den Kreismittelpunkt nach hinten zu jedem Originalsegment. Dies sind die Endpunkte Ihres Bogens.

  5. Stellen Sie sicher, dass sich die Bogenendpunkte in jedem Segment befinden. Andernfalls erstellen Sie ein sich selbst schneidendes Polygon.

  6. Erstellen Sie einen Bogen durch beide Endpunkte mit dem von Ihnen bestimmten Mittelpunkt und Radius.

Ich habe keine geeignete Zeichensoftware zur Hand, aber dieses Diagramm zeigt die Idee:

enter image description here

An dieser Stelle müssen Sie entweder Klassen einführen, um eine Figur darzustellen, die aus Linien- und Bogensegmenten besteht, oder den Bogen mit einer geeigneten Genauigkeit polygonisieren und alle Segmente zum Polygon hinzufügen.

Update: Ich habe das Bild aktualisiert und die Punkte P1, P2 und P3 sowie die Normalenvektoren Norm12 und Norm23 beschriftet. Die normalisierten Normalen sind nur bis zur Umkehrrichtung eindeutig, und Sie sollten die Umkehrungen wie folgt wählen:

  • Das dot Produkt von Norm12 mit (P3 - P2) muss positiv sein. Wenn es negativ ist, mehrere Norm12 durch -1.0. Wenn es Null ist, sind die Punkte kollinear und es muss keine abgerundete Ecke erstellt werden. Dies liegt daran, dass Sie in Richtung P3 verschieben möchten.

  • Das Punktprodukt von Norm23 mit (P1 - P2) muss ebenfalls positiv sein, da Sie sich in Richtung P1 verschieben.

25
dbc

Objective-C-Anpassung der nempoBu4-Antwort :

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;
}
6
Michael Vlasov

Hier ist meine Realisierung der Idee von dbc zu 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;
}
1
viter.alex

Hier ist eine Möglichkeit, etwas Geometrie zu verwenden: -

  1. die beiden Linien sind tangential zur Kreisbeschriftung
  2. Die Normalen der Tangente treffen sich im Zentrum des Kreises.
  3. Der Winkel zwischen den Linien sei X
  4. Der im Mittelpunkt des Kreises nach unten gerichtete Winkel beträgt K = 360-90 * 2-X = 180-X
  5. Lasst uns die zwei Tangentenpunkte als (x1, y) und (x2, y) bestimmen
  6. Der Akkord, der die Punkte verbindet, hat die Länge l = (x2-x1)
  7. Innerhalb des Kreises bilden der Akkord und zwei Normalen der Länge r (Radius) ein gleichschenkliges Dreieck
  8. Das Pendel teilt die Spur in gleich halbierte rechtwinklige Dreiecke auf.
  9. Der Winkel ist K/2 und die Seite ist l/2 
  10. unter Verwendung der Eigenschaften des rechtwinkligen Dreiecks sin (K/2) = (l/2)/r
  11. r = (l/2)/sin (K/2)
  12. aber K = 180-X, so r = (1/2)/sin (90-X/2) = (1/2)/cos (X/2)
  13. daher ist r = (x2-x1)/(2 * cos (X/2))
  14. Zeichnen Sie nun einfach einen Bogen von (x1, y) nach (x2, y) mit dem Radius r

Hinweis:-  

Das Obige wird nur für Linien erläutert, die sich am Ursprung treffen, und die Y-Achse teilt den Winkel zwischen ihnen in zwei Hälften. Es ist jedoch gleichermaßen anwendbar, dass alle Ecken nur eine Drehung und eine Übersetzung anwenden müssen, bevor das Obige angewendet wird. Außerdem müssen Sie einige x-Werte für den Schnittpunkt auswählen, von wo aus Sie den Bogen zeichnen möchten. Die Werte sollten nicht zu weit entfernt oder nahe an Origin liegen

0
Vikram Bhat