1 /*******************************************************************
2
3 Part of the Fritzing project - http://fritzing.org
4 Copyright (c) 2007-2014 Fachhochschule Potsdam - http://fh-potsdam.de
5
6 Fritzing is free software: you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation, either version 3 of the License, orF
9 (at your option) any later version.
10
11 Fritzing is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with Fritzing. If not, see <http://www.gnu.org/licenses/>.
18
19 ********************************************************************
20
21 $Revision: 6941 $:
22 $Author: irascibl@gmail.com $:
23 $Date: 2013-03-26 15:03:18 +0100 (Di, 26. Mrz 2013) $
24
25 ********************************************************************/
26
27 #include "groundplanegenerator.h"
28 #include "svgfilesplitter.h"
29 #include "../fsvgrenderer.h"
30 #include "../debugdialog.h"
31 #include "../version/version.h"
32 #include "../utils/folderutils.h"
33 #include "../utils/graphicsutils.h"
34 #include "../utils/textutils.h"
35 #include "../items/wire.h"
36 #include "../processeventblocker.h"
37 #include "../autoroute/drc.h"
38
39 #include <QBitArray>
40 #include <QPainter>
41 #include <QSvgRenderer>
42 #include <QDate>
43 #include <QTextStream>
44 #include <qmath.h>
45 #include <limits>
46 #include <QtConcurrentRun>
47
48 static const double BORDERINCHES = 0.04;
49
50 const QString GroundPlaneGenerator::KeepoutSettingName("GPG_Keepout");
51 const double GroundPlaneGenerator::KeepoutDefaultMils = 10;
52
OFFSET(int x,int y,QImage * image)53 inline int OFFSET(int x, int y, QImage * image) { return (y * image->width()) + x; }
54
55 QString GroundPlaneGenerator::ConnectorName = "connector0pad";
56
57 // !!!!!!!!!!!!!!!!!!!
58 // !!!!!!!!!!!!!!!!!!! IMPORTANT NOTE: QRect::right() and QRect::bottom() are off by one--this is a known Qt problem
59 // !!!!!!!!!!!!!!!!!!!
60 // !!!!!!!!!!!!!!!!!!! one workaround might be to switch to QRectF
61 // !!!!!!!!!!!!!!!!!!!
62
GroundPlaneGenerator()63 GroundPlaneGenerator::GroundPlaneGenerator()
64 {
65 m_strokeWidthIncrement = 0;
66 m_minRiseSize = m_minRunSize = 1;
67 }
68
~GroundPlaneGenerator()69 GroundPlaneGenerator::~GroundPlaneGenerator() {
70 }
71
getBoardRects(const QByteArray & boardByteArray,QGraphicsItem * board,double res,double keepoutSpace,QList<QRect> & rects)72 bool GroundPlaneGenerator::getBoardRects(const QByteArray & boardByteArray, QGraphicsItem * board, double res, double keepoutSpace, QList<QRect> & rects)
73 {
74
75 QRectF br = board->sceneBoundingRect();
76 double bWidth = res * br.width() / GraphicsUtils::SVGDPI;
77 double bHeight = res * br.height() / GraphicsUtils::SVGDPI;
78 QImage image(bWidth, bHeight, QImage::Format_Mono);
79 image.setDotsPerMeterX(res * GraphicsUtils::InchesPerMeter);
80 image.setDotsPerMeterY(res * GraphicsUtils::InchesPerMeter);
81 image.fill(0xffffffff);
82
83 QSvgRenderer renderer(boardByteArray);
84 QPainter painter;
85 painter.begin(&image);
86 painter.setRenderHint(QPainter::Antialiasing, false);
87 renderer.render(&painter);
88 painter.end();
89
90 #ifndef QT_NO_DEBUG
91 image.save(FolderUtils::getUserDataStorePath("") + "/getBoardRects.png");
92 #endif
93
94 QColor keepaway(255,255,255);
95
96 // now add keepout area to the border
97 QImage image2 = image.copy();
98 painter.begin(&image2);
99 painter.setRenderHint(QPainter::Antialiasing, false);
100 painter.fillRect(0, 0, image2.width(), keepoutSpace, keepaway);
101 painter.fillRect(0, image2.height() - keepoutSpace, image2.width(), keepoutSpace, keepaway);
102 painter.fillRect(0, 0, keepoutSpace, image2.height(), keepaway);
103 painter.fillRect(image2.width() - keepoutSpace, 0, keepoutSpace, image2.height(), keepaway);
104
105 for (int y = 0; y < image.height(); y++) {
106 for (int x = 0; x < image.width(); x++) {
107 QRgb current = image.pixel(x, y);
108 if (current != 0xffffffff) {
109 continue;
110 }
111
112 painter.fillRect(x - keepoutSpace, y - keepoutSpace, keepoutSpace + keepoutSpace, keepoutSpace + keepoutSpace, keepaway);
113 }
114 }
115 painter.end();
116
117 #ifndef QT_NO_DEBUG
118 image2.save(FolderUtils::getUserDataStorePath("") + "/getBoardRects2.png");
119 #endif
120
121 scanLines(image2, bWidth, bHeight, rects);
122
123 // combine parallel equal-sized rects
124 int ix = 0;
125 while (ix < rects.count()) {
126 QRect r = rects.at(ix++);
127 for (int j = ix; j < rects.count(); j++) {
128 QRect s = rects.at(j);
129 if (s.bottom() == r.bottom()) {
130 // on same row; keep going
131 continue;
132 }
133
134 if (s.top() > r.bottom() + 1) {
135 // skipped row, can't join
136 break;
137 }
138
139 if (s.left() == r.left() && s.right() == r.right()) {
140 // join these
141 r.setBottom(s.bottom());
142 rects.removeAt(j);
143 ix--;
144 rects.replace(ix, r);
145 break;
146 }
147 }
148 }
149
150 return true;
151 }
152
generateGroundPlaneUnit(const QString & boardSvg,QSizeF boardImageSize,const QString & svg,QSizeF copperImageSize,QStringList & exceptions,QGraphicsItem * board,double res,const QString & color,QPointF whereToStart,double keepoutMils)153 bool GroundPlaneGenerator::generateGroundPlaneUnit(const QString & boardSvg, QSizeF boardImageSize, const QString & svg, QSizeF copperImageSize,
154 QStringList & exceptions, QGraphicsItem * board, double res, const QString & color,
155 QPointF whereToStart, double keepoutMils)
156 {
157 GPGParams params;
158 params.boardSvg = boardSvg;
159 params.boardImageSize = boardImageSize;
160 params.svg = svg;
161 params.copperImageSize = copperImageSize;
162 params.exceptions = exceptions;
163 params.board = board;
164 params.res = res;
165 params.color = color;
166 params.keepoutMils = keepoutMils;
167
168 double bWidth, bHeight;
169 QList<QRectF> rects;
170 QImage * image = generateGroundPlaneAux(params, bWidth, bHeight, rects);
171 if (image == NULL) return false;
172
173 QRectF bsbr = board->sceneBoundingRect();
174
175 QPoint s(qRound(res * (whereToStart.x() - bsbr.topLeft().x()) / GraphicsUtils::SVGDPI),
176 qRound(res * (whereToStart.y() - bsbr.topLeft().y()) / GraphicsUtils::SVGDPI));
177
178 QBitArray redMarker(image->height() * image->width(), false);
179
180 QRgb pixel = image->pixel(s);
181 //DebugDialog::debug(QString("unit %1").arg(pixel, 0, 16));
182 if (pixel != 0xffffffff) {
183 // starting off in bad territory
184 delete image;
185 return false;
186 }
187
188 // step 1 flood fill white to "red" (keep max locations)
189
190 int minY = image->height();
191 int maxY = 0;
192 int minX = image->width();
193 int maxX = 0;
194 QList<QPoint> stack;
195 stack << s;
196 while (stack.count() > 0) {
197 QPoint p = stack.takeFirst();
198
199 if (p.x() < 0) continue;
200 if (p.y() < 0) continue;
201 if (p.x() >= image->width()) continue;
202 if (p.y() >= image->height()) continue;
203 if (redMarker.testBit(OFFSET(p.x(), p.y(), image))) continue; // already been here
204
205 QRgb pixel = image->pixel(p);
206 if (pixel != 0xffffffff) continue; // black; bail
207
208 redMarker.setBit(OFFSET(p.x(), p.y(), image), true);
209 if (p.x() > maxX) maxX = p.x();
210 if (p.x() < minX) minX = p.x();
211 if (p.y() > maxY) maxY = p.y();
212 if (p.y() < minY) minY = p.y();
213
214 stack.append(QPoint(p.x() - 1, p.y()));
215 stack.append(QPoint(p.x() + 1, p.y()));
216 stack.append(QPoint(p.x(), p.y() - 1));
217 stack.append(QPoint(p.x(), p.y() + 1));
218 }
219
220 //image->save("testPoly1.png");
221
222 // step 2 replace white with black
223 image->fill(0);
224
225 // step 3 replace "red" with white
226 for (int y = 0; y < image->height(); y++) {
227 for (int x = 0; x < image->width(); x++) {
228 if (redMarker.testBit(OFFSET(x, y, image))) {
229 image->setPixel(x, y, 1);
230 }
231 }
232 }
233
234 #ifndef QT_NO_DEBUG
235 image->save(FolderUtils::getUserDataStorePath("") + "/testGroundPlaneUnit3.png");
236 #endif
237
238 scanImage(*image, bWidth, bHeight, GraphicsUtils::StandardFritzingDPI / res, res, color, true, true, QSizeF(.05, .05), 1 / GraphicsUtils::SVGDPI, QPointF(0,0));
239 delete image;
240 return true;
241 }
242
generateGroundPlane(const QString & boardSvg,QSizeF boardImageSize,const QString & svg,QSizeF copperImageSize,QStringList & exceptions,QGraphicsItem * board,double res,const QString & color,double keepoutMils)243 bool GroundPlaneGenerator::generateGroundPlane(const QString & boardSvg, QSizeF boardImageSize, const QString & svg, QSizeF copperImageSize,
244 QStringList & exceptions, QGraphicsItem * board, double res, const QString & color, double keepoutMils)
245 {
246 GPGParams params;
247 params.boardSvg = boardSvg;
248 params.keepoutMils = keepoutMils;
249 params.boardImageSize = boardImageSize;
250 params.svg = svg;
251 params.copperImageSize = copperImageSize;
252 params.exceptions = exceptions;
253 params.board = board;
254 params.res = res;
255 params.color = color;
256 QFuture<bool> future = QtConcurrent::run(this, &GroundPlaneGenerator::generateGroundPlaneFn, params);
257 while (!future.isFinished()) {
258 ProcessEventBlocker::processEvents(200);
259 }
260 return future.result();
261 }
262
generateGroundPlaneFn(GPGParams & params)263 bool GroundPlaneGenerator::generateGroundPlaneFn(GPGParams & params)
264 {
265
266 double bWidth, bHeight;
267 QList<QRectF> rects;
268 QImage * image = generateGroundPlaneAux(params, bWidth, bHeight, rects);
269 if (image == NULL) return false;
270
271 double pixelFactor = GraphicsUtils::StandardFritzingDPI / params.res;
272 scanImage(*image, bWidth, bHeight, pixelFactor, params.res, params.color, true, true, QSizeF(.05, .05), 1 / GraphicsUtils::SVGDPI, QPointF(0,0));
273 if (rects.count() > 0) {
274 foreach (QRectF r, rects) {
275 // add the rects separately as tiny SVGs which don't get clipped (since they are connected)
276 QList<QPolygon> polygons;
277 QPolygon polygon;
278 polygon << QPoint(r.left() * pixelFactor, r.top() * pixelFactor)
279 << QPoint(r.right() * pixelFactor, r.top() * pixelFactor)
280 << QPoint(r.right() * pixelFactor, r.bottom() * pixelFactor)
281 << QPoint(r.left() * pixelFactor, r.bottom() * pixelFactor);
282 polygons.append(polygon);
283 makePolySvg(polygons, params.res, bWidth, bHeight, pixelFactor, params.color, false, true, QSizeF(0, 0), 0, QPointF(0, 0));
284 }
285 }
286
287 delete image;
288 return true;
289 }
290
generateGroundPlaneAux(GPGParams & params,double & bWidth,double & bHeight,QList<QRectF> & rects)291 QImage * GroundPlaneGenerator::generateGroundPlaneAux(GPGParams & params, double & bWidth, double & bHeight, QList<QRectF> & rects)
292 {
293 QByteArray boardByteArray;
294 QString tempColor("#ffffff");
295 if (!SvgFileSplitter::changeColors(params.boardSvg, tempColor, params.exceptions, boardByteArray)) {
296 return NULL;
297 }
298
299
300 //QFile file0("testGroundFillBoard.svg");
301 //file0.open(QIODevice::WriteOnly);
302 //QTextStream out0(&file0);
303 //out0 << boardByteArray;
304 //file0.close();
305
306
307 /*
308 QByteArray copperByteArray;
309 if (!SvgFileSplitter::changeStrokeWidth(params.svg, m_strokeWidthIncrement, false, true, copperByteArray)) {
310 return NULL;
311 }
312 */
313
314 QString errorStr;
315 int errorLine;
316 int errorColumn;
317 QDomDocument doc;
318 doc.setContent(params.svg, &errorStr, &errorLine, &errorColumn);
319 QDomElement root = doc.documentElement();
320 SvgFileSplitter::forceStrokeWidth(root, 2 * params.keepoutMils, "#000000", true, true);
321 QByteArray copperByteArray = doc.toByteArray(0);
322
323 //QFile file1("testGroundFillCopper.svg");
324 //file1.open(QIODevice::WriteOnly);
325 //QTextStream out1(&file1);
326 //out1 << copperByteArray;
327 //file1.close();
328
329
330 double svgWidth = params.res * qMax(params.boardImageSize.width(), params.copperImageSize.width()) / GraphicsUtils::SVGDPI;
331 double svgHeight = params.res * qMax(params.boardImageSize.height(), params.copperImageSize.height()) / GraphicsUtils::SVGDPI;
332
333 QRectF br = params.board->sceneBoundingRect();
334 bWidth = params.res * br.width() / GraphicsUtils::SVGDPI;
335 bHeight = params.res * br.height() / GraphicsUtils::SVGDPI;
336 QImage * image = new QImage(qMax(svgWidth, bWidth), qMax(svgHeight, bHeight), QImage::Format_Mono); //
337 image->setDotsPerMeterX(params.res * GraphicsUtils::InchesPerMeter);
338 image->setDotsPerMeterY(params.res * GraphicsUtils::InchesPerMeter);
339 image->fill(0x0);
340
341 QSvgRenderer renderer(boardByteArray);
342 QPainter painter;
343 painter.begin(image);
344 painter.setRenderHint(QPainter::Antialiasing, false);
345 QRectF boardBounds(0, 0, params.res * params.boardImageSize.width() / GraphicsUtils::SVGDPI, params.res * params.boardImageSize.height() / GraphicsUtils::SVGDPI);
346 DebugDialog::debug("boardbounds", boardBounds);
347 renderer.render(&painter, boardBounds);
348 painter.end();
349
350 #ifndef QT_NO_DEBUG
351 image->save(FolderUtils::getUserDataStorePath("") + "/testGroundFillBoard.png");
352 #endif
353
354 DRC::extendBorder(BORDERINCHES * params.res, image);
355 GraphicsUtils::drawBorder(image, BORDERINCHES * params.res);
356
357 QImage boardImage = image->copy();
358
359 /*
360 for (double m = 0; m < BORDERINCHES; m += (1.0 / params.res)) { // 1 mm
361 QList<QPoint> points;
362 collectBorderPoints(*image, points);
363
364 #ifndef QT_NO_DEBUG
365
366 // for debugging
367 //double pixelFactor = GraphicsUtils::StandardFritzingDPI / res;
368 //QPolygon polygon;
369 //foreach(QPoint p, points) {
370 // polygon.append(QPoint(p.x() * pixelFactor, p.y() * pixelFactor));
371 //}
372
373 //QList<QPolygon> polygons;
374 //polygons.append(polygon);
375 //QPointF offset;
376 //this
377 //QString pSvg = makePolySvg(polygons, res, bWidth, bHeight, pixelFactor, "#ffffff", false, NULL, QSizeF(0,0), 0, QPointF(0, 0));
378
379 #endif
380
381 foreach (QPoint p, points) image->setPixel(p, 0);
382 }
383 */
384
385 #ifndef QT_NO_DEBUG
386 image->save(FolderUtils::getUserDataStorePath("") + "/testGroundFillBoardBorder.png");
387 #endif
388
389 QSvgRenderer renderer2(copperByteArray);
390 painter.begin(image);
391 painter.setRenderHint(QPainter::Antialiasing, false);
392 QRectF bounds(0, 0, params.res * params.copperImageSize.width() / GraphicsUtils::SVGDPI, params.res * params.copperImageSize.height() / GraphicsUtils::SVGDPI);
393 DebugDialog::debug("copperbounds", bounds);
394 renderer2.render(&painter, bounds);
395 painter.end();
396
397 #ifndef QT_NO_DEBUG
398 image->save(FolderUtils::getUserDataStorePath("") + "/testGroundFillCopper.png");
399 #endif
400
401 emit postImageSignal(this, image, &boardImage, params.board, &rects);
402
403 return image;
404 }
405
scanImage(QImage & image,double bWidth,double bHeight,double pixelFactor,double res,const QString & colorString,bool makeConnectorFlag,bool makeOffset,QSizeF minAreaInches,double minDimensionInches,QPointF polygonOffset)406 void GroundPlaneGenerator::scanImage(QImage & image, double bWidth, double bHeight, double pixelFactor, double res,
407 const QString & colorString, bool makeConnectorFlag,
408 bool makeOffset, QSizeF minAreaInches, double minDimensionInches, QPointF polygonOffset)
409 {
410 QList<QRect> rects;
411 scanLines(image, bWidth, bHeight, rects);
412 QList< QList<int> * > pieces;
413 splitScanLines(rects, pieces);
414 foreach (QList<int> * piece, pieces) {
415 QList<QPolygon> polygons;
416 QList<QRect> newRects;
417 foreach (int i, *piece) {
418 QRect r = rects.at(i);
419 newRects.append(QRect(r.x() * pixelFactor, r.y() * pixelFactor, (r.width() * pixelFactor) + 1, pixelFactor + 1)); // + 1 is for off-by-one converting rects to polys
420 }
421
422 // note: there is always one
423 joinScanLines(newRects, polygons);
424 makePolySvg(polygons, res, bWidth, bHeight, pixelFactor, colorString, makeConnectorFlag, makeOffset, minAreaInches, minDimensionInches, polygonOffset);
425 }
426
427 /*
428 QString newSvg = QString("<svg xmlns='http://www.w3.org/2000/svg' width='%1in' height='%2in' viewBox='0 0 %3 %4' >\n")
429 .arg(bWidth / res)
430 .arg(bHeight / res)
431 .arg(bWidth * MILS)
432 .arg(bHeight * MILS);
433 newSvg += "<g id='groundplane'>\n";
434
435 // ?split each line into two lines (l1, l2) and add a terminal point at the left of l1 and the right of l2?
436
437 ix = 0;
438 foreach (QRectF r, rects) {
439 newSvg += QString("<rect x='%1' y='%2' width='%3' height='%4' id='connector%5pad' fill='%6' />\n")
440 .arg(r.left() * MILS)
441 .arg(r.top() * MILS)
442 .arg(r.width() * MILS)
443 .arg(MILS)
444 .arg(ix++).
445 .arg(ViewLayer::Copper0Color);
446 }
447 newSvg += "</g>\n</svg>\n";
448 */
449
450 }
451
scanLines(QImage & image,int bWidth,int bHeight,QList<QRect> & rects)452 void GroundPlaneGenerator::scanLines(QImage & image, int bWidth, int bHeight, QList<QRect> & rects)
453 {
454 if (m_minRiseSize > 1) {
455 for (int x = 0; x < bWidth; x++) {
456 bool inWhite = false;
457 int whiteStart = 0;
458 for (int y = 0; y < bHeight; y++) {
459 QRgb current = image.pixel(x, y);
460 if (inWhite) {
461 if (current == 0xffffffff) { // qBlue(current) == 0xff gray > 128
462 // another white pixel, keep moving
463 continue;
464 }
465
466 // got black: close up this segment;
467 inWhite = false;
468 if (y - whiteStart < m_minRiseSize) {
469 for (int j = whiteStart; j <= y; j++) {
470 image.setPixel(x, j, 0);
471 }
472 continue;
473 }
474
475 }
476 else {
477 if (current != 0xffffffff) { // qBlue(current) != 0xff
478 // another black pixel, keep moving
479 continue;
480 }
481
482 inWhite = true;
483 whiteStart = y;
484 }
485 }
486 if (inWhite) {
487 // close up the last segment
488 if (bHeight - whiteStart < m_minRiseSize) {
489 for (int j = whiteStart; j <= bHeight; j++) {
490 image.setPixel(x, j, 0);
491 }
492 }
493 }
494 }
495 }
496
497 // threshold should be between 0 and 255 exclusive; smaller will include more of the svg
498 for (int y = 0; y < bHeight; y++) {
499 bool inWhite = false;
500 int whiteStart = 0;
501 for (int x = 0; x < bWidth; x++) {
502 QRgb current = image.pixel(x, y);
503 //if (current != 0xff000000 && current != 0xffffffff) {
504 //DebugDialog::debug(QString("current %1").arg(current,0,16));
505 //}
506 //DebugDialog::debug(QString("current %1 %2").arg(current,0,16).arg(gray, 0, 16));
507 if (inWhite) {
508 if (current == 0xffffffff) { // qBlue(current) == 0xff gray > 128
509 // another white pixel, keep moving
510 continue;
511 }
512
513 // got black: close up this segment;
514 inWhite = false;
515 if (x - whiteStart < m_minRunSize) {
516 // not a big enough section
517 continue;
518 }
519
520 rects.append(QRect(whiteStart, y, x - whiteStart, 1));
521 }
522 else {
523 if (current != 0xffffffff) { // qBlue(current) != 0xff
524 // another black pixel, keep moving
525 continue;
526 }
527
528 inWhite = true;
529 whiteStart = x;
530 }
531 }
532 if (inWhite) {
533 // close up the last segment
534 if (bWidth - whiteStart >= m_minRunSize) {
535 rects.append(QRect(whiteStart, y, bWidth - whiteStart, 1));
536 }
537 }
538 }
539 }
540
splitScanLines(QList<QRect> & rects,QList<QList<int> * > & pieces)541 void GroundPlaneGenerator::splitScanLines(QList<QRect> & rects, QList< QList<int> * > & pieces)
542 {
543 // combines vertically adjacent scanlines into "pieces"
544 int ix = 0;
545 int prevFirst = -1;
546 int prevLast = -1;
547 while (ix < rects.count()) {
548 int first = ix;
549 QRectF firstR = rects.at(ix);
550 while (++ix < rects.count()) {
551 QRectF nextR = rects.at(ix);
552 if (nextR.y() != firstR.y()) {
553 break;
554 }
555 }
556 int last = ix - 1; // this was a lookahead so step back one
557 if (prevFirst >= 0) {
558 for (int i = first; i <= last; i++) {
559 QRectF candidate = rects.at(i);
560 int gotCount = 0;
561 for (int j = prevFirst; j <= prevLast; j++) {
562 QRectF prev = rects.at(j);
563 if (prev.y() + 1 != candidate.y()) {
564 // skipped a line; no intersection possible
565 break;
566 }
567
568 if ((prev.x() + prev.width() <= candidate.x()) || (candidate.x() + candidate.width() <= prev.x())) {
569 // candidate and prev didn't intersect
570 continue;
571 }
572
573 if (++gotCount > 1) {
574 QList<int> * piecei = NULL;
575 QList<int> * piecej = NULL;
576 foreach (QList<int> * piece, pieces) {
577 if (piece->contains(j)) {
578 piecej = piece;
579 break;
580 }
581 }
582 foreach (QList<int> * piece, pieces) {
583 if (piece->contains(i)) {
584 piecei = piece;
585 break;
586 }
587 }
588 if (piecei != NULL && piecej != NULL) {
589 if (piecei != piecej) {
590 foreach (int b, *piecej) {
591 piecei->append(b);
592 }
593 piecej->clear();
594 pieces.removeOne(piecej);
595 delete piecej;
596 }
597 piecei->append(i);
598 }
599 else {
600 DebugDialog::debug("we are really screwed here, what should we do about it?");
601 }
602 }
603 else {
604 // put the candidate (i) in j's piece
605 foreach (QList<int> * piece, pieces) {
606 if (piece->contains(j)) {
607 piece->append(i);
608 break;
609 }
610 }
611 }
612 }
613
614 if (gotCount == 0) {
615 // candidate is an orphan line at this point
616 QList<int> * piece = new QList<int>;
617 piece->append(i);
618 pieces.append(piece);
619 }
620
621 }
622 }
623 else {
624 for (int i = first; i <= last; i++) {
625 QList<int> * piece = new QList<int>;
626 piece->append(i);
627 pieces.append(piece);
628 }
629 }
630
631 prevFirst = first;
632 prevLast = last;
633 }
634
635 foreach (QList<int> * piece, pieces) {
636 qSort(*piece);
637 }
638 }
639
joinScanLines(QList<QRect> & rects,QList<QPolygon> & polygons)640 void GroundPlaneGenerator::joinScanLines(QList<QRect> & rects, QList<QPolygon> & polygons) {
641 QList< QList<int> * > pieces;
642 int ix = 0;
643 int prevFirst = -1;
644 int prevLast = -1;
645 while (ix < rects.count()) {
646 int first = ix;
647 QRectF firstR = rects.at(ix);
648 while (++ix < rects.count()) {
649 QRectF nextR = rects.at(ix);
650 if (nextR.y() != firstR.y()) {
651 break;
652 }
653 }
654 int last = ix - 1;
655 if (prevFirst >= 0) {
656 QVector<int> holdPrevs(last - first + 1);
657 QVector<int> gotCounts(last - first + 1);
658 for (int i = first; i <= last; i++) {
659 int index = i - first;
660 holdPrevs[index] = 0;
661 gotCounts[index] = 0;
662 QRectF candidate = rects.at(i);
663 for (int j = prevFirst; j <= prevLast; j++) {
664 QRectF prev = rects.at(j);
665
666 if ((prev.x() + prev.width() <= candidate.x()) || (candidate.x() + candidate.width() <= prev.x())) {
667 // candidate and prev didn't intersect
668 continue;
669 }
670
671 holdPrevs[index] = j;
672 gotCounts[index]++;
673 }
674 if (gotCounts[index] > 1) {
675 holdPrevs[index] = -1; // clear this to allow one of the others in this scanline to capture a previous
676 }
677 }
678 for (int i = first; i <= last; i++) {
679 int index = i - first;
680
681 bool gotOne = false;
682 if (gotCounts[index] == 1) {
683 bool unique = true;
684 for (int j = first; j <= last; j++) {
685 if (j - first == index) continue; // don't compare against yourself
686
687 if (holdPrevs[index] == holdPrevs[j - first]) {
688 unique = false;
689 break;
690 }
691 }
692
693 if (unique) {
694 // add this to the previous chunk
695 gotOne = true;
696 foreach (QList<int> * piece, pieces) {
697 if (piece->contains(holdPrevs[index])) {
698 piece->append(i);
699 break;
700
701 }
702 }
703 }
704 }
705 if (!gotOne) {
706 // start a new chunk
707 holdPrevs[index] = -1; // allow others to capture the prev
708 QList<int> * piece = new QList<int>;
709 piece->append(i);
710 pieces.append(piece);
711 }
712 }
713 }
714 else {
715 for (int i = first; i <= last; i++) {
716 QList<int> * piece = new QList<int>;
717 piece->append(i);
718 pieces.append(piece);
719 }
720 }
721
722 prevFirst = first;
723 prevLast = last;
724 }
725
726 foreach (QList<int> * piece, pieces) {
727 //QPolygon poly(rects.at(piece->at(0)), true);
728 //for (int i = 1; i < piece->length(); i++) {
729 //QPolygon temp(rects.at(piece->at(i)), true);
730 //poly = poly.united(temp);
731 //}
732
733 // no need to close polygon; SVG automatically closes path
734
735 QPolygon poly;
736
737 // left side
738 for (int i = 0; i < piece->length(); i++) {
739 QRect r = rects.at(piece->at(i));
740 if ((poly.count() > 0) && (poly.last().x() == r.left())) {
741 poly.pop_back();
742 }
743 else {
744 poly.append(QPoint(r.left(), r.top()));
745 }
746 poly.append(QPoint(r.left(), r.bottom()));
747 }
748 // right side
749 for (int i = piece->length() - 1; i >= 0; i--) {
750 QRect r = rects.at(piece->at(i));
751 if ((poly.count() > 0) && (poly.last().x() == r.right())) {
752 poly.pop_back();
753 }
754 else {
755 poly.append(QPoint(r.right(), r.bottom()));
756 }
757 poly.append(QPoint(r.right(), r.top()));
758 }
759
760
761
762 polygons.append(poly);
763 delete piece;
764 }
765 }
766
makePolySvg(QList<QPolygon> & polygons,double res,double bWidth,double bHeight,double pixelFactor,const QString & colorString,bool makeConnectorFlag,bool makeOffset,QSizeF minAreaInches,double minDimensionInches,QPointF polygonOffset)767 void GroundPlaneGenerator::makePolySvg(QList<QPolygon> & polygons, double res, double bWidth, double bHeight, double pixelFactor,
768 const QString & colorString, bool makeConnectorFlag, bool makeOffset,
769 QSizeF minAreaInches, double minDimensionInches, QPointF polygonOffset)
770 {
771 QPointF offset;
772 QString pSvg = makePolySvg(polygons, res, bWidth, bHeight, pixelFactor, colorString, makeConnectorFlag, makeOffset ? &offset : NULL, minAreaInches, minDimensionInches, polygonOffset);
773 if (pSvg.isEmpty()) return;
774
775 m_newSVGs.append(pSvg);
776 if (makeOffset) {
777 offset *= GraphicsUtils::SVGDPI;
778 m_newOffsets.append(offset); // offset now in pixels
779 }
780
781 /*
782 QFile file4("testPoly.svg");
783 file4.open(QIODevice::WriteOnly);
784 QTextStream out4(&file4);
785 out4 << pSvg;
786 file4.close();
787 */
788 }
789
makePolySvg(QList<QPolygon> & polygons,double res,double bWidth,double bHeight,double pixelFactor,const QString & colorString,bool makeConnectorFlag,QPointF * offset,QSizeF minAreaInches,double minDimensionInches,QPointF polygonOffset)790 QString GroundPlaneGenerator::makePolySvg(QList<QPolygon> & polygons, double res, double bWidth, double bHeight, double pixelFactor,
791 const QString & colorString, bool makeConnectorFlag, QPointF * offset,
792 QSizeF minAreaInches, double minDimensionInches, QPointF polygonOffset)
793 {
794 int minX = 0;
795 int minY = 0;
796 if (offset != NULL) {
797 minY = std::numeric_limits<int>::max();
798 int maxY = std::numeric_limits<int>::min();
799 minX = minY;
800 int maxX = maxY;
801
802 foreach (QPolygon polygon, polygons) {
803 foreach (QPoint p, polygon) {
804 if (p.x() > maxX) maxX = p.x();
805 if (p.x() < minX) minX = p.x();
806 if (p.y() > maxY) maxY = p.y();
807 if (p.y() < minY) minY = p.y();
808 }
809 }
810
811 bWidth = (maxX - minX) / pixelFactor;
812 bHeight = (maxY - minY) / pixelFactor;
813 offset->setX(minX / (res * pixelFactor)); // inches
814 offset->setY(minY / (res * pixelFactor)); // inches
815 }
816
817 if ((bWidth / res < minAreaInches.width()) && (bHeight / res < minAreaInches.height())) {
818 return "";
819 }
820 if ((bWidth / res < minDimensionInches) || (bHeight / res < minDimensionInches)) {
821 return "";
822 }
823
824
825 QString pSvg = QString("<svg xmlns='http://www.w3.org/2000/svg' width='%1in' height='%2in' viewBox='0 0 %3 %4' >\n")
826 .arg(bWidth / res)
827 .arg(bHeight / res)
828 .arg(bWidth * pixelFactor)
829 .arg(bHeight * pixelFactor);
830 QString transform;
831 if (polygonOffset.x() != 0 || polygonOffset.y() != 0) {
832 transform = QString("transform='translate(%1, %2)'").arg(polygonOffset.x()).arg(polygonOffset.y());
833 }
834 pSvg += QString("<g id='%1' %2>\n").arg(m_layerName).arg(transform);
835 if (makeConnectorFlag) {
836 makeConnector(polygons, res, pixelFactor, colorString, minX, minY, pSvg);
837 }
838 else {
839 foreach (QPolygon poly, polygons) {
840 pSvg += makeOnePoly(poly, colorString, "", minX, minY);
841 }
842 }
843
844 pSvg += "</g>\n</svg>\n";
845
846 return pSvg;
847 }
848
makeConnector(QList<QPolygon> & polygons,double res,double pixelFactor,const QString & colorString,int minX,int minY,QString & pSvg)849 void GroundPlaneGenerator::makeConnector(QList<QPolygon> & polygons, double res, double pixelFactor, const QString & colorString, int minX, int minY, QString & pSvg)
850 {
851 // see whether the standard circular connector will fit somewhere inside a polygon:
852 // http://stackoverflow.com/questions/4279478/maximum-circle-inside-a-non-convex-polygon
853 // or maybe this is useful, e.g. treating the circle as a square:
854 // http://stackoverflow.com/questions/4833802/check-if-polygon-is-inside-a-polygon
855
856 // code presently uses a version of the Poles of Inaccessibility algorithm:
857
858 static const double standardConnectorWidth = .075; // inches
859 double targetDiameter = res * pixelFactor * standardConnectorWidth;
860 double targetDiameterAnd = targetDiameter * 1.25;
861 double targetRadius = targetDiameter / 2;
862 double targetRadiusAnd = targetDiameterAnd / 2;
863 double targetRadiusAndSquared = targetRadiusAnd * targetRadiusAnd;
864 foreach (QPolygon poly, polygons) {
865 QRect boundingRect = poly.boundingRect();
866 if (boundingRect.width() < targetDiameterAnd) continue;
867 if (boundingRect.height() < targetDiameterAnd) continue;
868
869 QList<QLineF> polyLines;
870 int count = poly.count();
871 for (int i = 0; i < count; i++) {
872 QLineF lp(poly[i], poly[(i + 1) % count]);
873 polyLines.append(lp);
874 }
875
876 int xDivisor = qRound(boundingRect.width() / targetRadius);
877 int yDivisor = qRound(boundingRect.height() / targetRadius);
878
879 double dx = (boundingRect.width() - targetDiameterAnd) / xDivisor;
880 double dy = (boundingRect.height() - targetDiameterAnd) / yDivisor;
881 double x;
882 double y = boundingRect.top() + targetRadiusAnd - dy;
883 for (int iy = 0; iy <= yDivisor; iy++) {
884 y += dy;
885 x = boundingRect.left() + targetRadiusAnd - dx;
886 for (int ix = 0; ix <= xDivisor; ix++) {
887 x += dx;
888 if (!poly.containsPoint(QPoint(qRound(x), qRound(y)), Qt::OddEvenFill)) continue;
889
890 bool gotOne = true;
891 foreach (QLineF line, polyLines) {
892 double distance, dx, dy;
893 bool atEndpoint;
894 GraphicsUtils::distanceFromLine(x, y, line.p1().x(), line.p1().y(), line.p2().x(), line.p2().y(),
895 dx, dy, distance, atEndpoint);
896 if (distance <= targetRadiusAndSquared) {
897 gotOne = false;
898 break;
899 }
900 }
901
902 if (!gotOne) continue;
903
904 foreach (QPolygon poly, polygons) {
905 pSvg += makeOnePoly(poly, colorString, "", minX, minY);
906 }
907
908 pSvg += QString("<g id='%1'><circle cx='%2' cy='%3' r='%4' fill='%5' stroke='none' stroke-width='0' /></g>\n")
909 .arg(ConnectorName)
910 .arg(x - minX)
911 .arg(y - minY)
912 .arg(targetRadius)
913 .arg(colorString);
914
915
916 return;
917 }
918 }
919 }
920
921 // couldn't find anything big enough above, so
922 // try to find a poly with an area that's big enough to click, but not so big as to get in the way
923 int useIndex = -1;
924 QList<double> areas;
925 double divisor = res * pixelFactor * res * pixelFactor;
926 foreach (QPolygon poly, polygons) {
927 areas.append(calcArea(poly) / divisor);
928 }
929
930 for (int i = 0; i < areas.count(); i++) {
931 if (areas.at(i) > 0.1 && areas.at(i) < 0.25) {
932 useIndex = i;
933 break;
934 }
935 }
936 if (useIndex < 0) {
937 for (int i = 0; i < areas.count(); i++) {
938 if (areas.at(i) > 0.1) {
939 useIndex = i;
940 break;
941 }
942 }
943 }
944 if (useIndex < 0) {
945 pSvg += QString("<g id='%1'>\n").arg(ConnectorName);
946 foreach (QPolygon poly, polygons) {
947 pSvg += makeOnePoly(poly, colorString, "", minX, minY);
948 }
949 pSvg += "</g>";
950 }
951 else {
952 int ix = 0;
953 for (int i = 0; i < polygons.count(); i++) {
954 if (i == useIndex) {
955 // has to appear inside a g element
956 pSvg += QString("<g id='%1'>\n").arg(ConnectorName);
957 pSvg += makeOnePoly(polygons.at(i), colorString, "", minX, minY);
958 pSvg += "</g>";
959 }
960 else {
961 pSvg += makeOnePoly(polygons.at(i), colorString, FSvgRenderer::NonConnectorName + QString::number(ix++), minX, minY);
962 }
963 }
964 }
965 }
966
calcArea(QPolygon & poly)967 double GroundPlaneGenerator::calcArea(QPolygon & poly) {
968 double total = 0;
969 for (int ix = 0; ix < poly.count(); ix++) {
970 QPoint p0 = poly.at(ix);
971 QPoint p1 = poly.at((ix + 1) % poly.count());
972 total += (p0.x() * p1.y() - p1.x() * p0.y());
973 }
974 return qAbs(total / 2.0);
975 }
976
makeOnePoly(const QPolygon & poly,const QString & colorString,const QString & id,int minX,int minY)977 QString GroundPlaneGenerator::makeOnePoly(const QPolygon & poly, const QString & colorString, const QString & id, int minX, int minY) {
978 QString idString;
979 if (!id.isEmpty()) {
980 idString = QString("id='%1'").arg(id);
981 }
982 QString polyString = QString("<polygon fill='%1' stroke='none' stroke-width='0' %2 points='\n").arg(colorString).arg(idString);
983 int space = 0;
984 foreach (QPoint p, poly) {
985 polyString += QString("%1,%2 %3").arg(p.x() - minX).arg(p.y() - minY).arg((++space % 8 == 0) ? "\n" : "");
986 }
987 polyString += "'/>\n";
988 return polyString;
989 }
990
newSVGs()991 const QStringList & GroundPlaneGenerator::newSVGs() {
992 return m_newSVGs;
993 }
994
newOffsets()995 const QList<QPointF> & GroundPlaneGenerator::newOffsets() {
996 return m_newOffsets;
997 }
998
removeRedundant(QList<QPoint> & points)999 void removeRedundant(QList<QPoint> & points)
1000 {
1001 QPoint current = points.last();
1002 int ix = points.count() - 2;
1003 int soFar = 1;
1004 while (ix > 0) {
1005 if (points.at(ix).x() != current.x()) {
1006 current = points.at(ix--);
1007 soFar = 1;
1008 continue;
1009 }
1010
1011 if (++soFar > 2) {
1012 points.removeAt(ix + 1);
1013 }
1014 ix--;
1015 }
1016 }
1017
collectBorderPoints(QImage & image,QList<QPoint> & points)1018 bool GroundPlaneGenerator::collectBorderPoints(QImage & image, QList<QPoint> & points)
1019 {
1020 // background is black
1021
1022 int currentX = 0, currentY = 0;
1023 bool gotSomething = false;
1024
1025 for (int y = 0; y < image.height(); y++) {
1026 for (int x = 0; x < image.width(); x++) {
1027 QRgb current = image.pixel(x, y);
1028 if (current != 0xffffffff) {
1029 // another black pixel, keep moving
1030 continue;
1031 }
1032
1033 currentX = x;
1034 currentY = y;
1035 //DebugDialog::debug(QString("first point %1 %2").arg(currentX).arg(currentY));
1036 points.append(QPoint(currentX, currentY));
1037 gotSomething = true;
1038 break;
1039 }
1040 if (gotSomething) break;
1041 }
1042
1043 if (!gotSomething) {
1044 DebugDialog::debug("first border point not found");
1045 return false;
1046 }
1047
1048 bool done = false;
1049 long maxPoints = image.height() * image.width() / 2;
1050 for (long inc = 0; inc < maxPoints; inc++) {
1051 if (try8(currentX, currentY, image, points)) ;
1052 else {
1053 QPoint p = points.first();
1054 if (qAbs(p.x() - currentX) < 4 && qAbs(p.y() - currentY) < 4) {
1055 // we're near the beginning again
1056 done = true;
1057 break;
1058 }
1059
1060 bool keepGoing = false;
1061 for (int ix = points.count() - 2; ix >= 0; ix--) {
1062 QPoint p = points.at(ix);
1063 if (try8(p.x(), p.y(), image, points)) {
1064 keepGoing = true;
1065 break;
1066 }
1067 }
1068
1069 if (!keepGoing) break;
1070 }
1071
1072 QPoint p = points.last();
1073 currentX = p.x();
1074 currentY = p.y();
1075 //DebugDialog::debug(QString("next point %1 %2").arg(currentX).arg(currentY));
1076 //if (inc % 100 == 0) {
1077 //DebugDialog::debug("\n");
1078 //}
1079 }
1080 return done;
1081 }
1082
scanOutline(QImage & image,double bWidth,double bHeight,double pixelFactor,double res,const QString & colorString,bool makeConnectorFlag,bool makeOffset,QSizeF minAreaInches,double minDimensionInches)1083 void GroundPlaneGenerator::scanOutline(QImage & image, double bWidth, double bHeight, double pixelFactor, double res,
1084 const QString & colorString, bool makeConnectorFlag,
1085 bool makeOffset, QSizeF minAreaInches, double minDimensionInches)
1086 {
1087 QList<QPoint> points;
1088
1089 bool result = collectBorderPoints(image, points);
1090 if (points.count() == 0 || !result) {
1091 DebugDialog::debug("no border points");
1092 return;
1093 }
1094
1095 removeRedundant(points);
1096
1097 QPolygon polygon;
1098 foreach(QPoint p, points) {
1099 polygon.append(QPoint(p.x() * pixelFactor, p.y() * pixelFactor));
1100 }
1101
1102 QList<QPolygon> polygons;
1103 polygons.append(polygon);
1104 makePolySvg(polygons, res, bWidth, bHeight, pixelFactor, colorString, makeConnectorFlag, makeOffset, minAreaInches, minDimensionInches, QPointF(0,0));
1105
1106 /*
1107 QFile file4("testPoly.svg");
1108 file4.open(QIODevice::WriteOnly);
1109 QTextStream out4(&file4);
1110 out4 << pSvg;
1111 file4.close();
1112 */
1113 }
1114
1115
try8(int x,int y,QImage & image,QList<QPoint> & points)1116 bool GroundPlaneGenerator::try8(int x, int y, QImage & image, QList<QPoint> & points) {
1117 if (tryNextPoint(x, y + 1, image, points)) return true;
1118 else if (tryNextPoint(x + 1, y, image, points)) return true;
1119 else if (tryNextPoint(x, y - 1, image, points)) return true;
1120 else if (tryNextPoint(x - 1, y, image, points)) return true;
1121 else if (tryNextPoint(x + 1, y + 1, image, points)) return true;
1122 else if (tryNextPoint(x - 1, y + 1, image, points)) return true;
1123 else if (tryNextPoint(x + 1, y - 1, image, points)) return true;
1124 else if (tryNextPoint(x - 1, y - 1, image, points)) return true;
1125 return false;
1126 }
1127
tryNextPoint(int x,int y,QImage & image,QList<QPoint> & points)1128 bool GroundPlaneGenerator::tryNextPoint(int x, int y, QImage & image, QList<QPoint> & points)
1129 {
1130 if (x < 0) return false;
1131 if (y < 0) return false;
1132 if (x >= image.width()) return false;
1133 if (y >= image.height()) return false;
1134
1135 foreach (QPoint p, points) {
1136 if (p.x() == x && p.y() == y) {
1137 // already visited
1138 return false;
1139 }
1140
1141 if (qAbs(p.x() - x) > 3 && qAbs(p.y() - y) > 3) {
1142 // too far away from the start of the polygon
1143 break;
1144 }
1145 }
1146
1147
1148 for (int i = points.count() - 1; i >= 0; i--) {
1149 QPoint p = points.at(i);
1150 if (p.x() == x && p.y() == y) {
1151 // already visited
1152 return false;
1153 }
1154
1155 if (qAbs(p.x() - x) > 3 && qAbs(p.y() - y) > 3) {
1156 // too far away from from the current point
1157 break;
1158 }
1159 }
1160
1161 QRgb pixel = image.pixel(x, y);
1162 //DebugDialog::debug(QString("pixel %1,%2 %3").arg(x).arg(y).arg(pixel, 0, 16));
1163 if (pixel != 0xffffffff) {
1164 // empty pixel, not on the border
1165 return false;
1166 }
1167
1168 if (x + 1 == image.width()) {
1169 points.append(QPoint(x, y));
1170 return true;
1171 }
1172
1173 pixel = image.pixel(x + 1, y);
1174 if (pixel != 0xffffffff) {
1175 points.append(QPoint(x, y));
1176 return true;
1177 }
1178
1179 if (y + 1 == image.height()) {
1180 points.append(QPoint(x, y));
1181 return true;
1182 }
1183
1184 pixel = image.pixel(x, y + 1);
1185 if (pixel != 0xffffffff) {
1186 points.append(QPoint(x, y));
1187 return true;
1188 }
1189
1190 if (x - 1 < 0) {
1191 points.append(QPoint(x, y));
1192 return true;
1193 }
1194
1195 pixel = image.pixel(x - 1, y);
1196 if (pixel != 0xffffffff) {
1197 points.append(QPoint(x, y));
1198 return true;
1199 }
1200
1201 if (y - 1 < 0) {
1202 points.append(QPoint(x, y));
1203 return true;
1204 }
1205
1206 pixel = image.pixel(x, y - 1);
1207 if (pixel != 0xffffffff) {
1208 points.append(QPoint(x, y));
1209 return true;
1210 }
1211
1212 return false;
1213 }
1214
setStrokeWidthIncrement(double swi)1215 void GroundPlaneGenerator::setStrokeWidthIncrement(double swi) {
1216 m_strokeWidthIncrement = swi;
1217 }
1218
setLayerName(const QString & layerName)1219 void GroundPlaneGenerator::setLayerName(const QString & layerName) {
1220 m_layerName = layerName;
1221 }
1222
layerName()1223 const QString & GroundPlaneGenerator::layerName() {
1224 return m_layerName;
1225 }
1226
setMinRunSize(int mrus,int mris)1227 void GroundPlaneGenerator::setMinRunSize(int mrus, int mris) {
1228 m_minRunSize = mrus;
1229 m_minRiseSize = mris;
1230 }
1231
mergeSVGs(const QString & initialSVG,const QString & layerName)1232 QString GroundPlaneGenerator::mergeSVGs(const QString & initialSVG, const QString & layerName) {
1233 QDomDocument doc;
1234 if (!initialSVG.isEmpty()) {
1235 TextUtils::mergeSvg(doc, initialSVG, layerName);
1236 }
1237 foreach (QString newSvg, m_newSVGs) {
1238 TextUtils::mergeSvg(doc, newSvg, layerName);
1239 }
1240 return TextUtils::mergeSvgFinish(doc);
1241 }
1242
1243