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 <QPoint>
13 
14 // Non-member comparison function
15 static bool compareByY (const QPoint &first,
16  const QPoint &second)
17 {
18  if (first.y() < second.y()) {
19  return true;
20  } else if (first.y() > second.y()) {
21  return false;
22  } else {
23  // If y values are the same then sort by x values
24  return (first.x() < second.x());
25  }
26 }
27 
28 GridTriangleFill::GridTriangleFill ()
29 {
30 }
31 
32 void GridTriangleFill::drawLine (GridLog &gridLog,
33  QImage &image,
34  int x0,
35  int x1,
36  int y)
37 {
38  const double RADIUS = 0.1;
39 
40  if (x0 > x1) {
41  int xTemp = x0;
42  x0 = x1;
43  x1 = xTemp;
44 
45  }
46 
47  for (int x = x0; x <= x1; x++) {
48 
49  gridLog.showOutputScanLinePixel (x, y, RADIUS);
50 
51  image.setPixel (QPoint (x, y),
52  Qt::black);
53  }
54 }
55 
57  QImage &image,
58  const QPoint &p0In,
59  const QPoint &p1In,
60  const QPoint &p2In)
61 {
62  if (p0In.x() > 0 && p0In.y() > 0 &&
63  p1In.x() > 0 && p1In.y() > 0 &&
64  p2In.x() > 0 && p2In.y() > 0) {
65 
66  QPoint p0, p1, p2;
67 
68  sortByAscendingY (p0In, p1In, p2In, p0, p1, p2);
69 
70  if (p1.y() == p2.y()) {
71 
72  // Triangle with flat bottom
73  flatBottom (gridLog, image, p0, p1, p2);
74 
75  } else if (p0.y() == p1.y()) {
76 
77  // Triangle with flat top
78  flatTop (gridLog, image, p0, p1, p2);
79 
80  } else {
81 
82  // General case is handled by splitting the triangle into one flat top piece and
83  // one flat bottom piece. Fourth point is at same y value as middle point p1
84  double s = (double) (p1.y() - p0.y())/ (double) (p2.y() - p0.y());
85  QPoint p3 ((int) (p0.x() + s * (p2.x() - p0.x())),
86  p1.y());
87  flatBottom (gridLog, image, p0, p1, p3);
88  flatTop (gridLog, image, p1, p3, p2);
89  }
90  }
91 }
92 
93 void GridTriangleFill::flatBottom (GridLog &gridLog,
94  QImage &image,
95  const QPoint &p0,
96  const QPoint &p1,
97  const QPoint &p2)
98 {
99  // Either neither or both denominators are zero, since p1.y()=p2.y()
100  double denom0 = p1.y() - p0.y();
101  double denom1 = p2.y() - p0.y();
102  if (denom0 == 0 || denom1 == 0) {
103  drawLine (gridLog,
104  image,
105  p0.x(),
106  p2.x(),
107  p0.y());
108  } else {
109  double slopeInverse0 = (p1.x() - p0.x()) / denom0;
110  double slopeInverse1 = (p2.x() - p0.x()) / denom1;
111 
112  // For rounding lower point down and upper point up, thus ensuring thorough coverage
113  // (=no gaps between triangles), we order the inverse slopes
114  if (slopeInverse0 > slopeInverse1) {
115  double temp = slopeInverse0;
116  slopeInverse0 = slopeInverse1;
117  slopeInverse1 = temp;
118  }
119 
120  double x0 = p0.x();
121  double x1 = p0.x();
122 
123  for (int scanLineY = p0.y(); scanLineY <= p1.y(); scanLineY++) {
124  drawLine (gridLog,
125  image,
126  (int) x0,
127  (int) x1,
128  scanLineY);
129  x0 += slopeInverse0;
130  x1 += slopeInverse1;
131  }
132  }
133 }
134 
135 void GridTriangleFill::flatTop (GridLog &gridLog,
136  QImage &image,
137  const QPoint &p0,
138  const QPoint &p1,
139  const QPoint &p2)
140 {
141  // Either neither or both denominators are zero, since p0.y()=p1.y()
142  double denom0 = p2.y() - p0.y();
143  double denom1 = p2.y() - p1.y();
144  if (denom0 == 0 || denom1 == 0) {
145  drawLine (gridLog,
146  image,
147  p0.x(),
148  p2.x(),
149  p0.y());
150  } else {
151  double slopeInverse0 = (p2.x() - p0.x()) / denom0;
152  double slopeInverse1 = (p2.x() - p1.x()) / denom1;
153 
154  // For rounding lower point down and upper point up, thus ensuring thorough coverage
155  // (=no gaps between triangles), we order the inverse slopes
156  if (slopeInverse1 > slopeInverse0) {
157  double temp = slopeInverse0;
158  slopeInverse0 = slopeInverse1;
159  slopeInverse1 = temp;
160  }
161 
162  double x0 = p2.x();
163  double x1 = p2.x();
164 
165  for (int scanLineY = p2.y(); scanLineY >= p0.y(); scanLineY--) {
166  drawLine (gridLog,
167  image,
168  (int) x0,
169  (int) x1,
170  scanLineY);
171  x0 -= slopeInverse0;
172  x1 -= slopeInverse1;
173  }
174  }
175 }
176 
177 void GridTriangleFill::sortByAscendingY (QPoint p0In,
178  QPoint p1In,
179  QPoint p2In,
180  QPoint &p0,
181  QPoint &p1,
182  QPoint &p2) const
183 {
184  // Sort by ascending y value
185  QList<QPoint> list;
186  list << p0In << p1In << p2In;
187  std::sort (list.begin(), list.end(), compareByY);
188 
189  p0 = list.front();
190  list.pop_front();
191  p1 = list.front();
192  list.pop_front();
193  p2 = list.front();
194 }
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