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 _______________________________________________ Mailing list: https://launchpad.net/~kicad-developers Post to : kicad-developers@lists.launchpad.net Unsubscribe : https://launchpad.net/~kicad-developers More help : https://help.launchpad.net/ListHelp