kicad-developers team mailing list archive

[Maciej Sumiński <maciej.suminski@xxxxxxx>]

Hi Jon,

If we decide to handle this special case, then we need to account for
the point count as well. Otherwise it may lead to situations when the
number of points is higher than the number of segments.

Please see the attached patch (particularly 0002). I think these changes
might be committed after a short test period. If we want to go the safe,
but not so elegant way, then perhaps a simple condition could be added
to POLYGON_GEOM_MANAGER::IsSelfIntersecting().

Cheers,
Orson

On 03/25/2018 04:07 AM, Jon Evans wrote:
> Hi all (but especially Orson),
> 
> I wanted to fix the issue Bernhard raised here:
> https://bugs.launchpad.net/kicad/+bug/1751654/comments/7
> 
> I dug in to it a bit and found out
> that SHAPE_LINE_CHAIN::SelfIntersecting() doesn't work right when polygons
> are actually closed (i.e. the last point is the same as the first) and when
> m_closed is set to true.
> 
> The attached patch fixes this by only generating a closing segment when the
> last point isn't the same as the first point.  It fixes the issue with the
> self-intersection warning showing up even when you aren't yet intersecting
> (i.e. when the last point is the same as the first), and I didn't notice
> any obvious other issues, but maybe you can double-check that changing the
> behavior of SegmentCount() won't have any strange side-effects.
> 
> Thanks,
> -Jon
> 

From c90eefc472ff31999a2273d87b4967b3a9518e2e Mon Sep 17 00:00:00 2001
From: Maciej Suminski <maciej.suminski@xxxxxxx>
Date: Mon, 26 Mar 2018 11:23:43 +0200
Subject: [PATCH 1/2] Code formatting

---
 common/geometry/shape_line_chain.cpp | 12 ++++++++----
 include/geometry/shape_line_chain.h  |  1 +
 2 files changed, 9 insertions(+), 4 deletions(-)

diff --git a/common/geometry/shape_line_chain.cpp b/common/geometry/shape_line_chain.cpp
index 5f11b376c..2e0e12f10 100644
--- a/common/geometry/shape_line_chain.cpp
+++ b/common/geometry/shape_line_chain.cpp
@@ -397,7 +397,7 @@ const OPT<SHAPE_LINE_CHAIN::INTERSECTION> SHAPE_LINE_CHAIN::SelfIntersecting() c
                      // for closed polylines, the ending point of the
                      // last segment == starting point of the first segment
                      // this is a normal case, not self intersecting case
-                     !( IsClosed() && s1 == 0 && s2 == SegmentCount()-1 ) )
+                     !( IsClosed() && s1 == 0 && s2 == SegmentCount() - 1 ) )
             {
                 INTERSECTION is;
                 is.our = CSegment( s1 );
@@ -547,18 +547,21 @@ const std::string SHAPE_LINE_CHAIN::Format() const
 }
 
 
-bool SHAPE_LINE_CHAIN::CompareGeometry ( const SHAPE_LINE_CHAIN & aOther ) const
+bool SHAPE_LINE_CHAIN::CompareGeometry( const SHAPE_LINE_CHAIN& aOther ) const
 {
-    SHAPE_LINE_CHAIN a(*this), b( aOther );
+    SHAPE_LINE_CHAIN a( *this ), b( aOther );
     a.Simplify();
     b.Simplify();
 
     if( a.m_points.size() != b.m_points.size() )
         return false;
 
-    for( int i = 0; i < a.PointCount(); i++)
+    for( int i = 0; i < a.PointCount(); i++ )
+    {
         if( a.CPoint( i ) != b.CPoint( i ) )
             return false;
+    }
+
     return true;
 }
 
@@ -624,6 +627,7 @@ const VECTOR2I SHAPE_LINE_CHAIN::PointAlong( int aPathLength ) const
     return CPoint( -1 );
 }
 
