KiCad PCB EDA Suite
Loading...
Searching...
No Matches
sch_io_wire_detour.cpp
Go to the documentation of this file.
1/*
2 * This program source code file is part of KiCad, a free EDA CAD application.
3 *
4 * Copyright The KiCad Developers, see AUTHORS.txt for contributors.
5 *
6 * This program is free software: you can redistribute it and/or modify it
7 * under the terms of the GNU General Public License as published by the
8 * Free Software Foundation, either version 3 of the License, or (at your option)
9 * any later version.
10 *
11 * This program is distributed in the hope that it will be useful, but
12 * WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program. If not, see <https://www.gnu.org/licenses/>.
18 */
19
20#include "sch_io_wire_detour.h"
21
22#include <algorithm>
23
24#include <base_units.h>
25
26namespace
27{
28bool strictlyInside( const SEG& aSeg, const VECTOR2I& aPt )
29{
30 return aPt != aSeg.A && aPt != aSeg.B && aSeg.Contains( aPt );
31}
32} // namespace
33
34
35void SCH_IO_WIRE_DETOUR::AddWire( const SEG& aWire, int aNet )
36{
37 m_wires.push_back( { aWire, aNet } );
38}
39
40
41void SCH_IO_WIRE_DETOUR::AddContact( const VECTOR2I& aPos, int aNet )
42{
43 m_contacts.push_back( { aPos, aNet } );
44}
45
46
47std::vector<SCH_IO_WIRE_DETOUR::CONTACT> SCH_IO_WIRE_DETOUR::contacts() const
48{
49 std::vector<CONTACT> all = m_contacts;
50
51 for( const WIRE& wire : m_wires )
52 {
53 all.push_back( { wire.Seg.A, wire.Net } );
54 all.push_back( { wire.Seg.B, wire.Net } );
55 }
56
57 return all;
58}
59
60
61bool SCH_IO_WIRE_DETOUR::TouchesOtherNet( const VECTOR2I& aPos, int aNet ) const
62{
63 for( const CONTACT& contact : contacts() )
64 {
65 if( contact.Net != aNet && contact.Pos == aPos )
66 return true;
67 }
68
69 return false;
70}
71
72
73bool SCH_IO_WIRE_DETOUR::joinsOtherNet( const SEG& aPiece, const SEG& aWire, int aNet,
74 const std::vector<CONTACT>& aContacts ) const
75{
76 // Whatever the wire already touches at its own ends is not made worse by a detour
77 auto atWireEnd = [&]( const VECTOR2I& aPt )
78 {
79 return aPt == aWire.A || aPt == aWire.B;
80 };
81
82 for( const CONTACT& contact : aContacts )
83 {
84 if( contact.Net != aNet && !atWireEnd( contact.Pos ) && aPiece.Contains( contact.Pos ) )
85 return true;
86 }
87
88 for( const WIRE& wire : m_wires )
89 {
90 if( wire.Net == aNet )
91 continue;
92
93 if( ( !atWireEnd( aPiece.A ) && wire.Seg.Contains( aPiece.A ) )
94 || ( !atWireEnd( aPiece.B ) && wire.Seg.Contains( aPiece.B ) ) )
95 {
96 return true;
97 }
98 }
99
100 return false;
101}
102
103
104std::vector<SEG> SCH_IO_WIRE_DETOUR::detour( const SEG& aWire, const VECTOR2I& aEnter, const VECTOR2I& aLeave,
105 int aNet, const std::vector<CONTACT>& aContacts ) const
106{
107 const int step = schIUScale.MilsToIU( 50 );
108 const VECTOR2I normal = ( aWire.B - aWire.A ).Perpendicular().Resize( step );
109 const SEG replaced( aEnter, aLeave );
110
111 // A branch of this net on the replaced stretch would be left hanging
112 for( const CONTACT& contact : aContacts )
113 {
114 if( contact.Net == aNet && strictlyInside( replaced, contact.Pos ) )
115 return {};
116 }
117
118 std::vector<SEG> best;
119 int bestCrossings = 0;
120
121 for( int mult : { 1, -1, 2, -2, 3, -3 } )
122 {
123 const VECTOR2I enterOff = aEnter + normal * mult;
124 const VECTOR2I leaveOff = aLeave + normal * mult;
125 const SEG pieces[] = { SEG( aEnter, enterOff ), SEG( enterOff, leaveOff ), SEG( leaveOff, aLeave ) };
126
127 if( std::any_of( std::begin( pieces ), std::end( pieces ),
128 [&]( const SEG& aPiece )
129 {
130 return joinsOtherNet( aPiece, aWire, aNet, aContacts );
131 } ) )
132 {
133 continue;
134 }
135
136 // Prefer the side where the detour crosses the fewest other wires
137 int crossings = 0;
138
139 for( const WIRE& wire : m_wires )
140 {
141 if( wire.Net == aNet )
142 continue;
143
144 for( const SEG& piece : pieces )
145 {
146 if( piece.Intersect( wire.Seg, true ) )
147 crossings++;
148 }
149 }
150
151 if( best.empty() || crossings < bestCrossings )
152 {
153 best.assign( std::begin( pieces ), std::end( pieces ) );
154 bestCrossings = crossings;
155 }
156 }
157
158 return best;
159}
160
161
163{
164 const int step = schIUScale.MilsToIU( 50 );
165
167 const std::vector<CONTACT> all = contacts();
168
169 std::vector<VECTOR2I> foreign;
170
171 for( const CONTACT& contact : all )
172 {
173 if( contact.Net != aNet && strictlyInside( aWire, contact.Pos )
174 && std::find( foreign.begin(), foreign.end(), contact.Pos ) == foreign.end() )
175 {
176 foreign.push_back( contact.Pos );
177 }
178 }
179
180 auto replaceRegistered =
181 [&]()
182 {
183 std::erase_if( m_wires,
184 [&]( const WIRE& aEntry )
185 {
186 return aEntry.Net == aNet && aEntry.Seg == aWire;
187 } );
188
189 for( const SEG& piece : result.Pieces )
190 AddWire( piece, aNet );
191 };
192
193 if( foreign.empty() )
194 {
195 result.Pieces = { aWire };
196 replaceRegistered();
197 return result;
198 }
199
200 // Anchors on a diagonal cannot be placed exactly on the wire, which would detach contacts from it
201 if( aWire.A.x != aWire.B.x && aWire.A.y != aWire.B.y )
202 {
203 result.Pieces = { aWire };
204 result.Failed = true;
205 replaceRegistered();
206 return result;
207 }
208
209 const VECTOR2I along = aWire.B - aWire.A;
210 const VECTOR2I stepVec = along.Resize( step );
211
212 std::sort( foreign.begin(), foreign.end(),
213 [&]( const VECTOR2I& a, const VECTOR2I& b )
214 {
215 return ( a - aWire.A ).SquaredEuclideanNorm() < ( b - aWire.A ).SquaredEuclideanNorm();
216 } );
217
218 auto alongWire = [&]( const VECTOR2I& aPt )
219 {
220 return ( aPt - aWire.A ).Dot( along );
221 };
222
223 // A branch of this net joins the wire here, so a detour has to end there rather than pass it
224 std::vector<VECTOR2I> branches;
225
226 for( const CONTACT& contact : all )
227 {
228 if( contact.Net == aNet && strictlyInside( aWire, contact.Pos ) )
229 branches.push_back( contact.Pos );
230 }
231
232 auto branchBetween = [&]( const VECTOR2I& aFrom, const VECTOR2I& aTo )
233 {
234 return std::any_of( branches.begin(), branches.end(),
235 [&]( const VECTOR2I& aPt )
236 {
237 return alongWire( aPt ) > alongWire( aFrom ) && alongWire( aPt ) < alongWire( aTo );
238 } );
239 };
240
241 // Items close together share one detour
242 std::vector<std::pair<VECTOR2I, VECTOR2I>> clusters;
243
244 for( const VECTOR2I& pt : foreign )
245 {
246 if( !clusters.empty() && ( pt - clusters.back().second ).EuclideanNorm() <= 3 * step
247 && !branchBetween( clusters.back().second, pt ) )
248 {
249 clusters.back().second = pt;
250 }
251 else
252 {
253 clusters.emplace_back( pt, pt );
254 }
255 }
256
257 std::vector<VECTOR2I> path{ aWire.A };
258
259 for( const auto& [first, last] : clusters )
260 {
261 VECTOR2I enter = first - stepVec;
262 VECTOR2I leave = last + stepVec;
263
264 if( alongWire( enter ) < 0 )
265 enter = aWire.A;
266
267 if( alongWire( leave ) > alongWire( aWire.B ) )
268 leave = aWire.B;
269
270 for( const VECTOR2I& branch : branches )
271 {
272 if( alongWire( branch ) > alongWire( enter ) && alongWire( branch ) < alongWire( first ) )
273 enter = branch;
274
275 if( alongWire( branch ) < alongWire( leave ) && alongWire( branch ) > alongWire( last ) )
276 leave = branch;
277 }
278
279 std::vector<SEG> pieces = detour( aWire, enter, leave, aNet, all );
280
281 if( pieces.empty() )
282 {
283 result.Failed = true;
284 continue;
285 }
286
287 for( const VECTOR2I& pt : { pieces[0].A, pieces[0].B, pieces[1].B, pieces[2].B } )
288 {
289 if( pt != path.back() )
290 path.push_back( pt );
291 }
292 }
293
294 if( aWire.B != path.back() )
295 path.push_back( aWire.B );
296
297 for( size_t i = 1; i < path.size(); i++ )
298 result.Pieces.emplace_back( path[i - 1], path[i] );
299
300 // Every contact of this net on the wire has to stay exactly on it
301 for( const VECTOR2I& branch : branches )
302 {
303 if( std::none_of( result.Pieces.begin(), result.Pieces.end(),
304 [&]( const SEG& aPiece )
305 {
306 return aPiece.Contains( branch );
307 } ) )
308 {
309 result.Pieces = { aWire };
310 result.Failed = true;
311 break;
312 }
313 }
314
315 replaceRegistered();
316
317 return result;
318}
constexpr EDA_IU_SCALE schIUScale
Definition base_units.h:130
std::vector< WIRE > m_wires
std::vector< CONTACT > m_contacts
void AddContact(const VECTOR2I &aPos, int aNet)
Register a pin or junction.
RESULT Route(const SEG &aWire, int aNet)
Detour a wire around foreign items lying on it and register the result as the wire's geometry.
void AddWire(const SEG &aWire, int aNet)
Register a wire as an obstacle for the wires of other nets.
bool TouchesOtherNet(const VECTOR2I &aPos, int aNet) const
bool joinsOtherNet(const SEG &aPiece, const SEG &aWire, int aNet, const std::vector< CONTACT > &aContacts) const
True if a detour piece would join another net.
std::vector< CONTACT > contacts() const
std::vector< SEG > detour(const SEG &aWire, const VECTOR2I &aEnter, const VECTOR2I &aLeave, int aNet, const std::vector< CONTACT > &aContacts) const
Detour the stretch of a wire between two points, or an empty vector if there is no safe place for it.
Definition seg.h:38
VECTOR2I A
Definition seg.h:45
VECTOR2I B
Definition seg.h:46
bool Contains(const SEG &aSeg) const
Definition seg.h:342
VECTOR2< T > Resize(T aNewLength) const
Return a vector of the same direction, but length specified in aNewLength.
Definition vector2d.h:406
std::string path
wxString result
Test unit parsing edge cases and error handling.
VECTOR2< int32_t > VECTOR2I
Definition vector2d.h:708