kicad-developers team mailing list archive

[Andreas Buhr <andreas@xxxxxxxxxxxxxx>]

Dear Kicad developers,

when looking at the polygons generated by converting all copper layers
to polygons, I found some very small segments. I further investigated
these segments and the reason was that zones are inflated by adding
segments with rounded ends to their boundary. The rounded ends are
segmented into a specified number of segments. This was not aligned.
Often, two of these half-circles lye on each other and are bool-added
afterwards. This creates these small segments.

Find attached some code which aligns the segmentation. With the change,
circles are always segmented the same way and two circles with same
center and same radius have the same vertices in the generated polygon.

Generating all polygons for all copper layers of the Olimex A64 board
resulted in 415312 vertices before. With this patch applied, this number
goes down to 280378 vertices.

I hope you like it. Source code is clang-format-ed :-).

Cheers,
Andreas

Attachment: after.png
Description: PNG image

Attachment: before.png
Description: PNG image

From f138235f2b768b1749572a4bb7e66f8e8e36a748 Mon Sep 17 00:00:00 2001
From: Andreas Buhr <andreas@xxxxxxxxxxxxxx>
Date: Mon, 11 Dec 2017 11:03:41 +0100
Subject: [PATCH] always align segmentation of circles

Rounded end segments were converted to a polygon using
a specified "aCircleToSegmentCount". But the segmentation
was not aligned to be 0 degree, delta degree, 2*delta degree etc,
but it was aligned with the angle of the segment.
Often, two rounded segment ends are joined (boolAdd).
Because their segmentation did not align, this resulted
in more segments than necessary and sometimes very small segments.
This commit changes this behavior to create aligned
segmentations. This reduces the number of vertices in the generated
polygons substantially.
---
 common/convert_basic_shapes_to_polygon.cpp | 71 ++++++++++++++++++++----------
 1 file changed, 47 insertions(+), 24 deletions(-)

diff --git a/common/convert_basic_shapes_to_polygon.cpp b/common/convert_basic_shapes_to_polygon.cpp
index f2efe03..0c42263 100644
--- a/common/convert_basic_shapes_to_polygon.cpp
+++ b/common/convert_basic_shapes_to_polygon.cpp
@@ -149,59 +149,82 @@ void TransformRoundRectToPolygon( SHAPE_POLY_SET& aCornerBuffer,
  * Note: the polygon is inside the arc ends, so if you want to have the polygon
  * outside the circle, you should give aStart and aEnd calculated with a correction factor
  */
-void TransformRoundedEndsSegmentToPolygon( SHAPE_POLY_SET& aCornerBuffer,
-                                           wxPoint aStart, wxPoint aEnd,
-                                           int aCircleToSegmentsCount,
-                                           int aWidth )
+void TransformRoundedEndsSegmentToPolygon( SHAPE_POLY_SET& aCornerBuffer, wxPoint aStart,
+        wxPoint aEnd, int aCircleToSegmentsCount, int aWidth )
 {
-    int     radius  = aWidth / 2;
-    wxPoint endp    = aEnd - aStart; // end point coordinate for the same segment starting at (0,0)
-    wxPoint startp  = aStart;
-    wxPoint corner;
+    int     radius = aWidth / 2;
+    wxPoint direction =
+            aEnd - aStart; // end point coordinate for the same segment starting at (0,0)
+    wxPoint  startp = aStart;
+    wxPoint  endp = aEnd;
+    wxPoint  corner;
     VECTOR2I polypoint;
 
     aCornerBuffer.NewOutline();
 
     // normalize the position in order to have endp.x >= 0;
-    if( endp.x < 0 )
+    if( direction.x < 0 )
     {
-        endp    = aStart - aEnd;
-        startp  = aEnd;
+        direction = aStart - aEnd;
+        startp = aEnd;
+        endp = aStart;
     }
 
-    double delta_angle = ArcTangente( endp.y, endp.x ); // delta_angle is in 0.1 degrees
-    int seg_len        = KiROUND( EuclideanNorm( endp ) );
+    double delta_angle = ArcTangente( direction.y, direction.x ); // delta_angle is in 0.1 degrees
 
-    int delta = 3600 / aCircleToSegmentsCount;    // rot angle in 0.1 degree
+    int delta = 3600 / aCircleToSegmentsCount; // rot angle in 0.1 degree
 
     // Compute the outlines of the segment, and creates a polygon
     // add right rounded end:
-    for( int ii = 0; ii < 1800; ii += delta )
+
+    // Start arc:
+    corner = wxPoint( 0, radius );
+    RotatePoint( &corner, -delta_angle );
+    corner += endp;
+    polypoint.x = corner.x;
+    polypoint.y = corner.y;
+    aCornerBuffer.Append( polypoint.x, polypoint.y );
+
+    int ii = int( delta_angle ) % delta;
+    if( ii <= 0 )
+        ii += delta;
+    for( ; ii < 1800; ii += delta )
     {
+        assert( ( ii - int( delta_angle ) ) % delta == 0 );
         corner = wxPoint( 0, radius );
-        RotatePoint( &corner, ii );
-        corner.x += seg_len;
-        RotatePoint( &corner, -delta_angle );
-        corner += startp;
+        RotatePoint( &corner, ii - int( delta_angle ) );
+        corner += endp;
         polypoint.x = corner.x;
         polypoint.y = corner.y;
         aCornerBuffer.Append( polypoint.x, polypoint.y );
     }
 
     // Finish arc:
-    corner = wxPoint( seg_len, -radius );
+    corner = wxPoint( 0, -radius );
     RotatePoint( &corner, -delta_angle );
-    corner += startp;
+    corner += endp;
     polypoint.x = corner.x;
     polypoint.y = corner.y;
     aCornerBuffer.Append( polypoint.x, polypoint.y );
 
     // add left rounded end:
-    for( int ii = 0; ii < 1800; ii += delta )
+
+    // start arc:
+    corner = wxPoint( 0, -radius );
+    RotatePoint( &corner, -delta_angle );
+    corner += startp;
+    polypoint.x = corner.x;
+    polypoint.y = corner.y;
+    aCornerBuffer.Append( polypoint.x, polypoint.y );
+
+    ii = int( delta_angle ) % delta;
+    if( ii <= 0 )
+        ii += delta;
+    for( ; ii < 1800; ii += delta )
     {
+        assert( ( ii - int( delta_angle ) ) % delta == 0 );
         corner = wxPoint( 0, -radius );
-        RotatePoint( &corner, ii );
-        RotatePoint( &corner, -delta_angle );
+        RotatePoint( &corner, ii - int( delta_angle ) );
         corner += startp;
         polypoint.x = corner.x;
         polypoint.y = corner.y;
-- 
2.7.4