Line data Source code
1 : /******************************************************************************
2 : *
3 : * Project: GDAL
4 : * Purpose: Vector polygon rasterization code.
5 : * Author: Frank Warmerdam, warmerdam@pobox.com
6 : *
7 : ******************************************************************************
8 : * Copyright (c) 2000, Frank Warmerdam <warmerdam@pobox.com>
9 : * Copyright (c) 2011, Even Rouault <even dot rouault at spatialys.com>
10 : *
11 : * SPDX-License-Identifier: MIT
12 : ****************************************************************************/
13 :
14 : #include "cpl_port.h"
15 : #include "gdal_alg_priv.h"
16 :
17 : #include <cmath>
18 : #include <cstdlib>
19 : #include <cstring>
20 :
21 : #include <algorithm>
22 : #include <set>
23 : #include <utility>
24 : #include <vector>
25 :
26 : #include "gdal_alg.h"
27 :
28 : /************************************************************************/
29 : /* dllImageFilledPolygon() */
30 : /* */
31 : /* Perform scanline conversion of the passed multi-ring */
32 : /* polygon. Note the polygon does not need to be explicitly */
33 : /* closed. The scanline function will be called with */
34 : /* horizontal scanline chunks which may not be entirely */
35 : /* contained within the valid raster area (in the X */
36 : /* direction). */
37 : /* */
38 : /* NEW: Nodes' coordinate are kept as double in order */
39 : /* to compute accurately the intersections with the lines */
40 : /* */
41 : /* A pixel is considered inside a polygon if its center */
42 : /* falls inside the polygon. This is robust unless */
43 : /* the nodes are placed in the center of the pixels in which */
44 : /* case, due to numerical inaccuracies, it's hard to predict */
45 : /* if the pixel will be considered inside or outside the shape. */
46 : /************************************************************************/
47 :
48 : /*
49 : * NOTE: This code was originally adapted from the gdImageFilledPolygon()
50 : * function in libgd.
51 : *
52 : * http://www.boutell.com/gd/
53 : *
54 : * It was later adapted for direct inclusion in GDAL and relicensed under
55 : * the GDAL MIT license (pulled from the OpenEV distribution).
56 : */
57 :
58 99 : void GDALdllImageFilledPolygon(int nRasterXSize, int nRasterYSize,
59 : int nPartCount, const int *panPartSize,
60 : const double *padfX, const double *padfY,
61 : const double *dfVariant,
62 : llScanlineFunc pfnScanlineFunc, void *pCBData,
63 : bool bAvoidBurningSamePoints)
64 : {
65 99 : if (!nPartCount)
66 : {
67 0 : return;
68 : }
69 :
70 99 : int n = 0;
71 206 : for (int part = 0; part < nPartCount; part++)
72 107 : n += panPartSize[part];
73 :
74 198 : std::vector<int> polyInts(n);
75 198 : std::vector<int> polyInts2;
76 99 : if (bAvoidBurningSamePoints)
77 12 : polyInts2.resize(n);
78 :
79 99 : double dminy = padfY[0];
80 99 : double dmaxy = padfY[0];
81 6632 : for (int i = 1; i < n; i++)
82 : {
83 6533 : if (padfY[i] < dminy)
84 : {
85 901 : dminy = padfY[i];
86 : }
87 6533 : if (padfY[i] > dmaxy)
88 : {
89 1322 : dmaxy = padfY[i];
90 : }
91 : }
92 99 : int miny = static_cast<int>(dminy);
93 99 : int maxy = static_cast<int>(dmaxy);
94 :
95 99 : if (miny < 0)
96 9 : miny = 0;
97 99 : if (maxy >= nRasterYSize)
98 15 : maxy = nRasterYSize - 1;
99 :
100 99 : int minx = 0;
101 99 : const int maxx = nRasterXSize - 1;
102 :
103 : // Fix in 1.3: count a vertex only once.
104 8780 : for (int y = miny; y <= maxy; y++)
105 : {
106 8681 : int partoffset = 0;
107 :
108 8681 : const double dy = y + 0.5; // Center height of line.
109 :
110 8681 : int part = 0;
111 8681 : int ints = 0;
112 8681 : int ints2 = 0;
113 :
114 6961600 : for (int i = 0; i < n; i++)
115 : {
116 6952920 : if (i == partoffset + panPartSize[part])
117 : {
118 114 : partoffset += panPartSize[part];
119 114 : part++;
120 : }
121 :
122 6952920 : int ind1 = 0;
123 6952920 : int ind2 = 0;
124 6952920 : if (i == partoffset)
125 : {
126 8795 : ind1 = partoffset + panPartSize[part] - 1;
127 8795 : ind2 = partoffset;
128 : }
129 : else
130 : {
131 6944130 : ind1 = i - 1;
132 6944130 : ind2 = i;
133 : }
134 :
135 6952920 : double dy1 = padfY[ind1];
136 6952920 : double dy2 = padfY[ind2];
137 :
138 6952920 : if ((dy1 < dy && dy2 < dy) || (dy1 > dy && dy2 > dy))
139 6935520 : continue;
140 :
141 17478 : double dx1 = 0.0;
142 17478 : double dx2 = 0.0;
143 17478 : if (dy1 < dy2)
144 : {
145 8699 : dx1 = padfX[ind1];
146 8699 : dx2 = padfX[ind2];
147 : }
148 8779 : else if (dy1 > dy2)
149 : {
150 8699 : std::swap(dy1, dy2);
151 8699 : dx2 = padfX[ind1];
152 8699 : dx1 = padfX[ind2];
153 : }
154 : else // if( fabs(dy1-dy2) < 1.e-6 )
155 : {
156 :
157 : // AE: DO NOT skip bottom horizontal segments
158 : // -Fill them separately-
159 80 : if (padfX[ind1] > padfX[ind2])
160 : {
161 24 : const int horizontal_x1 =
162 24 : static_cast<int>(floor(padfX[ind2] + 0.5));
163 24 : const int horizontal_x2 =
164 24 : static_cast<int>(floor(padfX[ind1] + 0.5));
165 :
166 24 : if ((horizontal_x1 > maxx) || (horizontal_x2 <= minx))
167 0 : continue;
168 :
169 : // Fill the horizontal segment (separately from the rest).
170 24 : if (bAvoidBurningSamePoints)
171 : {
172 10 : polyInts2[ints2++] = horizontal_x1;
173 10 : polyInts2[ints2++] = horizontal_x2;
174 : }
175 : else
176 : {
177 14 : pfnScanlineFunc(
178 : pCBData, y, horizontal_x1, horizontal_x2 - 1,
179 : dfVariant == nullptr ? 0 : dfVariant[0]);
180 : }
181 : }
182 : // else: Skip top horizontal segments.
183 : // They are already filled in the regular loop.
184 80 : continue;
185 : }
186 :
187 17398 : if (dy < dy2 && dy >= dy1)
188 : {
189 17342 : const double intersect =
190 17342 : (dy - dy1) * (dx2 - dx1) / (dy2 - dy1) + dx1;
191 :
192 17342 : polyInts[ints++] = static_cast<int>(floor(intersect + 0.5));
193 : }
194 : }
195 :
196 8681 : std::sort(polyInts.begin(), polyInts.begin() + ints);
197 8681 : std::sort(polyInts2.begin(), polyInts2.begin() + ints2);
198 :
199 17352 : for (int i = 0; i + 1 < ints; i += 2)
200 : {
201 8671 : if (polyInts[i] <= maxx && polyInts[i + 1] > minx)
202 : {
203 8003 : pfnScanlineFunc(pCBData, y, polyInts[i], polyInts[i + 1] - 1,
204 : dfVariant == nullptr ? 0 : dfVariant[0]);
205 : }
206 : }
207 :
208 8691 : for (int i2 = 0, i = 0; i2 + 1 < ints2; i2 += 2)
209 : {
210 10 : if (polyInts2[i2] <= maxx && polyInts2[i2 + 1] > minx)
211 : {
212 : // "synchronize" polyInts[i] with polyInts2[i2]
213 10 : while (i + 1 < ints && polyInts[i] < polyInts2[i2])
214 0 : i += 2;
215 : // Only burn if we don't have a common segment between
216 : // polyInts[] and polyInts2[]
217 10 : if (i + 1 >= ints || polyInts[i] != polyInts2[i2])
218 : {
219 4 : pfnScanlineFunc(pCBData, y, polyInts2[i2],
220 2 : polyInts2[i2 + 1] - 1,
221 : dfVariant == nullptr ? 0 : dfVariant[0]);
222 : }
223 : }
224 : }
225 : }
226 : }
227 :
228 : /************************************************************************/
229 : /* GDALdllImagePoint() */
230 : /************************************************************************/
231 :
232 5 : void GDALdllImagePoint(int nRasterXSize, int nRasterYSize, int nPartCount,
233 : const int * /*panPartSize*/, const double *padfX,
234 : const double *padfY, const double *padfVariant,
235 : llPointFunc pfnPointFunc, void *pCBData)
236 : {
237 10 : for (int i = 0; i < nPartCount; i++)
238 : {
239 5 : const int nX = static_cast<int>(floor(padfX[i]));
240 5 : const int nY = static_cast<int>(floor(padfY[i]));
241 5 : double dfVariant = 0.0;
242 5 : if (padfVariant != nullptr)
243 0 : dfVariant = padfVariant[i];
244 :
245 5 : if (0 <= nX && nX < nRasterXSize && 0 <= nY && nY < nRasterYSize)
246 5 : pfnPointFunc(pCBData, nY, nX, dfVariant);
247 : }
248 5 : }
249 :
250 : /************************************************************************/
251 : /* GDALdllImageLine() */
252 : /************************************************************************/
253 :
254 1874 : void GDALdllImageLine(int nRasterXSize, int nRasterYSize, int nPartCount,
255 : const int *panPartSize, const double *padfX,
256 : const double *padfY, const double *padfVariant,
257 : llPointFunc pfnPointFunc, void *pCBData)
258 : {
259 1874 : if (!nPartCount)
260 0 : return;
261 :
262 3748 : for (int i = 0, n = 0; i < nPartCount; n += panPartSize[i++])
263 : {
264 48667 : for (int j = 1; j < panPartSize[i]; j++)
265 : {
266 46793 : int iX = static_cast<int>(floor(padfX[n + j - 1]));
267 46793 : int iY = static_cast<int>(floor(padfY[n + j - 1]));
268 :
269 46793 : const int iX1 = static_cast<int>(floor(padfX[n + j]));
270 46793 : const int iY1 = static_cast<int>(floor(padfY[n + j]));
271 :
272 46793 : double dfVariant = 0.0;
273 46793 : double dfVariant1 = 0.0;
274 46793 : if (padfVariant != nullptr &&
275 46758 : static_cast<GDALRasterizeInfo *>(pCBData)->eBurnValueSource !=
276 : GBV_UserBurnValue)
277 : {
278 46758 : dfVariant = padfVariant[n + j - 1];
279 46758 : dfVariant1 = padfVariant[n + j];
280 : }
281 :
282 46793 : int nDeltaX = std::abs(iX1 - iX);
283 46793 : int nDeltaY = std::abs(iY1 - iY);
284 :
285 : // Step direction depends on line direction.
286 46793 : const int nXStep = (iX > iX1) ? -1 : 1;
287 46793 : const int nYStep = (iY > iY1) ? -1 : 1;
288 :
289 : // Determine the line slope.
290 46793 : if (nDeltaX >= nDeltaY)
291 : {
292 38876 : const int nXError = nDeltaY << 1;
293 38876 : const int nYError = nXError - (nDeltaX << 1);
294 38876 : int nError = nXError - nDeltaX;
295 : // == 0 makes clang -fcatch-undefined-behavior -ftrapv happy,
296 : // but if it is == 0, dfDeltaVariant is not really used, so any
297 : // value is okay.
298 38876 : const double dfDeltaVariant =
299 38876 : nDeltaX == 0 ? 0.0 : (dfVariant1 - dfVariant) / nDeltaX;
300 :
301 : // Do not burn the end point, unless we are in the last
302 : // segment. This is to avoid burning twice intermediate points,
303 : // which causes artifacts in Add mode
304 38876 : if (j != panPartSize[i] - 1)
305 : {
306 37185 : nDeltaX--;
307 : }
308 :
309 67162 : while (nDeltaX-- >= 0)
310 : {
311 28286 : if (0 <= iX && iX < nRasterXSize && 0 <= iY &&
312 : iY < nRasterYSize)
313 28089 : pfnPointFunc(pCBData, iY, iX, dfVariant);
314 :
315 28286 : dfVariant += dfDeltaVariant;
316 28286 : iX += nXStep;
317 28286 : if (nError > 0)
318 : {
319 11024 : iY += nYStep;
320 11024 : nError += nYError;
321 : }
322 : else
323 : {
324 17262 : nError += nXError;
325 : }
326 : }
327 : }
328 : else
329 : {
330 7917 : const int nXError = nDeltaX << 1;
331 7917 : const int nYError = nXError - (nDeltaY << 1);
332 7917 : int nError = nXError - nDeltaY;
333 : // == 0 makes clang -fcatch-undefined-behavior -ftrapv happy,
334 : // but if it is == 0, dfDeltaVariant is not really used, so any
335 : // value is okay.
336 7917 : double dfDeltaVariant =
337 7917 : nDeltaY == 0 ? 0.0 : (dfVariant1 - dfVariant) / nDeltaY;
338 :
339 : // Do not burn the end point, unless we are in the last
340 : // segment. This is to avoid burning twice intermediate points,
341 : // which causes artifacts in Add mode
342 7917 : if (j != panPartSize[i] - 1)
343 : {
344 7734 : nDeltaY--;
345 : }
346 :
347 16207 : while (nDeltaY-- >= 0)
348 : {
349 8290 : if (0 <= iX && iX < nRasterXSize && 0 <= iY &&
350 : iY < nRasterYSize)
351 8201 : pfnPointFunc(pCBData, iY, iX, dfVariant);
352 :
353 8290 : dfVariant += dfDeltaVariant;
354 8290 : iY += nYStep;
355 8290 : if (nError > 0)
356 : {
357 35 : iX += nXStep;
358 35 : nError += nYError;
359 : }
360 : else
361 : {
362 8255 : nError += nXError;
363 : }
364 : }
365 : }
366 : }
367 : }
368 : }
369 :
370 : /************************************************************************/
371 : /* GDALdllImageLineAllTouched() */
372 : /* */
373 : /* This alternate line drawing algorithm attempts to ensure */
374 : /* that every pixel touched at all by the line will get set. */
375 : /* @param padfVariant should contain the values that are to be */
376 : /* added to the burn value. The values along the line between the */
377 : /* points will be linearly interpolated. These values are used */
378 : /* only if pCBData->eBurnValueSource is set to something other */
379 : /* than GBV_UserBurnValue. If NULL is passed, a monotonous line */
380 : /* will be drawn with the burn value. */
381 : /************************************************************************/
382 :
383 33 : void GDALdllImageLineAllTouched(int nRasterXSize, int nRasterYSize,
384 : int nPartCount, const int *panPartSize,
385 : const double *padfX, const double *padfY,
386 : const double *padfVariant,
387 : llPointFunc pfnPointFunc, void *pCBData,
388 : bool bAvoidBurningSamePoints,
389 : bool bIntersectOnly)
390 :
391 : {
392 : // This is an epsilon to detect geometries that are aligned with pixel
393 : // coordinates. Hard to find the right value. We put it to that value
394 : // to satisfy the scenarios of https://github.com/OSGeo/gdal/issues/7523
395 : // and https://github.com/OSGeo/gdal/issues/6414
396 33 : constexpr double EPSILON_INTERSECT_ONLY = 1e-4;
397 :
398 33 : if (!nPartCount)
399 0 : return;
400 :
401 66 : for (int i = 0, n = 0; i < nPartCount; n += panPartSize[i++])
402 : {
403 66 : std::set<std::pair<int, int>> lastBurntPoints;
404 66 : std::set<std::pair<int, int>> newBurntPoints;
405 :
406 158 : for (int j = 1; j < panPartSize[i]; j++)
407 : {
408 125 : lastBurntPoints = std::move(newBurntPoints);
409 125 : newBurntPoints.clear();
410 :
411 125 : double dfX = padfX[n + j - 1];
412 125 : double dfY = padfY[n + j - 1];
413 :
414 125 : double dfXEnd = padfX[n + j];
415 125 : double dfYEnd = padfY[n + j];
416 :
417 125 : double dfVariant = 0.0;
418 125 : double dfVariantEnd = 0.0;
419 125 : if (padfVariant != nullptr &&
420 0 : static_cast<GDALRasterizeInfo *>(pCBData)->eBurnValueSource !=
421 : GBV_UserBurnValue)
422 : {
423 0 : dfVariant = padfVariant[n + j - 1];
424 0 : dfVariantEnd = padfVariant[n + j];
425 : }
426 :
427 : // Skip segments that are off the target region.
428 125 : if ((dfY < 0.0 && dfYEnd < 0.0) ||
429 124 : (dfY > nRasterYSize && dfYEnd > nRasterYSize) ||
430 123 : (dfX < 0.0 && dfXEnd < 0.0) ||
431 122 : (dfX > nRasterXSize && dfXEnd > nRasterXSize))
432 114 : continue;
433 :
434 : // Swap if needed so we can proceed from left2right (X increasing)
435 121 : if (dfX > dfXEnd)
436 : {
437 35 : std::swap(dfX, dfXEnd);
438 35 : std::swap(dfY, dfYEnd);
439 35 : std::swap(dfVariant, dfVariantEnd);
440 : }
441 :
442 : // Special case for vertical lines.
443 121 : if (floor(dfX) == floor(dfXEnd) || fabs(dfX - dfXEnd) < .01)
444 : {
445 57 : if (bIntersectOnly)
446 : {
447 48 : if (std::abs(dfX - std::round(dfX)) <
448 57 : EPSILON_INTERSECT_ONLY &&
449 9 : std::abs(dfXEnd - std::round(dfXEnd)) <
450 : EPSILON_INTERSECT_ONLY)
451 9 : continue;
452 : }
453 :
454 48 : if (dfYEnd < dfY)
455 : {
456 25 : std::swap(dfY, dfYEnd);
457 25 : std::swap(dfVariant, dfVariantEnd);
458 : }
459 :
460 48 : const int iX = static_cast<int>(floor(dfXEnd));
461 48 : int iY = static_cast<int>(floor(dfY));
462 48 : int iYEnd =
463 48 : static_cast<int>(floor(dfYEnd - EPSILON_INTERSECT_ONLY));
464 :
465 48 : if (iX < 0 || iX >= nRasterXSize)
466 0 : continue;
467 :
468 48 : double dfDeltaVariant = 0.0;
469 48 : if (dfYEnd - dfY > 0.0)
470 48 : dfDeltaVariant = (dfVariantEnd - dfVariant) /
471 48 : (dfYEnd - dfY); // Per unit change in iY.
472 :
473 : // Clip to the borders of the target region.
474 48 : if (iY < 0)
475 0 : iY = 0;
476 48 : if (iYEnd >= nRasterYSize)
477 0 : iYEnd = nRasterYSize - 1;
478 48 : dfVariant += dfDeltaVariant * (iY - dfY);
479 :
480 48 : if (padfVariant == nullptr)
481 : {
482 561 : for (; iY <= iYEnd; iY++)
483 : {
484 513 : if (bAvoidBurningSamePoints)
485 : {
486 136 : auto yx = std::pair<int, int>(iY, iX);
487 136 : if (lastBurntPoints.find(yx) !=
488 272 : lastBurntPoints.end())
489 : {
490 11 : continue;
491 : }
492 125 : newBurntPoints.insert(yx);
493 : }
494 502 : pfnPointFunc(pCBData, iY, iX, 0.0);
495 : }
496 : }
497 : else
498 : {
499 0 : for (; iY <= iYEnd; iY++, dfVariant += dfDeltaVariant)
500 : {
501 0 : if (bAvoidBurningSamePoints)
502 : {
503 0 : auto yx = std::pair<int, int>(iY, iX);
504 0 : if (lastBurntPoints.find(yx) !=
505 0 : lastBurntPoints.end())
506 : {
507 0 : continue;
508 : }
509 0 : newBurntPoints.insert(yx);
510 : }
511 0 : pfnPointFunc(pCBData, iY, iX, dfVariant);
512 : }
513 : }
514 :
515 48 : continue; // Next segment.
516 : }
517 :
518 64 : const double dfDeltaVariant =
519 64 : (dfVariantEnd - dfVariant) /
520 64 : (dfXEnd - dfX); // Per unit change in iX.
521 :
522 : // Special case for horizontal lines.
523 64 : if (floor(dfY) == floor(dfYEnd) || fabs(dfY - dfYEnd) < .01)
524 : {
525 53 : if (bIntersectOnly)
526 : {
527 44 : if (std::abs(dfY - std::round(dfY)) <
528 49 : EPSILON_INTERSECT_ONLY &&
529 5 : std::abs(dfYEnd - std::round(dfYEnd)) <
530 : EPSILON_INTERSECT_ONLY)
531 5 : continue;
532 : }
533 :
534 48 : if (dfXEnd < dfX)
535 : {
536 0 : std::swap(dfX, dfXEnd);
537 0 : std::swap(dfVariant, dfVariantEnd);
538 : }
539 :
540 48 : int iX = static_cast<int>(floor(dfX));
541 48 : const int iY = static_cast<int>(floor(dfY));
542 48 : int iXEnd =
543 48 : static_cast<int>(floor(dfXEnd - EPSILON_INTERSECT_ONLY));
544 :
545 48 : if (iY < 0 || iY >= nRasterYSize)
546 0 : continue;
547 :
548 : // Clip to the borders of the target region.
549 48 : if (iX < 0)
550 0 : iX = 0;
551 48 : if (iXEnd >= nRasterXSize)
552 0 : iXEnd = nRasterXSize - 1;
553 48 : dfVariant += dfDeltaVariant * (iX - dfX);
554 :
555 48 : if (padfVariant == nullptr)
556 : {
557 605 : for (; iX <= iXEnd; iX++)
558 : {
559 557 : if (bAvoidBurningSamePoints)
560 : {
561 134 : auto yx = std::pair<int, int>(iY, iX);
562 134 : if (lastBurntPoints.find(yx) !=
563 268 : lastBurntPoints.end())
564 : {
565 8 : continue;
566 : }
567 126 : newBurntPoints.insert(yx);
568 : }
569 549 : pfnPointFunc(pCBData, iY, iX, 0.0);
570 : }
571 : }
572 : else
573 : {
574 0 : for (; iX <= iXEnd; iX++, dfVariant += dfDeltaVariant)
575 : {
576 0 : if (bAvoidBurningSamePoints)
577 : {
578 0 : auto yx = std::pair<int, int>(iY, iX);
579 0 : if (lastBurntPoints.find(yx) !=
580 0 : lastBurntPoints.end())
581 : {
582 0 : continue;
583 : }
584 0 : newBurntPoints.insert(yx);
585 : }
586 0 : pfnPointFunc(pCBData, iY, iX, dfVariant);
587 : }
588 : }
589 :
590 48 : continue; // Next segment.
591 : }
592 :
593 : /* --------------------------------------------------------------------
594 : */
595 : /* General case - left to right sloped. */
596 : /* --------------------------------------------------------------------
597 : */
598 11 : const double dfSlope = (dfYEnd - dfY) / (dfXEnd - dfX);
599 :
600 : // Clip segment in X.
601 11 : if (dfXEnd > nRasterXSize)
602 : {
603 0 : dfYEnd -= (dfXEnd - nRasterXSize) * dfSlope;
604 0 : dfXEnd = nRasterXSize;
605 : }
606 11 : if (dfX < 0.0)
607 : {
608 1 : dfY += (0.0 - dfX) * dfSlope;
609 1 : dfVariant += dfDeltaVariant * (0.0 - dfX);
610 1 : dfX = 0.0;
611 : }
612 :
613 : // Clip segment in Y.
614 11 : if (dfYEnd > dfY)
615 : {
616 6 : if (dfY < 0.0)
617 : {
618 0 : const double dfDiffX = (0.0 - dfY) / dfSlope;
619 0 : dfX += dfDiffX;
620 0 : dfVariant += dfDeltaVariant * dfDiffX;
621 0 : dfY = 0.0;
622 : }
623 6 : if (dfYEnd >= nRasterYSize)
624 : {
625 2 : dfXEnd += (dfYEnd - nRasterYSize) / dfSlope;
626 2 : if (dfXEnd > nRasterXSize)
627 2 : dfXEnd = nRasterXSize;
628 : // dfYEnd is no longer used afterwards, but for
629 : // consistency it should be:
630 : // dfYEnd = nRasterXSize;
631 : }
632 : }
633 : else
634 : {
635 5 : if (dfY >= nRasterYSize)
636 : {
637 0 : const double dfDiffX = (nRasterYSize - dfY) / dfSlope;
638 0 : dfX += dfDiffX;
639 0 : dfVariant += dfDeltaVariant * dfDiffX;
640 0 : dfY = nRasterYSize;
641 : }
642 5 : if (dfYEnd < 0.0)
643 : {
644 0 : dfXEnd -= (dfYEnd - 0) / dfSlope;
645 : // dfYEnd is no longer used afterwards, but for
646 : // consistency it should be:
647 : // dfYEnd = 0.0;
648 : }
649 : }
650 :
651 : // Step from pixel to pixel.
652 3299 : while (dfX >= 0.0 && dfX < dfXEnd)
653 : {
654 3288 : const int iX = static_cast<int>(floor(dfX));
655 3288 : const int iY = static_cast<int>(floor(dfY));
656 :
657 : // Burn in the current point.
658 : // We should be able to drop the Y check because we clipped
659 : // in Y, but there may be some error with all the small steps.
660 3288 : if (iY >= 0 && iY < nRasterYSize)
661 : {
662 3287 : if (bAvoidBurningSamePoints)
663 : {
664 29 : auto yx = std::pair<int, int>(iY, iX);
665 57 : if (lastBurntPoints.find(yx) == lastBurntPoints.end() &&
666 57 : newBurntPoints.find(yx) == newBurntPoints.end())
667 : {
668 19 : newBurntPoints.insert(yx);
669 19 : pfnPointFunc(pCBData, iY, iX, dfVariant);
670 : }
671 : }
672 : else
673 : {
674 3258 : pfnPointFunc(pCBData, iY, iX, dfVariant);
675 : }
676 : }
677 :
678 3288 : double dfStepX = floor(dfX + 1.0) - dfX;
679 3288 : double dfStepY = dfStepX * dfSlope;
680 :
681 : // Step to right pixel without changing scanline?
682 3288 : if (static_cast<int>(floor(dfY + dfStepY)) == iY)
683 : {
684 2715 : dfX += dfStepX;
685 2715 : dfY += dfStepY;
686 2715 : dfVariant += dfDeltaVariant * dfStepX;
687 : }
688 573 : else if (dfSlope < 0)
689 : {
690 42 : dfStepY = iY - dfY;
691 42 : if (dfStepY > -0.000000001)
692 22 : dfStepY = -0.000000001;
693 :
694 42 : dfStepX = dfStepY / dfSlope;
695 42 : dfX += dfStepX;
696 42 : dfY += dfStepY;
697 42 : dfVariant += dfDeltaVariant * dfStepX;
698 : }
699 : else
700 : {
701 531 : dfStepY = (iY + 1) - dfY;
702 531 : if (dfStepY < 0.000000001)
703 0 : dfStepY = 0.000000001;
704 :
705 531 : dfStepX = dfStepY / dfSlope;
706 531 : dfX += dfStepX;
707 531 : dfY += dfStepY;
708 531 : dfVariant += dfDeltaVariant * dfStepX;
709 : }
710 : } // Next step along segment.
711 : } // Next segment.
712 : } // Next part.
713 : }
|
