Horizon
pns_optimizer.h
1/*
2 * KiRouter - a push-and-(sometimes-)shove PCB router
3 *
4 * Copyright (C) 2013-2014 CERN
5 * Copyright (C) 2016 KiCad Developers, see AUTHORS.txt for contributors.
6 * Author: Tomasz Wlostowski <tomasz.wlostowski@cern.ch>
7 *
8 * This program is free software: you can redistribute it and/or modify it
9 * under the terms of the GNU General Public License as published by the
10 * Free Software Foundation, either version 3 of the License, or (at your
11 * option) any later version.
12 *
13 * This program is distributed in the hope that it will be useful, but
14 * WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * General Public License for more details.
17 *
18 * You should have received a copy of the GNU General Public License along
19 * with this program. If not, see <http://www.gnu.org/licenses/>.
20 */
21
22#ifndef __PNS_OPTIMIZER_H
23#define __PNS_OPTIMIZER_H
24
25#include <unordered_map>
26#include <memory>
27
28#include <geometry/shape_index_list.h>
29#include <geometry/shape_line_chain.h>
30
31#include "range.h"
32
33namespace PNS {
34
35class NODE;
36class ROUTER;
37class LINE;
38class DIFF_PAIR;
39
46{
47public:
49 m_lengthCost( 0 ),
50 m_cornerCost( 0 )
51 {}
52
53 COST_ESTIMATOR( const COST_ESTIMATOR& aB ) :
54 m_lengthCost( aB.m_lengthCost ),
55 m_cornerCost( aB.m_cornerCost )
56 {}
57
58 ~COST_ESTIMATOR() {};
59
60 static int CornerCost( const SEG& aA, const SEG& aB );
61 static int CornerCost( const SHAPE_LINE_CHAIN& aLine );
62 static int CornerCost( const LINE& aLine );
63
64 void Add( LINE& aLine );
65 void Remove( LINE& aLine );
66 void Replace( LINE& aOldLine, LINE& aNewLine );
67
68 bool IsBetter( COST_ESTIMATOR& aOther, double aLengthTolerance,
69 double aCornerTollerace ) const;
70
71 double GetLengthCost() const { return m_lengthCost; }
72 double GetCornerCost() const { return m_cornerCost; }
73
74private:
75 double m_lengthCost;
76 int m_cornerCost;
77};
78
91{
92public:
93 enum OptimizationEffort
94 {
95 MERGE_SEGMENTS = 0x01,
96 SMART_PADS = 0x02,
97 MERGE_OBTUSE = 0x04,
98 FANOUT_CLEANUP = 0x08
99 };
100
101 OPTIMIZER( NODE* aWorld );
102 ~OPTIMIZER();
103
105 static bool Optimize( LINE* aLine, int aEffortLevel, NODE* aWorld);
106
107 bool Optimize( LINE* aLine, LINE* aResult = NULL );
108 bool Optimize( DIFF_PAIR* aPair );
109
110
111 void SetWorld( NODE* aNode ) { m_world = aNode; }
112 void CacheStaticItem( ITEM* aItem );
113 void CacheRemove( ITEM* aItem );
114 void ClearCache( bool aStaticOnly = false );
115
116 void SetCollisionMask( int aMask )
117 {
118 m_collisionKindMask = aMask;
119 }
120
121 void SetEffortLevel( int aEffort )
122 {
123 m_effortLevel = aEffort;
124 }
125
126
127 void SetRestrictArea( const BOX2I& aArea )
128 {
129 m_restrictArea = aArea;
130 m_restrictAreaActive = true;
131 }
132
133private:
134 static const int MaxCachedItems = 256;
135
136 typedef std::vector<SHAPE_LINE_CHAIN> BREAKOUT_LIST;
137
138 struct CACHE_VISITOR;
139
140 struct CACHED_ITEM
141 {
142 int m_hits;
143 bool m_isStatic;
144 };
145
146 bool mergeObtuse( LINE* aLine );
147 bool mergeFull( LINE* aLine );
148 bool removeUglyCorners( LINE* aLine );
149 bool runSmartPads( LINE* aLine );
150 bool mergeStep( LINE* aLine, SHAPE_LINE_CHAIN& aCurrentLine, int step );
151 bool fanoutCleanup( LINE * aLine );
152 bool mergeDpSegments( DIFF_PAIR *aPair );
153 bool mergeDpStep( DIFF_PAIR *aPair, bool aTryP, int step );
154
155 bool checkColliding( ITEM* aItem, bool aUpdateCache = true );
156 bool checkColliding( LINE* aLine, const SHAPE_LINE_CHAIN& aOptPath );
157
158 void cacheAdd( ITEM* aItem, bool aIsStatic );
159 void removeCachedSegments( LINE* aLine, int aStartVertex = 0, int aEndVertex = -1 );
160
161 BREAKOUT_LIST circleBreakouts( int aWidth, const SHAPE* aShape, bool aPermitDiagonal ) const;
162 BREAKOUT_LIST rectBreakouts( int aWidth, const SHAPE* aShape, bool aPermitDiagonal ) const;
163 BREAKOUT_LIST ovalBreakouts( int aWidth, const SHAPE* aShape, bool aPermitDiagonal ) const;
164 BREAKOUT_LIST customBreakouts( int aWidth, const ITEM* aItem, bool aPermitDiagonal ) const;
165 BREAKOUT_LIST computeBreakouts( int aWidth, const ITEM* aItem, bool aPermitDiagonal ) const;
166
167 int smartPadsSingle( LINE* aLine, ITEM* aPad, bool aEnd, int aEndVertex );
168
169 ITEM* findPadOrVia( int aLayer, int aNet, const VECTOR2I& aP ) const;
170
172
173 typedef std::unordered_map<ITEM*, CACHED_ITEM> CachedItemTags;
174 CachedItemTags m_cacheTags;
175 NODE* m_world;
176 int m_collisionKindMask;
177 int m_effortLevel;
178 bool m_keepPostures;
179
180 BOX2I m_restrictArea;
181 bool m_restrictAreaActive;
182};
183
184}
185
186#endif
Class COST_ESTIMATOR.
Definition: pns_optimizer.h:46
static int CornerCost(const SEG &aA, const SEG &aB)
Cost Estimator Methods.
Definition: pns_optimizer.cpp:41
Class DIFF_PAIR.
Definition: pns_diff_pair.h:265
Class ITEM.
Definition: pns_item.h:55
Definition: pns_line.h:61
Class NODE.
Definition: pns_node.h:138
Class OPTIMIZER.
Definition: pns_optimizer.h:91
static bool Optimize(LINE *aLine, int aEffortLevel, NODE *aWorld)
‍a quick shortcut to optmize a line without creating and setting up an optimizer
Definition: pns_optimizer.cpp:969
OPTIMIZER(NODE *aWorld)
Optimizer.
Definition: pns_optimizer.cpp:126
Definition: seg.h:37
Definition: shape_index_list.h:36
Class SHAPE_LINE_CHAIN.
Definition: shape_line_chain.h:50
Class SHAPE.
Definition: shape.h:59
Definition: pns_optimizer.cpp:142