##### Number of pixels in digital straight line segment

Find the number of pixels of the (minimally connected) digital straight line segment connecting (0, 0) and (1007, 37). Find out the maximum number of pixels among them, which are on the same horizontal line.

Will be updated soon.

Try answering in the comments.

The first part of minimally connected pixels is pretty straight forward as both DDA and Bresenham's algorithm provide a set of points that are minimally connected which is equal to \(max(\Delta x, \Delta y) + 1\) .

Reason:In both the algorithms, we always paint the next pixel by incrementing \(x-coordinate\) (assuming slope < 1). In other words, we paint a \(y-coordinate\) for for\(x-coordinate\). Hence, total painted pixels are \(\Delta x + 1\) . (Similarly, when slope > 1, it is \(\Delta y + 1\))everyFor the second part, the intuition behind is very simple. To put it differently, for drawing a line segment from \((x_1, y_1)\) to \((x_2, y_2)\) and assuming slope < 1, we have to only paint \((\Delta x + 1)\) pixels with suitable \(y\) coordinates.

Take the line segment asked in question i.e. from \((0, 0)\) to \((1007, 37)\) . In total we have to paint \((\Delta x + 1) = 1007 + 1 = 1008\)pixels. We paint in

stair-casemanneri.e. some set of pixels are at the same horizontal with the condition that first and last staircase is of half the average length.Total levels of staircase \(= (\Delta y + 1) = (37 + 1) = 38\)levels or steps.

Let the length of average pixel be \(n\) . So, the equation follows:

Total pixels to be painted = Sum of pixels at each step or staircase level

\(1008 = (1)*n/2 + (38-2)*n + (1)*n/2\)[Read it as first stair is halfway painted while next subsequent stairs are fully painted and finally last stair is also half painted to maintain symmetry]. Solving this equation, we have \(n = 27.24\)

So, length of first and last staircase \(= floor(n/2) = floor(27.24\ /\ 2) = floor(13.62) = 13\)

Length of intermediate staircase step \(= floor(n) = floor(27.24) = 27\)

Now, the remaining pixels are \(= 1008 - (1*13 + 36*27 + 1*13) = 1008 - (998) = 20\)

Now, each of these

20pixels can be symmetrically added to some 20 horizontal steps whose length is already27(intermediate stairs) and13(terminal stairs). Hence, their length becomes28 (and 14 respectively). So, the required answer is28.To generalize this rule, the max number of pixels on same horizontal is \(ceil (\ max({{\Delta x + 1} \over {\Delta y}}, {{\Delta y + 1} \over {\Delta x}}))\)

To visualize, the image shows pixelated line segments with different slopes all of which are drawn using DDA algorithm.

1. The

greenline with slope1paints pixel by incrementing 1 in \(x\) as well as \(y\) direction. Horizontal step is of length12. The

blueline with slope4paints pixel by incrementing ~4 in \(x\) and 1 in \(y\) direction. Horizontal step is of length4(Notice that the last and first stair is of length 2)3. The

yellowline with slopeintermediate between 1 and 4paints pixel accordingly and without loss of symmetry. Horizontal step is of length1as well as2I don't think the generalised answer is still correct. You can simply check for lines whose inverse of slope (i.e. \(\frac{\Delta x}{\Delta y}\)) is an integer. Correct answer should be \(\left\lceil max(\frac{\Delta x}{\Delta y}, \frac{\Delta y}{\Delta x}) \right\rceil \). For example for line between points \((0,0)\) and (20,2) the answer should be 10.

You are very close to the answer. But, there is one catch; the first row of pixels (at y = 0) and the last row of pixels (at y = 37) are not full length. You may try to modify the approach accordingly to get to the correct answer. Very good presentation, by the way.

Yes, ma'am I got that, they are half the average length due to the shorter window size of [0, 0.5] in case of starting point and [1006.5, 1007] in case of last point. I'll shortly update it.

A slight modification (modifications are in

bold) to the solution provided by ma'am in the class:Lets assume below situation for any line \(y = mx,\; m\le1\) (if line is not passing through \((0,0)\) then translate it so that it passes through origin since translation will not change relative properties of pixels):

Here \(i,\ j \) and \(h\) are integers.

As all the pixels in the horizontal line \(y\;=\;j\) from \(x \;=\;i \quad\text{to} \quad x\;=i+h\)should be colored.

So, \(j-mi \le 0.5\quad \text{and} \quad m(i+h) - j \lt 0.5\)

.Using both we get,\(h\lt\frac{1}{m} \quad \text{or} \quad h\lt \frac{\Delta x}{\Delta y}\)Since h is maximum, there are two cases:If \(\frac{\Delta x}{\Delta y}\) is an integer then \(h = \frac{\Delta x}{\Delta y}-1\) otherwise \(h = \left\lfloor \frac{\Delta x}{\Delta y}\right\rfloor\).So \(h = \left\lceil \frac{\Delta x}{\Delta y}\right\rceil -1\).And total number of pixels = \(h+1 = \left\lceil \frac{\Delta x}{\Delta y}\right\rceil\).