Algoritmo per la creazione di angoli arrotondati in un poligono

Sto cercando un algoritmo che mi permetta di creare angoli arrotondati da un poligono. In Input, ottengo una serie di punti che rappresenta il poligono (linea rossa) e in uscita, una serie di punti che rappresenta il poligono con l’angolo arrotondato (linea nera).

Mi piacerebbe anche avere un modo per controllare il raggio di ogni angolo. Ho già provato a usare Bezier e Subdivision ma non è quello che sto cercando. Bezier e Subdivision stanno lisciando tutto il poligono. Quello che voglio, è solo rendere gli angoli arrotondati.

Qualcuno conosce un buon algoritmo per farlo? Sto lavorando in C # ma il codice deve essere indipendente da qualsiasi libreria .NET.

Esempio

Alcune geometrie con Paint:

0. Hai un angolo:
Angolo

1. Conosci le coordinate dei punti d’angolo, lascia che sia P 1 , P 2 e P:
Punti d'angolo

2. Ora puoi ottenere i vettori dai punti e dall’angolo tra i vettori:
Vettori e angolazione

  angolo = atan (P Y - P 1 Y , P X - P 1 X ) - atan (P Y - P 2 Y , P X - P 2 X ) 

3. Ottieni la lunghezza del segmento tra il punto angular e i punti di intersezione con il cerchio.
Segmento

  segmento = PC 1 = PC 2 = raggio / | tan (angolo / 2) | 

4. Qui è necessario controllare la lunghezza del segmento e la lunghezza minima da PP 1 e PP 2 :
Lunghezza minima
Lunghezza di PP 1 :

  PP 1 = sqrt ((P X - P 1 X ) 2 + (P Y - P 1 Y ) 2 ) 

Lunghezza di PP 2 :

  PP 2 = sqrt ((P X - P 2 X ) 2 + (P Y - P 2 Y ) 2 ) 

Se segmento> PP 1 o segmento> PP 2, è necessario ridurre il raggio:

  min = Min (PP 1 , PP 2 ) (per poligono è meglio dividere questo valore per 2)
 segmento> min?
     segmento = min
     raggio = segmento * | tan (angolo / 2) | 

5. Ottieni la lunghezza di PO:

  PO = sqrt (raggio 2 + segmento 2 ) 

6. Ottieni C 1 X e C 1 Y in base alla proporzione tra le coordinate del vettore, la lunghezza del vettore e la lunghezza del segmento:
Coordinate di PC1

Proporzione:

  (P X - C 1 X ) / (P X - P 1 X ) = PC 1 / PP 1 

Così:

  C 1 X = P X - (P X - P 1 X ) * PC 1 / PP 1 

Lo stesso per C 1 Y :

  C 1 Y = P Y - (P Y - P 1 Y ) * PC 1 / PP 1 

7. Prendi C 2 X e C 2 Y allo stesso modo:

  C 2 X = P X - (P X - P 2 X ) * PC 2 / PP 2
 C 2 Y = P Y - (P Y - P 2 Y ) * PC 2 / PP 2 

8. Ora è ansible utilizzare l’aggiunta di vettori PC 1 e PC 2 per trovare il centro del cerchio allo stesso modo in proporzione:
Aggiunta di vettori

  (P X - O X ) / (P X - C X ) = PO / PC
 (P Y - O Y ) / (P Y - C Y ) = PO / PC 

Qui:

  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 ) 2 + (P Y - C Y ) 2 ) 

Permettere:

  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 

Così:

  PC = sqrt (dx 2 + dy 2 )

 O X = P X - dx * PO / PC
 O Y = P Y - dy * PO / PC 

9. Qui puoi disegnare un arco. Per questo è necessario ottenere l’angolo iniziale e l’angolo finale dell’arco:
Arco
Trovato qui :

  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. Alla fine è necessario ottenere un angolo di sweep e fare alcuni controlli per questo:
Angolo di spazzata

 sweepAngle = endAngle - startAngle 

Se sweepAngle <0 allora scambia startAngle e endAngle e inverti sweepAngle:

 sweepAngle < 0 ? sweepAngle = - sweepAngle startAngle = endAngle 

Controlla se sweepAngle> 180 gradi:

 sweepAngle > 180 ? sweepAngle = 180 - sweepAngle 

11. E ora puoi disegnare un angolo arrotondato:
Il risultato

Alcune geometrie con 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)); } 

Per ottenere punti d'arco puoi usare questo:

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

