Horizon
pns_shove.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_SHOVE_H
23 #define __PNS_SHOVE_H
24 
25 #include <vector>
26 #include <stack>
27 
28 #include "pns_optimizer.h"
29 #include "pns_routing_settings.h"
30 #include "pns_algo_base.h"
31 #include "pns_logger.h"
32 #include "range.h"
33 
34 namespace PNS {
35 
36 class LINE;
37 class NODE;
38 class ROUTER;
39 
46 class SHOVE : public ALGO_BASE
47 {
48 public:
49 
50  enum SHOVE_STATUS
51  {
52  SH_OK = 0,
53  SH_NULL,
54  SH_INCOMPLETE,
55  SH_HEAD_MODIFIED,
56  SH_TRY_WALK
57  };
58 
59  SHOVE( NODE* aWorld, ROUTER* aRouter );
60  ~SHOVE();
61 
62  virtual LOGGER* Logger() override
63  {
64  return &m_logger;
65  }
66 
67  SHOVE_STATUS ShoveLines( const LINE& aCurrentHead );
68  SHOVE_STATUS ShoveMultiLines( const ITEM_SET& aHeadSet );
69 
70  SHOVE_STATUS ShoveDraggingVia( VIA* aVia, const VECTOR2I& aWhere, VIA** aNewVia );
71  SHOVE_STATUS ProcessSingleLine( LINE& aCurrent, LINE& aObstacle,
72  LINE& aShoved );
73 
74  void ForceClearance ( bool aEnabled, int aClearance )
75  {
76  if( aEnabled )
77  m_forceClearance = aClearance;
78  else
79  m_forceClearance = -1;
80  }
81 
82  NODE* CurrentNode();
83 
84  const LINE NewHead() const;
85 
86  void SetInitialLine( LINE& aInitial );
87 
88 private:
89  typedef std::vector<SHAPE_LINE_CHAIN> HULL_SET;
90  typedef OPT<LINE> OPT_LINE;
91  typedef std::pair<LINE, LINE> LINE_PAIR;
92  typedef std::vector<LINE_PAIR> LINE_PAIR_VEC;
93 
94  struct SPRINGBACK_TAG
95  {
96  int64_t m_length;
97  int m_segments;
98  VECTOR2I m_p;
99  NODE* m_node;
100  ITEM_SET m_headItems;
101  COST_ESTIMATOR m_cost;
102  OPT_BOX2I m_affectedArea;
103  };
104 
105  SHOVE_STATUS processHullSet( LINE& aCurrent, LINE& aObstacle,
106  LINE& aShoved, const HULL_SET& hulls );
107 
108  bool reduceSpringback( const ITEM_SET& aHeadItems );
109  bool pushSpringback( NODE* aNode, const ITEM_SET& aHeadItems,
110  const COST_ESTIMATOR& aCost, const OPT_BOX2I& aAffectedArea );
111 
112  SHOVE_STATUS walkaroundLoneVia( LINE& aCurrent, LINE& aObstacle, LINE& aShoved );
113  bool checkBumpDirection( const LINE& aCurrent, const LINE& aShoved ) const;
114 
115  SHOVE_STATUS onCollidingLine( LINE& aCurrent, LINE& aObstacle );
116  SHOVE_STATUS onCollidingSegment( LINE& aCurrent, SEGMENT* aObstacleSeg );
117  SHOVE_STATUS onCollidingSolid( LINE& aCurrent, ITEM* aObstacle );
118  SHOVE_STATUS onCollidingVia( ITEM* aCurrent, VIA* aObstacleVia );
119  SHOVE_STATUS onReverseCollidingVia( LINE& aCurrent, VIA* aObstacleVia );
120  SHOVE_STATUS pushVia( VIA* aVia, const VECTOR2I& aForce, int aCurrentRank, bool aDryRun = false );
121 
122  OPT_BOX2I totalAffectedArea() const;
123 
124  void unwindStack( SEGMENT* aSeg );
125  void unwindStack( ITEM* aItem );
126 
127  void runOptimizer( NODE* aNode );
128 
129  bool pushLine( const LINE& aL, bool aKeepCurrentOnTop = false );
130  void popLine();
131 
132  LINE assembleLine( const SEGMENT* aSeg, int* aIndex = NULL );
133 
134  void replaceItems( ITEM* aOld, std::unique_ptr< ITEM > aNew );
135  void replaceLine( LINE& aOld, LINE& aNew );
136 
137  OPT_BOX2I m_affectedAreaSum;
138 
139  SHOVE_STATUS shoveIteration( int aIter );
140  SHOVE_STATUS shoveMainLoop();
141 
142  int getClearance( const ITEM* aA, const ITEM* aB ) const;
143 
144  std::vector<SPRINGBACK_TAG> m_nodeStack;
145  std::vector<LINE> m_lineStack;
146  std::vector<LINE> m_optimizerQueue;
147 
148  NODE* m_root;
149  NODE* m_currentNode;
150 
151  OPT_LINE m_newHead;
152 
153  LOGGER m_logger;
154  VIA* m_draggedVia;
155  ITEM_SET m_draggedViaHeadSet;
156 
157  int m_iter;
158  int m_forceClearance;
159  bool m_multiLineMode;
160  void sanityCheck( LINE* aOld, LINE* aNew );
161 };
162 
163 }
164 
165 #endif // __PNS_SHOVE_H
PNS::LINE
Definition: pns_line.h:61
PNS::SHOVE::Logger
virtual LOGGER * Logger() override
Returns the logger object, allowing to dump geometry to a file.
Definition: pns_shove.h:62
VECTOR2
Class VECTOR2 defines a general 2D-vector/point.
Definition: vector2d.h:76
PNS::VIA
Definition: pns_via.h:38
PNS::LOGGER
Definition: pns_logger.h:40
libzip::int64_t
zip_int64_t int64_t
zip_int64_t typedef.
Definition: zip.hpp:103
PNS::ITEM_SET
Definition: pns_itemset.h:40