I am considering implementing my own version of Bresenham's line drawing algorithm, found here, my one question is does the algorithm guarantee that both endpoints will be covered/drawn. I am doubting this because of the error accumulation factor (decision variable), but I may be wrong.
3
-
$\begingroup$ Which error accumulation factor? $\endgroup$– plopAug 2, 2020 at 1:44
-
$\begingroup$ @plop sometimes also referred to as the decision variable, my bad let me update my question $\endgroup$– yosmo78Aug 2, 2020 at 23:58
-
$\begingroup$ It sounds like you are thinking about errors as those in floating point arithmetic, but for this algorithm you only need integers. You don't need floating point arithmetic. The last endpoint is always chosen because it satisfies the equation of the line passing through it. $\endgroup$– plopAug 3, 2020 at 0:10
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Yes, Bresenham line drawing algorithm guarantees that endpoints are drawn.
The error accumulation is used for drawing and decreased after drawing a pixel, this is the core idea of the algorithm: incremental error is accumulated to avoid division operation, which is costly, but in this context it is something good and it doesn't mean that errors would damage continuity of line or lose endpoints.
The failure of Bresenham algorithm is technically possible only if floating point variable fails to add error, so $$deltaerr := abs(deltay / deltax)$$ is so small that $error := error + deltaerr$ would not increase $error$ at all, but if that happened, image is too big to fit on computer or some kind of clipping algorithm or bigger floating point variables are needed.
It is safe to assume that $\frac{deltay}{deltax} \le \frac{1}{2^{22}}$ is not going to happen.