Stai cercando un arco tangente a due segmenti di linea connessi, di un dato raggio, dato da una serie sequenziale di punti. L’ algoritmo per trovare questo arco è il seguente:

  1. Per ogni segmento, costruisci un vettore normale.

    1. Se stai lavorando in 2d, puoi semplicemente sottrarre i due endpoint per ottenere un vettore tangente (X, Y). In tal caso, i vettori normali saranno più o meno (-Y, X). Normalizza il vettore normale alla lunghezza uno. Infine, scegli la direzione con un prodotto punto positivo con il vettore tangente del segmento successivo. ( Vedi aggiornamento sotto ).

    2. Se stai lavorando in 3d not 2d, per ottenere il normale, attraversa i vettori tangenti dei due segmenti sul vertice che desideri arrotondare per ottenere un vettore perpendicolare al piano delle linee. Se la perpendicolare ha lunghezza zero, i segmenti sono paralleli e non è ansible richiedere arrotondamenti. Altrimenti, normalizzalo, quindi attraversa la perpendicolare con la tangente per ottenere il normale.)

  2. Utilizzando i vettori normali, spostare ciascun segmento di linea verso l’interno del poligono in base al raggio desiderato. Per compensare un segmento, offset i suoi endpoint usando il vettore normale N appena calcolato, in questo modo: P ‘= P + r * N (una combinazione lineare).

  3. Interseca le due linee di offset per trovare il centro. (Funziona perché un vettore raggio di un cerchio è sempre perpendicolare alla sua tangente.)

  4. Per trovare il punto in cui il cerchio interseca ciascun segmento, sposta il centro del cerchio all’indietro verso ciascun segmento originale. Questi saranno gli endpoint del tuo arco.

  5. Assicurati che i punti finali dell’arco si trovino all’interno di ogni segmento, altrimenti creerai un poligono autointersecante.

  6. Crea un arco attraverso entrambi i punti finali con il centro e il raggio che hai determinato.

Non ho a disposizione software di disegno adeguato, ma questo tipo di diagramma mostra l’idea:

inserisci la descrizione dell'immagine qui

A questo punto sarà necessario introdurre le classi per rappresentare una figura composta da segmenti di linea e di arco, oppure poligonizzare l’arco con una precisione appropriata e aggiungere tutti i segmenti al poligono.

Aggiornamento: ho aggiornato l’immagine, etichettando i punti P1, P2 e P3, e vettori normali Norm12 e Norm23. Le normali normalizzate sono uniche solo fino alla direzione del flipping, e dovresti scegliere i flip come segue:

  • Il prodotto punto di Norm12 con (P3 – P2) deve essere positivo. Se è negativo, più Norm12 di -1.0. Se è zero, i punti sono collineari e non è necessario creare angoli arrotondati. Questo perché si desidera sfalsare verso P3.

  • Anche il prodotto punto di Norm23 con (P1 – P2) deve essere positivo poiché si sta sfalsando verso P1.

Adattamento oggettivo-C della risposta di 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 (py - p1.y, px - p1.x) - atan2f (py - p2.y, px - p2.x)); // 3 CGFloat segment = radius / fabsf (tanf (angle / 2)); CGFloat p_c1 = segment; CGFloat p_c2 = segment; // 4 CGFloat p_p1 = sqrtf (sqr (px - p1.x) + sqr (py - p1.y)); CGFloat p_p2 = sqrtf (sqr (px - p2.x) + sqr (py - 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) (px - (px - p1.x) * p_c1 / p_p1); c1.y = (CGFloat) (py - (py - p1.y) * p_c1 / p_p1); // 7 CGPoint c2; c2.x = (CGFloat) (px - (px - p2.x) * p_c2 / p_p2); c2.y = (CGFloat) (py - (py - p2.y) * p_c2 / p_p2); // 8 CGFloat dx = px * 2 - c1.x - c2.x; CGFloat dy = py * 2 - c1.y - c2.y; CGFloat p_c = sqrtf (sqr (dx) + sqr (dy)); CGPoint o; ox = px - dx * p_o / p_c; oy = py - dy * p_o / p_c; // 9 CGFloat start_angle = positive_angle (atan2f ((c1.y - oy), (c1.x - ox))); CGFloat end_angle = positive_angle (atan2f ((c2.y - oy), (c2.x - ox))); 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* 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; } 

Ecco la mia realizzazione dell’idea di dbc su c #:

 ///  /// Round polygon corners ///  /// Vertices array /// Round radius ///  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; } 

Ecco un modo con alcune geometrie: –

  1. le due linee sono tangenti al cerchio inscritto
  2. Il normale alla tangente si incontra al centro del cerchio.
  3. Lascia che l’angolo tra le linee sia X
  4. L’angolo sotteso al centro del cerchio sarà K = 360-90 * 2-X = 180-X
  5. Decidiamo i due punti di tangente come (x1, y) e (x2, y)
  6. La corda che unisce i punti ha lunghezza l = (x2-x1)
  7. All’interno del cerchio, la corda e due normali di lunghezza r (raggio) formano un triangolo isoscele
  8. Il pendicolare divide il trainer in triangoli ad angolo retto a metà uguali.
  9. Uno di angolo è K / 2 e il lato è l / 2
  10. usando le proprietà del triangolo ad angolo retto sin (K / 2) = (l / 2) / r
  11. r = (l / 2) / sin (K / 2)
  12. ma K = 180-X così r = (l / 2) / sin (90-X / 2) = (l / 2) / cos (X / 2)
  13. quindi r = (x2-x1) / (2 * cos (X / 2))
  14. Ora semplicemente disegna un arco da (x1, y) a (x2, y) usando il raggio r

Nota:-

Quanto sopra è spiegato solo per le linee che si incontrano all’origine e l’asse Y divide l’angolo tra di loro in metà. Ma è ugualmente applicabile a tutti gli angoli, basta applicare una rotazione e una traduzione prima di applicare quanto sopra. Inoltre è necessario selezionare alcuni valori x di intersezione da cui si desidera disegnare l’arco. I valori non dovrebbero essere troppo lontani o vicini all’origine