kicad-developers team mailing list archive
-
kicad-developers team
-
Mailing list archive
-
Message #17316
[PATCH] Better SHAPE_CONVEX for the PNS router
Hi everybody,
below is an improved patch to add a SHAPE_CONVEX for the PNS router. The
patch was generated against revision 5508.
In this version nice tight octagonal "hulls" are created for convex
polygons. I think it should work for arbitrary convex polygons (as long
as the requested distance between polygon and hull is larger than about
20) - but this probably just means I overlooked some corner case.
A trace snaking around some pads each arbitrarily rotated looks quite
weird... ;-)
I also think I figured out the "breakouts" stuff. This works nicely for
pads rotated by 45 degrees, but looks weird if the pad is rotated e.g.
by 30 degrees.
Finally I fixed a small bug in SHAPE_LINE_CHAIN, which ignored the
parameter aClearance when computing a bounding box.
Enjoy,
MGri
=== modified file 'common/geometry/shape_collisions.cpp'
--- common/geometry/shape_collisions.cpp 2015-03-09 10:06:54 +0000
+++ common/geometry/shape_collisions.cpp 2015-03-12 19:44:01 +0000
@@ -30,6 +30,7 @@
#include <geometry/shape_circle.h>
#include <geometry/shape_rect.h>
#include <geometry/shape_segment.h>
+#include <geometry/shape_convex.h>
typedef VECTOR2I::extended_type ecoord;
@@ -165,6 +166,32 @@
}
+static inline bool Collide( const SHAPE_CIRCLE& aA, const SHAPE_CONVEX& aB, int aClearance,
+ bool aNeedMTV, VECTOR2I& aMTV )
+{
+ bool found;
+ const SHAPE_LINE_CHAIN& lc( aB.Vertices() );
+
+ found = lc.Distance( aA.GetCenter() ) <= aClearance + aA.GetRadius();
+
+ if( !aNeedMTV || !found )
+ return found;
+
+ SHAPE_CIRCLE cmoved( aA );
+ VECTOR2I f_total( 0, 0 );
+
+ for( int s = 0; s < lc.SegmentCount(); s++ )
+ {
+ VECTOR2I f = pushoutForce( cmoved, lc.CSegment( s ), aClearance );
+ cmoved.SetCenter( cmoved.GetCenter() + f );
+ f_total += f;
+ }
+
+ aMTV = f_total;
+ return found;
+}
+
+
static inline bool Collide( const SHAPE_CIRCLE& aA, const SHAPE_SEGMENT& aSeg, int aClearance,
bool aNeedMTV, VECTOR2I& aMTV )
{
@@ -189,6 +216,20 @@
}
+static inline bool Collide( const SHAPE_LINE_CHAIN& aA, const SHAPE_CONVEX& aB, int aClearance,
+ bool aNeedMTV, VECTOR2I& aMTV )
+{
+ return Collide( aA, aB.Vertices(), aClearance, aNeedMTV, aMTV );
+}
+
+
+static inline bool Collide( const SHAPE_CONVEX& aA, const SHAPE_CONVEX& aB, int aClearance,
+ bool aNeedMTV, VECTOR2I& aMTV )
+{
+ return Collide( aA.Vertices(), aB.Vertices(), aClearance, aNeedMTV, aMTV );
+}
+
+
static inline bool Collide( const SHAPE_RECT& aA, const SHAPE_LINE_CHAIN& aB, int aClearance,
bool aNeedMTV, VECTOR2I& aMTV )
{
@@ -204,6 +245,13 @@
}
+static inline bool Collide( const SHAPE_RECT& aA, const SHAPE_CONVEX& aB, int aClearance,
+ bool aNeedMTV, VECTOR2I& aMTV )
+{
+ return Collide( aA, aB.Vertices(), aClearance, aNeedMTV, aMTV );
+}
+
+
static inline bool Collide( const SHAPE_RECT& aA, const SHAPE_SEGMENT& aSeg, int aClearance,
bool aNeedMTV, VECTOR2I& aMTV )
{
@@ -228,6 +276,13 @@
}
+static inline bool Collide( const SHAPE_CONVEX& aA, const SHAPE_SEGMENT& aB, int aClearance,
+ bool aNeedMTV, VECTOR2I& aMTV )
+{
+ return Collide( aA.Vertices(), aB, aClearance, aNeedMTV, aMTV );
+}
+
+
template<class ShapeAType, class ShapeBType>
inline bool CollCase( const SHAPE* aA, const SHAPE* aB, int aClearance, bool aNeedMTV, VECTOR2I& aMTV )
{
@@ -264,6 +319,9 @@
case SH_SEGMENT:
return CollCase<SHAPE_RECT, SHAPE_SEGMENT>( aA, aB, aClearance, aNeedMTV, aMTV );
+ case SH_CONVEX:
+ return CollCase<SHAPE_RECT, SHAPE_CONVEX>( aA, aB, aClearance, aNeedMTV, aMTV );
+
default:
break;
}
@@ -283,6 +341,9 @@
case SH_SEGMENT:
return CollCase<SHAPE_CIRCLE, SHAPE_SEGMENT>( aA, aB, aClearance, aNeedMTV, aMTV );
+ case SH_CONVEX:
+ return CollCase<SHAPE_CIRCLE, SHAPE_CONVEX>( aA, aB, aClearance, aNeedMTV, aMTV );
+
default:
break;
}
@@ -302,6 +363,9 @@
case SH_SEGMENT:
return CollCase<SHAPE_LINE_CHAIN, SHAPE_SEGMENT>( aA, aB, aClearance, aNeedMTV, aMTV );
+ case SH_CONVEX:
+ return CollCase<SHAPE_LINE_CHAIN, SHAPE_CONVEX>( aA, aB, aClearance, aNeedMTV, aMTV );
+
default:
break;
}
@@ -321,10 +385,35 @@
case SH_SEGMENT:
return CollCase<SHAPE_SEGMENT, SHAPE_SEGMENT>( aA, aB, aClearance, aNeedMTV, aMTV );
- default:
- break;
- }
-
+ case SH_CONVEX:
+ return CollCase<SHAPE_CONVEX, SHAPE_SEGMENT>( aB, aA, aClearance, aNeedMTV, aMTV );
+
+ default:
+ break;
+ }
+
+ case SH_CONVEX:
+ switch( aB->Type() )
+ {
+ case SH_RECT:
+ return CollCase<SHAPE_RECT, SHAPE_CONVEX>( aB, aA, aClearance, aNeedMTV, aMTV );
+
+ case SH_CIRCLE:
+ return CollCase<SHAPE_CIRCLE, SHAPE_CONVEX>( aB, aA, aClearance, aNeedMTV, aMTV );
+
+ case SH_LINE_CHAIN:
+ return CollCase<SHAPE_LINE_CHAIN, SHAPE_CONVEX>( aB, aA, aClearance, aNeedMTV, aMTV );
+
+ case SH_SEGMENT:
+ return CollCase<SHAPE_CONVEX, SHAPE_SEGMENT>( aA, aB, aClearance, aNeedMTV, aMTV );
+
+ case SH_CONVEX:
+ return CollCase<SHAPE_CONVEX, SHAPE_CONVEX>( aA, aB, aClearance, aNeedMTV, aMTV );
+
+ default:
+ break;
+ }
+
default:
break;
}
=== modified file 'common/geometry/shape_line_chain.cpp'
--- common/geometry/shape_line_chain.cpp 2015-03-06 14:26:47 +0000
+++ common/geometry/shape_line_chain.cpp 2015-03-12 19:44:01 +0000
@@ -499,6 +499,26 @@
}
+const VECTOR2I SHAPE_LINE_CHAIN::NearestPoint( const SEG& aSeg, int& dist ) const
+{
+ int nearest = 0;
+
+ dist = INT_MAX;
+ for( int i = 0; i < PointCount(); i++ )
+ {
+ int d = aSeg.LineDistance( CPoint( i ) );
+
+ if( d < dist )
+ {
+ dist = d;
+ nearest = i;
+ }
+ }
+
+ return CPoint( nearest );
+}
+
+
const std::string SHAPE_LINE_CHAIN::Format() const
{
std::stringstream ss;
=== added file 'include/geometry/shape_convex.h'
--- include/geometry/shape_convex.h 1970-01-01 00:00:00 +0000
+++ include/geometry/shape_convex.h 2015-03-12 21:13:00 +0000
@@ -0,0 +1,189 @@
+/*
+ * This program source code file is part of KiCad, a free EDA CAD application.
+ *
+ * Copyright (C) 2015 Kicad Developers, see change_log.txt for contributors.
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, you may find one here:
+ * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
+ * or you may search the http://www.gnu.org website for the version 2 license,
+ * or you may write to the Free Software Foundation, Inc.,
+ * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
+ */
+
+#ifndef __SHAPE_CONVEX_H
+#define __SHAPE_CONVEX_H
+
+#include <vector>
+
+#include <geometry/shape.h>
+#include <geometry/seg.h>
+#include <geometry/shape_line_chain.h>
+
+/**
+ * Class SHAPE_CONVEX
+ *
+ * Represents a convex polygon consisting of a zero-thickness closed chain of
+ * connected line segments.
+ *
+ * Internally the vertices are held in a SHAPE_LINE_CHAIN, please note that
+ * there is a "virtual" line segment between the last and first vertex.
+ */
+class SHAPE_CONVEX : public SHAPE
+{
+public:
+ /**
+ * Constructor
+ * Creates an empty polygon
+ */
+ SHAPE_CONVEX() :
+ SHAPE( SH_CONVEX )
+ {
+ m_points.SetClosed( true );
+ }
+
+ SHAPE_CONVEX( const SHAPE_CONVEX& aOther ) :
+ SHAPE( SH_CONVEX ), m_points( aOther.m_points )
+ {}
+
+ SHAPE* Clone() const
+ {
+ return new SHAPE_CONVEX( *this );
+ }
+
+ /**
+ * Function Clear()
+ * Removes all points from the polygon.
+ */
+ void Clear()
+ {
+ m_points.Clear();
+ }
+
+ /// @copydoc SHAPE::BBox()
+ const BOX2I BBox( int aClearance = 0 ) const
+ {
+ return m_points.BBox( aClearance );
+ }
+
+ /**
+ * Function PointCount()
+ *
+ * Returns the number of points (vertices) in this polygon
+ * @return number of points
+ */
+ int PointCount() const
+ {
+ return m_points.PointCount();
+ }
+
+ /**
+ * Function Point()
+ *
+ * Returns a reference to a given point in the polygon. Negative indices
+ * count from the end of the point list, e.g. -1 means "last point", -2
+ * means "second to last point" and so on.
+ * @param aIndex index of the point
+ * @return reference to the point
+ */
+ VECTOR2I& Point( int aIndex )
+ {
+ return m_points.Point( aIndex );
+ }
+
+ /**
+ * Function CPoint()
+ *
+ * Returns a const reference to a given point in the polygon. Negative
+ * indices count from the end of the point list, e.g. -1 means "last
+ * point", -2 means "second to last point" and so on.
+ * @param aIndex index of the point
+ * @return const reference to the point
+ */
+ const VECTOR2I& CPoint( int aIndex ) const
+ {
+ return m_points.CPoint( aIndex );
+ }
+
+ /**
+ * Function CDPoint()
+ *
+ * Returns a given point as a vector with elements of type double.
+ *
+ * @param aIndex index of the point
+ * @return the point with elements of type double
+ */
+ const VECTOR2D CDPoint( int aIndex ) const
+ {
+ const VECTOR2I& v = CPoint( aIndex );
+ return VECTOR2D( v.x, v.y );
+ }
+
+ /**
+ * Function Vertices()
+ *
+ * Returns the list of vertices defining this convex polygon.
+ *
+ * @return the list of vertices defining this convex polygon
+ */
+ const SHAPE_LINE_CHAIN& Vertices() const
+ {
+ return m_points;
+ }
+
+ /**
+ * Function Append()
+ *
+ * Appends a new point at the end of the polygon.
+ * @param aX is X coordinate of the new point
+ * @param aY is Y coordinate of the new point
+ */
+ void Append( int aX, int aY )
+ {
+ VECTOR2I v( aX, aY );
+ Append( v );
+ }
+
+ /**
+ * Function Append()
+ *
+ * Appends a new point at the end of the polygon.
+ * @param aP the new point
+ */
+ void Append( const VECTOR2I& aP )
+ {
+ m_points.Append( aP );
+ }
+
+ /// @copydoc SHAPE::Collide()
+ bool Collide( const SEG& aSeg, int aClearance = 0 ) const
+ {
+ return m_points.Collide( aSeg, aClearance );
+ }
+
+ void Move( const VECTOR2I& aVector )
+ {
+ m_points.Move( aVector );
+ }
+
+ bool IsSolid() const
+ {
+ return true;
+ }
+
+private:
+ // vertices
+ SHAPE_LINE_CHAIN m_points;
+};
+
+#endif // __SHAPE_CONVEX_H
=== modified file 'include/geometry/shape_line_chain.h'
--- include/geometry/shape_line_chain.h 2015-03-06 14:26:47 +0000
+++ include/geometry/shape_line_chain.h 2015-03-12 19:44:01 +0000
@@ -264,6 +264,9 @@
BOX2I bbox;
bbox.Compute( m_points );
+ if( aClearance != 0 )
+ bbox.Inflate( aClearance );
+
return bbox;
}
@@ -535,6 +538,17 @@
*/
const VECTOR2I NearestPoint( const VECTOR2I& aP ) const;
+ /**
+ * Function NearestPoint()
+ *
+ * Finds a point on the line chain that is closest to the line defined
+ * by the points of segment aSeg, also returns the distance.
+ * @param aSeg Segment defining the line.
+ * @param dist reference receiving the distance to the nearest point.
+ * @return the nearest point.
+ */
+ const VECTOR2I NearestPoint( const SEG& aSeg, int& dist ) const;
+
/// @copydoc SHAPE::Format()
const std::string Format() const;
=== modified file 'pcbnew/router/pns_logger.cpp'
--- pcbnew/router/pns_logger.cpp 2015-03-02 16:20:48 +0000
+++ pcbnew/router/pns_logger.cpp 2015-03-12 19:44:01 +0000
@@ -29,6 +29,7 @@
#include <geometry/shape_line_chain.h>
#include <geometry/shape_rect.h>
#include <geometry/shape_circle.h>
+#include <geometry/shape_convex.h>
PNS_LOGGER::PNS_LOGGER( )
{
@@ -173,6 +174,17 @@
break;
}
+ case SH_CONVEX:
+ {
+ const SHAPE_CONVEX* c = (const SHAPE_CONVEX*) aSh;
+ m_theLog << "convex " << c->PointCount() << " ";
+
+ for( int i = 0; i < c->PointCount(); i++ )
+ m_theLog << c->CPoint( i ).x << " " << c->CPoint( i ).y << " ";
+
+ break;
+ }
+
default:
break;
}
=== modified file 'pcbnew/router/pns_optimizer.cpp'
--- pcbnew/router/pns_optimizer.cpp 2015-03-10 14:38:27 +0000
+++ pcbnew/router/pns_optimizer.cpp 2015-03-12 21:34:12 +0000
@@ -22,6 +22,7 @@
#include <geometry/shape_line_chain.h>
#include <geometry/shape_rect.h>
+#include <geometry/shape_convex.h>
#include "pns_line.h"
#include "pns_diff_pair.h"
@@ -659,6 +660,48 @@
}
+PNS_OPTIMIZER::BREAKOUT_LIST PNS_OPTIMIZER::convexBreakouts( int aWidth,
+ const SHAPE* aShape, bool aPermitDiagonal ) const
+{
+ BREAKOUT_LIST breakouts;
+ const SHAPE_CONVEX* convex = static_cast<const SHAPE_CONVEX*>( aShape );
+
+ BOX2I bbox = convex->BBox( 0 );
+ VECTOR2I p0 = bbox.Centre();
+ // must be large enough to guarantee intersecting the convex polygon
+ int length = bbox.GetSize().EuclideanNorm() / 2 + 5;
+
+ for( int angle = 0; angle < 360; angle += ( aPermitDiagonal ? 45 : 90 ) )
+ {
+ SHAPE_LINE_CHAIN l;
+ VECTOR2I v0( p0 + VECTOR2I( length, 0 ).Rotate( angle * M_PI / 180.0 ) );
+ SHAPE_LINE_CHAIN::INTERSECTIONS intersections;
+ int n = convex->Vertices().Intersect( SEG( p0, v0 ), intersections );
+ // if n == 1 intersected a segment
+ // if n == 2 intersected the common point of 2 segments
+ // n == 0 can not happen I think, but...
+ if( n > 0 )
+ {
+ l.Append( p0 );
+
+ // for a breakout distance relative to the distance between
+ // center and polygon edge
+ //l.Append( intersections[0].p + (v0 - p0).Resize( (intersections[0].p - p0).EuclideanNorm() * 0.4 ) );
+
+ // for an absolute breakout distance, e.g. 0.1 mm
+ l.Append( intersections[0].p + (v0 - p0).Resize( 100000 ) );
+
+ // for the breakout right on the polygon edge
+ //l.Append( intersections[0].p );
+
+ breakouts.push_back( l );
+ }
+ }
+
+ return breakouts;
+}
+
+
PNS_OPTIMIZER::BREAKOUT_LIST PNS_OPTIMIZER::rectBreakouts( int aWidth,
const SHAPE* aShape, bool aPermitDiagonal ) const
{
@@ -743,6 +786,9 @@
case SH_CIRCLE:
return circleBreakouts( aWidth, shape, aPermitDiagonal );
+ case SH_CONVEX:
+ return convexBreakouts( aWidth, shape, aPermitDiagonal );
+
default:
break;
}
=== modified file 'pcbnew/router/pns_optimizer.h'
--- pcbnew/router/pns_optimizer.h 2015-02-18 16:53:46 +0000
+++ pcbnew/router/pns_optimizer.h 2015-03-12 19:44:01 +0000
@@ -158,6 +158,7 @@
BREAKOUT_LIST circleBreakouts( int aWidth, const SHAPE* aShape, bool aPermitDiagonal ) const;
BREAKOUT_LIST rectBreakouts( int aWidth, const SHAPE* aShape, bool aPermitDiagonal ) const;
BREAKOUT_LIST ovalBreakouts( int aWidth, const SHAPE* aShape, bool aPermitDiagonal ) const;
+ BREAKOUT_LIST convexBreakouts( int aWidth, const SHAPE* aShape, bool aPermitDiagonal ) const;
BREAKOUT_LIST computeBreakouts( int aWidth, const PNS_ITEM* aItem, bool aPermitDiagonal ) const;
int smartPadsSingle( PNS_LINE* aLine, PNS_ITEM* aPad, bool aEnd, int aEndVertex );
=== modified file 'pcbnew/router/pns_router.cpp'
--- pcbnew/router/pns_router.cpp 2015-03-11 22:48:53 +0000
+++ pcbnew/router/pns_router.cpp 2015-03-12 19:44:01 +0000
@@ -34,6 +34,7 @@
#include <geometry/shape_line_chain.h>
#include <geometry/shape_rect.h>
#include <geometry/shape_circle.h>
+#include <geometry/shape_convex.h>
#include "trace.h"
#include "pns_node.h"
@@ -202,52 +203,142 @@
solid->SetPos( c );
double orient = aPad->GetOrientation() / 10.0;
- bool nonOrtho = false;
- if( orient == 90.0 || orient == 270.0 )
- sz = VECTOR2I( sz.y, sz.x );
- else if( orient != 0.0 && orient != 180.0 )
+ if( aPad->GetShape() == PAD_CIRCLE )
{
- // rotated pads are replaced by for the moment by circles due to my laziness ;)
- solid->SetShape( new SHAPE_CIRCLE( c, std::min( sz.x, sz.y ) / 2 ) );
- nonOrtho = true;
+ solid->SetShape( new SHAPE_CIRCLE( c, sz.x / 2 ) );
}
-
- if( !nonOrtho )
+ else
{
- switch( aPad->GetShape() )
- {
- case PAD_CIRCLE:
- solid->SetShape( new SHAPE_CIRCLE( c, sz.x / 2 ) );
- break;
-
- case PAD_OVAL:
- if( sz.x == sz.y )
- solid->SetShape( new SHAPE_CIRCLE( c, sz.x / 2 ) );
- else
- {
- VECTOR2I delta;
-
- if( sz.x > sz.y )
- delta = VECTOR2I( ( sz.x - sz.y ) / 2, 0 );
- else
- delta = VECTOR2I( 0, ( sz.y - sz.x ) / 2 );
-
- SHAPE_SEGMENT* shape = new SHAPE_SEGMENT( c - delta, c + delta,
- std::min( sz.x, sz.y ) );
- solid->SetShape( shape );
- }
- break;
-
- case PAD_RECT:
- solid->SetShape( new SHAPE_RECT( c - sz / 2, sz.x, sz.y ) );
- break;
-
- default:
- TRACEn( 0, "unsupported pad shape" );
- delete solid;
-
- return NULL;
+ if( orient == 0.0 || orient == 90.0 || orient == 180.0 || orient == 270.0 )
+ {
+ if( orient == 90.0 || orient == 270.0 )
+ sz = VECTOR2I( sz.y, sz.x );
+
+ switch( aPad->GetShape() )
+ {
+ // PAD_CIRCLE already handled above
+
+ case PAD_OVAL:
+ if( sz.x == sz.y )
+ solid->SetShape( new SHAPE_CIRCLE( c, sz.x / 2 ) );
+ else
+ {
+ VECTOR2I delta;
+
+ if( sz.x > sz.y )
+ delta = VECTOR2I( ( sz.x - sz.y ) / 2, 0 );
+ else
+ delta = VECTOR2I( 0, ( sz.y - sz.x ) / 2 );
+
+ SHAPE_SEGMENT* shape = new SHAPE_SEGMENT( c - delta, c + delta,
+ std::min( sz.x, sz.y ) );
+ solid->SetShape( shape );
+ }
+ break;
+
+ case PAD_RECT:
+ solid->SetShape( new SHAPE_RECT( c - sz / 2, sz.x, sz.y ) );
+ break;
+
+ case PAD_TRAPEZOID:
+ {
+ wxPoint coords[4];
+ aPad->BuildPadPolygon( coords, wxSize( 0, 0 ), aPad->GetOrientation() );
+
+ SHAPE_CONVEX* shape = new SHAPE_CONVEX();
+ for( int ii = 0; ii < 4; ii++ )
+ {
+ shape->Append( wx_c + coords[ii] );
+ }
+
+ solid->SetShape( shape );
+ break;
+ }
+
+
+ default:
+ TRACEn( 0, "unsupported pad shape" );
+ delete solid;
+
+ return NULL;
+ }
+ }
+ else
+ {
+ switch( aPad->GetShape() )
+ {
+ // PAD_CIRCLE already handled above
+
+ case PAD_OVAL:
+ if( sz.x == sz.y )
+ solid->SetShape( new SHAPE_CIRCLE( c, sz.x / 2 ) );
+ else
+ {
+ wxPoint start;
+ wxPoint end;
+ wxPoint corner;
+
+ SHAPE_CONVEX* shape = new SHAPE_CONVEX();
+
+ int w = aPad->BuildSegmentFromOvalShape( start, end, 0.0, wxSize( 0, 0 ) );
+
+ if( start.y == 0 )
+ corner = wxPoint( start.x, -(w / 2) );
+ else
+ corner = wxPoint( w / 2, start.y );
+ RotatePoint( &start, aPad->GetOrientation() );
+ RotatePoint( &corner, aPad->GetOrientation() );
+ shape->Append( wx_c + corner );
+
+ for( int rot = 100; rot <= 1800; rot += 100 )
+ {
+ wxPoint p( corner );
+ RotatePoint( &p, start, rot );
+ shape->Append( wx_c + p );
+ }
+
+ if( end.y == 0 )
+ corner = wxPoint( end.x, w / 2 );
+ else
+ corner = wxPoint( -(w / 2), end.y );
+ RotatePoint( &end, aPad->GetOrientation() );
+ RotatePoint( &corner, aPad->GetOrientation() );
+ shape->Append( wx_c + corner );
+
+ for( int rot = 100; rot <= 1800; rot += 100 )
+ {
+ wxPoint p( corner );
+ RotatePoint( &p, end, rot );
+ shape->Append( wx_c + p );
+ }
+
+ solid->SetShape( shape );
+ }
+ break;
+
+ case PAD_RECT:
+ case PAD_TRAPEZOID:
+ {
+ wxPoint coords[4];
+ aPad->BuildPadPolygon( coords, wxSize( 0, 0 ), aPad->GetOrientation() );
+
+ SHAPE_CONVEX* shape = new SHAPE_CONVEX();
+ for( int ii = 0; ii < 4; ii++ )
+ {
+ shape->Append( wx_c + coords[ii] );
+ }
+
+ solid->SetShape( shape );
+ break;
+ }
+
+ default:
+ TRACEn( 0, "unsupported pad shape" );
+ delete solid;
+
+ return NULL;
+ }
}
}
=== modified file 'pcbnew/router/pns_solid.cpp'
--- pcbnew/router/pns_solid.cpp 2015-02-18 16:53:46 +0000
+++ pcbnew/router/pns_solid.cpp 2015-03-12 19:44:01 +0000
@@ -24,6 +24,7 @@
#include <geometry/shape_line_chain.h>
#include <geometry/shape_rect.h>
#include <geometry/shape_circle.h>
+#include <geometry/shape_convex.h>
#include "pns_solid.h"
#include "pns_utils.h"
@@ -54,6 +55,13 @@
return SegmentHull( *seg, aClearance, aWalkaroundThickness );
}
+ case SH_CONVEX:
+ {
+ SHAPE_CONVEX* convex = static_cast<SHAPE_CONVEX*>( m_shape );
+
+ return ConvexHull( *convex, cl );
+ }
+
default:
break;
}
=== modified file 'pcbnew/router/pns_utils.cpp'
--- pcbnew/router/pns_utils.cpp 2015-03-03 09:36:44 +0000
+++ pcbnew/router/pns_utils.cpp 2015-03-12 19:44:01 +0000
@@ -81,6 +81,74 @@
}
+static void MoveDiagonal( SEG& diagonal, const SHAPE_LINE_CHAIN& vertices, int clearance )
+{
+ int dist;
+
+ vertices.NearestPoint( diagonal, dist );
+ dist -= HULL_MARGIN;
+ VECTOR2I moveBy = (diagonal.A - diagonal.B).Perpendicular().Resize( dist - clearance );
+ diagonal.A += moveBy;
+ diagonal.B += moveBy;
+}
+
+
+const SHAPE_LINE_CHAIN ConvexHull( const SHAPE_CONVEX& convex, int clearance )
+{
+ // this defines the horizontal and vertical lines in the hull octagon
+ BOX2I box = convex.BBox( clearance + HULL_MARGIN );
+ box.Normalize();
+
+ SEG topline = SEG( VECTOR2I( box.GetX(), box.GetY() + box.GetHeight() ),
+ VECTOR2I( box.GetX() + box.GetWidth(), box.GetY() + box.GetHeight() ) );
+ SEG rightline = SEG( VECTOR2I( box.GetX() + box.GetWidth(), box.GetY() + box.GetHeight() ),
+ VECTOR2I( box.GetX() + box.GetWidth(), box.GetY() ) );
+ SEG bottomline = SEG( VECTOR2I( box.GetX() + box.GetWidth(), box.GetY() ),
+ box.GetOrigin() );
+ SEG leftline = SEG( box.GetOrigin(), VECTOR2I( box.GetX(), box.GetY() + box.GetHeight() ) );
+
+ const SHAPE_LINE_CHAIN& vertices = convex.Vertices();
+
+ // top right diagonal
+ VECTOR2I corner = box.GetOrigin() + box.GetSize();
+ SEG toprightline = SEG( corner,
+ corner + VECTOR2I( box.GetHeight(), -box.GetHeight() ) );
+ MoveDiagonal( toprightline, vertices, clearance );
+
+ // bottom right diagonal
+ corner = box.GetOrigin() + VECTOR2I( box.GetWidth(), 0 );
+ SEG bottomrightline = SEG( corner + VECTOR2I( box.GetHeight(), box.GetHeight() ),
+ corner );
+ MoveDiagonal( bottomrightline, vertices, clearance );
+
+ // bottom left diagonal
+ corner = box.GetOrigin();
+ SEG bottomleftline = SEG( corner,
+ corner + VECTOR2I( -box.GetHeight(), box.GetHeight() ) );
+ MoveDiagonal( bottomleftline, vertices, clearance );
+
+ // top left diagonal
+ corner = box.GetOrigin() + VECTOR2I( 0, box.GetHeight() );
+ SEG topleftline = SEG( corner + VECTOR2I( -box.GetHeight(), -box.GetHeight() ),
+ corner );
+ MoveDiagonal( topleftline, vertices, clearance );
+
+ SHAPE_LINE_CHAIN octagon;
+ octagon.SetClosed( true );
+
+ octagon.Append( leftline.IntersectLines( bottomleftline ).get() );
+ octagon.Append( bottomline.IntersectLines( bottomleftline ).get() );
+ octagon.Append( bottomline.IntersectLines( bottomrightline ).get() );
+ octagon.Append( rightline.IntersectLines( bottomrightline ).get() );
+ octagon.Append( rightline.IntersectLines( toprightline ).get() );
+ octagon.Append( topline.IntersectLines( toprightline ).get() );
+ octagon.Append( topline.IntersectLines( topleftline ).get() );
+ octagon.Append( leftline.IntersectLines( topleftline ).get() );
+
+ return octagon;
+}
+
+
SHAPE_RECT ApproximateSegmentAsRect( const SHAPE_SEGMENT& aSeg )
{
SHAPE_RECT r;
=== modified file 'pcbnew/router/pns_utils.h'
--- pcbnew/router/pns_utils.h 2015-02-18 16:53:46 +0000
+++ pcbnew/router/pns_utils.h 2015-03-12 19:44:01 +0000
@@ -26,6 +26,7 @@
#include <geometry/shape_line_chain.h>
#include <geometry/shape_segment.h>
#include <geometry/shape_rect.h>
+#include <geometry/shape_convex.h>
#define HULL_MARGIN 10
@@ -39,6 +40,16 @@
const SHAPE_LINE_CHAIN SegmentHull ( const SHAPE_SEGMENT& aSeg, int aClearance,
int aWalkaroundThickness );
+/**
+ * Function ConvexHull()
+ *
+ * Creates an octagonal hull around a convex polygon.
+ * @param convex The convex polygon.
+ * @param clearance The minimum distance between polygon and hull.
+ * @return A closed line chain describing the octagon.
+ */
+const SHAPE_LINE_CHAIN ConvexHull( const SHAPE_CONVEX& convex, int clearance );
+
SHAPE_RECT ApproximateSegmentAsRect( const SHAPE_SEGMENT& aSeg );
void DrawDebugPoint( VECTOR2I aP, int aColor );
=== modified file 'pcbnew/router/router_preview_item.cpp'
--- pcbnew/router/router_preview_item.cpp 2015-03-03 10:50:50 +0000
+++ pcbnew/router/router_preview_item.cpp 2015-03-12 19:44:01 +0000
@@ -18,9 +18,12 @@
* with this program. If not, see <http://www.gnu.org/licenses/>.
*/
+#include <deque>
+
#include <gal/color4d.h>
#include <geometry/shape_rect.h>
+#include <geometry/shape_convex.h>
#include "class_track.h"
#include <pcb_painter.h>
@@ -227,6 +230,28 @@
}
case SH_CONVEX:
+ {
+ const SHAPE_CONVEX* c = (const SHAPE_CONVEX*) m_shape;
+ std::deque<VECTOR2D> polygon = std::deque<VECTOR2D>();
+ for( int i = 0; i < c->PointCount(); i++ )
+ {
+ polygon.push_back( c->CDPoint( i ) );
+ }
+ aGal->DrawPolygon( polygon );
+
+ if( m_clearance > 0 )
+ {
+ aGal->SetLayerDepth( ClearanceOverlayDepth );
+ aGal->SetStrokeColor( COLOR4D( DARKDARKGRAY ) );
+ aGal->SetIsStroke( true );
+ aGal->SetLineWidth( 2 * m_clearance );
+ // need the implicit last segment to be explicit for DrawPolyline
+ polygon.push_back( c->CDPoint( 0 ) );
+ aGal->DrawPolyline( polygon );
+ }
+ break;
+ }
+
case SH_POLYGON:
case SH_COMPOUND:
break; // Not yet in use