+
 double SHAPE_LINE_CHAIN::Area() const
 {
     // see https://www.mathopenref.com/coordpolygonarea2.html
diff --git a/include/geometry/shape_line_chain.h b/include/geometry/shape_line_chain.h
index 135ea8b18..fad136fce 100644
--- a/include/geometry/shape_line_chain.h
+++ b/include/geometry/shape_line_chain.h
@@ -171,6 +171,7 @@ public:
     int SegmentCount() const
     {
         int c = m_points.size() - 1;
+
         if( m_closed && ( m_points[0] != m_points[c] ) )
             c++;
 
-- 
2.16.2

From 31903b03e22a831f3878bc32f61de19241133845 Mon Sep 17 00:00:00 2001
From: Maciej Suminski <maciej.suminski@xxxxxxx>
Date: Mon, 26 Mar 2018 12:49:16 +0200
Subject: [PATCH 2/2] Handle correctly closed SHAPE_LINE_CHAINs with equal
 first and last points

SHAPE_LINE_CHAIN by default do not repeat the first point in the point
list, even when it is set to 'closed'. In case the first point is
duplicated as the last point, the returned number of points/segments
needs to be adjusted to match the default behavior (ignore the duplicated
point).
---
 common/geometry/shape_line_chain.cpp |  6 +++---
 include/geometry/shape_line_chain.h  | 19 ++++++++++++-------
 2 files changed, 15 insertions(+), 10 deletions(-)

diff --git a/common/geometry/shape_line_chain.cpp b/common/geometry/shape_line_chain.cpp
index 2e0e12f10..5e3a6fea1 100644
--- a/common/geometry/shape_line_chain.cpp
+++ b/common/geometry/shape_line_chain.cpp
@@ -538,7 +538,7 @@ const std::string SHAPE_LINE_CHAIN::Format() const
 {
     std::stringstream ss;
 
-    ss << m_points.size() << " " << ( m_closed ? 1 : 0 ) << " ";
+    ss << PointCount() << " " << ( m_closed ? 1 : 0 ) << " ";
 
     for( int i = 0; i < PointCount(); i++ )
         ss << m_points[i].x << " " << m_points[i].y << " "; // Format() << " ";
@@ -553,7 +553,7 @@ bool SHAPE_LINE_CHAIN::CompareGeometry( const SHAPE_LINE_CHAIN& aOther ) const
     a.Simplify();
     b.Simplify();
 
-    if( a.m_points.size() != b.m_points.size() )
+    if( a.PointCount() != b.PointCount() )
         return false;
 
     for( int i = 0; i < a.PointCount(); i++ )
@@ -636,7 +636,7 @@ double SHAPE_LINE_CHAIN::Area() const
         return 0.0;
 
     double area = 0.0;
-    int size = m_points.size();
+    int size = PointCount();
 
     for( int i = 0, j = size - 1; i < size; ++i )
     {
diff --git a/include/geometry/shape_line_chain.h b/include/geometry/shape_line_chain.h
index fad136fce..a8e8bc14a 100644
--- a/include/geometry/shape_line_chain.h
+++ b/include/geometry/shape_line_chain.h
@@ -172,7 +172,7 @@ public:
     {
         int c = m_points.size() - 1;
 
-        if( m_closed && ( m_points[0] != m_points[c] ) )
+        if( m_closed && c > 1 && ( m_points[0] != m_points[c] ) )
             c++;
 
         return std::max( 0, c );
@@ -186,7 +186,12 @@ public:
      */
     int PointCount() const
     {
-        return m_points.size();
+        int c = m_points.size();
+
+        if( m_closed && c > 2 && ( m_points[0] == m_points[c - 1] ) )
+            --c;
+
+        return c;
     }
 
     /**
@@ -202,7 +207,7 @@ public:
         if( aIndex < 0 )
             aIndex += SegmentCount();
 
-        if( aIndex == (int)( m_points.size() - 1 ) && m_closed )
+        if( aIndex == SegmentCount() - 1 && m_closed )
             return SEG( m_points[aIndex], m_points[0], aIndex );
         else
             return SEG( m_points[aIndex], m_points[aIndex + 1], aIndex );
@@ -221,7 +226,7 @@ public:
         if( aIndex < 0 )
             aIndex += SegmentCount();
 
-        if( aIndex == (int)( m_points.size() - 1 ) && m_closed )
+        if( aIndex == SegmentCount() - 1 && m_closed )
             return SEG( const_cast<VECTOR2I&>( m_points[aIndex] ),
                         const_cast<VECTOR2I&>( m_points[0] ), aIndex );
         else
@@ -361,10 +366,10 @@ public:
      */
     void Append( const VECTOR2I& aP, bool aAllowDuplication = false )
     {
-        if( m_points.size() == 0 )
+        if( m_points.empty() )
             m_bbox = BOX2I( aP, VECTOR2I( 0, 0 ) );
 
-        if( m_points.size() == 0 || aAllowDuplication || CPoint( -1 ) != aP )
+        if( m_points.empty() || aAllowDuplication || CLastPoint() != aP )
         {
             m_points.push_back( aP );
             m_bbox.Merge( aP );
@@ -382,7 +387,7 @@ public:
         if( aOtherLine.PointCount() == 0 )
             return;
 
-        else if( PointCount() == 0 || aOtherLine.CPoint( 0 ) != CPoint( -1 ) )
+        else if( PointCount() == 0 || aOtherLine.CPoint( 0 ) != CLastPoint() )
         {
             const VECTOR2I p = aOtherLine.CPoint( 0 );
             m_points.push_back( p );
-- 
2.16.2

Attachment: signature.asc
Description: OpenPGP digital signature