Engauge Digitizer  2
 All Classes Functions Variables Typedefs Enumerations Friends Pages
GridTriangleFill.cpp
1 /******************************************************************************************************
2  * (C) 2018 markummitchell@github.com. This file is part of Engauge Digitizer, which is released *
3  * under GNU General Public License version 2 (GPLv2) or (at your option) any later version. See file *
4  * LICENSE or go to gnu.org/licenses for details. Distribution requires prior written permission. *
5  ******************************************************************************************************/
6 
7 #include <algorithm>
8 #include "GridLog.h"
9 #include "GridTriangleFill.h"
10 #include <QImage>
11 #include <QList>
12 #include <qmath.h>
13 #include <QPoint>
14 
15 // Non-member comparison function
16 static bool compareByY (const QPoint &first,
17  const QPoint &second)
18 {
19  if (first.y() < second.y()) {
20  return true;
21  } else if (first.y() > second.y()) {
22  return false;
23  } else {
24  // If y values are the same then sort by x values
25  return (first.x() < second.x());
26  }
27 }
28 
29 GridTriangleFill::GridTriangleFill ()
30 {
31 }
32 
33 void GridTriangleFill::drawLine (GridLog &gridLog,
34  QImage &image,
35  int x0,
36  int x1,
37  int y)
38 {
39  const double RADIUS = 0.1;
40 
41  if (x0 > x1) {
42  int xTemp = x0;
43  x0 = x1;
44  x1 = xTemp;
45 
46  }
47 
48  for (int x = x0; x <= x1; x++) {
49 
50  gridLog.showOutputScanLinePixel (x, y, RADIUS);
51 
52  image.setPixel (QPoint (x, y),
53  Qt::black);
54  }
55 }
56 
58  QImage &image,
59  const QPoint &p0In,
60  const QPoint &p1In,
61  const QPoint &p2In)
62 {
63  if (p0In.x() > 0 && p0In.y() > 0 &&
64  p1In.x() > 0 && p1In.y() > 0 &&
65  p2In.x() > 0 && p2In.y() > 0) {
66 
67  QPoint p0, p1, p2;
68 
69  sortByAscendingY (p0In, p1In, p2In, p0, p1, p2);
70 
71  if (p1.y() == p2.y()) {
72 
73  // Triangle with flat bottom
74  flatBottom (gridLog, image, p0, p1, p2);
75 
76  } else if (p0.y() == p1.y()) {
77 
78  // Triangle with flat top
79  flatTop (gridLog, image, p0, p1, p2);
80 
81  } else {
82 
83  // General case is handled by splitting the triangle into one flat top piece and
84  // one flat bottom piece. Fourth point is at same y value as middle point p1
85  double s = double (p1.y() - p0.y()) / double (p2.y() - p0.y());
86  QPoint p3 (qFloor (p0.x() + s * (p2.x() - p0.x())),
87  p1.y());
88  flatBottom (gridLog, image, p0, p1, p3);
89  flatTop (gridLog, image, p1, p3, p2);
90  }
91  }
92 }
93 
94 void GridTriangleFill::flatBottom (GridLog &gridLog,
95  QImage &image,
96  const QPoint &p0,
97  const QPoint &p1,
98  const QPoint &p2)
99 {
100  // Either neither or both denominators are zero, since p1.y()=p2.y()
101  double denom0 = p1.y() - p0.y();
102  double denom1 = p2.y() - p0.y();
103  if (qAbs (denom0) <= 0 || qAbs (denom1) <= 0) {
104  drawLine (gridLog,
105  image,
106  p0.x(),
107  p2.x(),
108  p0.y());
109  } else {
110  double slopeInverse0 = (p1.x() - p0.x()) / denom0;
111  double slopeInverse1 = (p2.x() - p0.x()) / denom1;
112 
113  // For rounding lower point down and upper point up, thus ensuring thorough coverage
114  // (=no gaps between triangles), we order the inverse slopes
115  if (slopeInverse0 > slopeInverse1) {
116  double temp = slopeInverse0;
117  slopeInverse0 = slopeInverse1;
118  slopeInverse1 = temp;
119  }
120 
121  double x0 = p0.x();
122  double x1 = p0.x();
123 
124  for (int scanLineY = p0.y(); scanLineY <= p1.y(); scanLineY++) {
125  drawLine (gridLog,
126  image,
127  qFloor (x0),
128  qFloor (x1),
129  scanLineY);
130  x0 += slopeInverse0;
131  x1 += slopeInverse1;
132  }
133  }
134 }
135 
136 void GridTriangleFill::flatTop (GridLog &gridLog,
137  QImage &image,
138  const QPoint &p0,
139  const QPoint &p1,
140  const QPoint &p2)
141 {
142  // Either neither or both denominators are zero, since p0.y()=p1.y()
143  double denom0 = p2.y() - p0.y();
144  double denom1 = p2.y() - p1.y();
145  if (qAbs (denom0) <= 0 || qAbs (denom1) <= 0) {
146  drawLine (gridLog,
147  image,
148  p0.x(),
149  p2.x(),
150  p0.y());
151  } else {
152  double slopeInverse0 = (p2.x() - p0.x()) / denom0;
153  double slopeInverse1 = (p2.x() - p1.x()) / denom1;
154 
155  // For rounding lower point down and upper point up, thus ensuring thorough coverage
156  // (=no gaps between triangles), we order the inverse slopes
157  if (slopeInverse1 > slopeInverse0) {
158  double temp = slopeInverse0;
159  slopeInverse0 = slopeInverse1;
160  slopeInverse1 = temp;
161  }
162 
163  double x0 = p2.x();
164  double x1 = p2.x();
165 
166  for (int scanLineY = p2.y(); scanLineY >= p0.y(); scanLineY--) {
167  drawLine (gridLog,
168  image,
169  qFloor (x0),
170  qFloor (x1),
171  scanLineY);
172  x0 -= slopeInverse0;
173  x1 -= slopeInverse1;
174  }
175  }
176 }
177 
178 void GridTriangleFill::sortByAscendingY (QPoint p0In,
179  QPoint p1In,
180  QPoint p2In,
181  QPoint &p0,
182  QPoint &p1,
183  QPoint &p2) const
184 {
185  // Sort by ascending y value
186  QList<QPoint> list;
187  list << p0In << p1In << p2In;
188  std::sort (list.begin(), list.end(), compareByY);
189 
190  p0 = list.front();
191  list.pop_front();
192  p1 = list.front();
193  list.pop_front();
194  p2 = list.front();
195 }
Class that does special logging for GridLog and GridRemoval classes.
Definition: GridLog.h:16
void fill(GridLog &gridLog, QImage &image, const QPoint &p0, const QPoint &p1, const QPoint &p2)
Fill triangle between these three points.
void showOutputScanLinePixel(int x, int y, double radius)
Show scan line pixel that is the output of GridHealer.
Definition: GridLog.cpp:88