1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
|
/*
VeroRoute - Qt based Veroboard/Perfboard/PCB layout & routing application.
Copyright (C) 2017 Alex Lawrow ( dralx@users.sourceforge.net )
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 3 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, see <http://www.gnu.org/licenses/>.
*/
#pragma once
#include "Common.h"
#include "ConnectionMatrix.h"
#include "PolygonHelper.h"
// Builds a minimal spanning tree or daisy chain between a set of points
struct SpanningTreeHelper
{
typedef std::pair<QPointF, QPointF> LINE;
static inline void Build(const std::list<QPointF>& pointsIn, std::list<LINE>& linesOut, bool bDaisyChain = false)
{
typedef std::pair<size_t, size_t> INDICES;
typedef std::pair<INDICES, qreal> EDGE;
linesOut.clear();
const size_t N = pointsIn.size();
if ( N < 2 ) return;
std::vector<size_t> nConn; nConn.resize(N,0); // Number of direct connections to each point (for daisy chain algorithm)
std::vector<QPointF> v; v.resize(N); // Points stored as a vector (for access via index)
size_t i(0);
for (const auto& o: pointsIn) v[i++] = o;
std::list<EDGE> edges; // Working list of edges
for (size_t i = 0; i < N; i++)
for (size_t j = i + 1; j < N; j++)
edges.push_back( EDGE(INDICES(i,j), PolygonHelper::Length(v[i] - v[j])) );
ConnectionMatrix matrix; // Helper for tracking connectivity between points
matrix.Allocate(N);
while ( linesOut.size() < N-1 )
{
qreal Dmin(DBL_MAX);
auto iterBest = edges.begin(); // The shortest edge that does not make an unnecessary connection
for (auto iter = iterBest, iterEnd = edges.end(); iter != iterEnd; ++iter)
{
const INDICES& ij = iter->first;
const qreal& D = iter->second;
if ( D > Dmin || matrix.GetAreConnected(ij.first, ij.second) ) continue;
if ( bDaisyChain && (nConn[ij.first] > 1 || nConn[ij.second] > 1) ) continue;
iterBest = iter;
Dmin = D;
}
const INDICES& ij = iterBest->first;
linesOut.push_back( LINE(v[ij.first], v[ij.second]) ); // Add best to output list
matrix.Connect(ij.first, ij.second); // Update connection matrix
nConn[ij.first]++; nConn[ij.second]++; // Update number of direct connections
edges.erase(iterBest); // Remove best from the working list
}
}
typedef std::pair<QPointF, unsigned int> AIRWIRE_POINT; // unsigned int holds the Route ID for the point
typedef std::pair<AIRWIRE_POINT, AIRWIRE_POINT> AIRWIRE_LINE;
static inline void BuildAirWires(const std::list<AIRWIRE_POINT>& pointsIn, std::list<AIRWIRE_LINE>& linesOut)
{
typedef std::pair<AIRWIRE_LINE, qreal> AIRWIRE_EDGE; // qreal holds the length of the AIRWIRE_LINE
linesOut.clear();
const size_t N = pointsIn.size();
if ( N < 2 ) return;
std::vector<AIRWIRE_POINT> v; v.resize(N); // Points stored as a vector (for access via index)
size_t i(0);
for (const auto& o: pointsIn) v[i++] = o;
std::unordered_map<size_t, size_t> mapRIDtoIndex; // Map Route IDs to consecutive indexes 0,1,2,... so we can use a ConnectionMatrix
size_t index(0); // For populating mapRIDtoIndex
std::list<AIRWIRE_EDGE> edges; // Working list of edges. An edge is an AIRWIRE_LINE plus its calculated length.
for (size_t i = 0; i < N; i++)
for (size_t j = i + 1; j < N; j++)
{
const unsigned int& RID_i = v[i].second;
const unsigned int& RID_j = v[j].second;
if ( RID_i != RID_j ) // Endpoints of edge must have different route IDs
{
edges.push_back( AIRWIRE_EDGE( AIRWIRE_LINE(v[i], v[j]), PolygonHelper::Length(v[i].first - v[j].first) ) );
// Update map of RID to indexes 0,1,2, ...
if ( mapRIDtoIndex.find(RID_i) == mapRIDtoIndex.end() ) mapRIDtoIndex[RID_i] = index++;
if ( mapRIDtoIndex.find(RID_j) == mapRIDtoIndex.end() ) mapRIDtoIndex[RID_j] = index++;
}
}
const size_t numRIDs = mapRIDtoIndex.size(); // Number of unique route IDs
if ( numRIDs < 2 ) return;
ConnectionMatrix matrix; // Helper for tracking connectivity between points
matrix.Allocate(numRIDs);
while ( linesOut.size() < numRIDs-1 )
{
qreal Dmin(DBL_MAX);
auto iterBest = edges.begin(); // The shortest edge that does not make an unnecessary connection
for (auto iter = iterBest, iterEnd = edges.end(); iter != iterEnd; ++iter)
{
const AIRWIRE_LINE& line_ij = iter->first;
const unsigned int& RID_i = line_ij.first.second;
const unsigned int& RID_j = line_ij.second.second;
const qreal& D = iter->second;
if ( D > Dmin || matrix.GetAreConnected(mapRIDtoIndex[RID_i], mapRIDtoIndex[RID_j]) ) continue;
iterBest = iter;
Dmin = D;
}
const AIRWIRE_LINE& line_ij = iterBest->first;
const unsigned int& RID_i = line_ij.first.second;
const unsigned int& RID_j = line_ij.second.second;
linesOut.push_back( line_ij ); // Add best line to linesOut
matrix.Connect(mapRIDtoIndex[RID_i], mapRIDtoIndex[RID_j]); // Update connection matrix
edges.erase(iterBest); // Remove best from the working list
}
}
SpanningTreeHelper() { assert( true || PreventBuildWarnings() ); }
private:
bool PreventBuildWarnings() const
{
std::list<QPointF> inA;
std::list<LINE> outA;
std::list<AIRWIRE_POINT> inB;
std::list<AIRWIRE_LINE> outB;
Build(inA, outA);
BuildAirWires(inB, outB);
return true;
}
};
|
