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.

5Comments
Gautam Choudhary @gautamchoudhary 11 Sep 2017 01:58 pm

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 every \(x-coordinate\). Hence, total painted pixels are \(\Delta x + 1\) . (Similarly, when slope > 1, it is \(\Delta y + 1\))

 

For 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-case manner i.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 20 pixels can be symmetrically added to some 20 horizontal steps whose length is already 27(intermediate stairs) and 13(terminal stairs). Hence, their length becomes 28 (and 14 respectively). So, the required answer is 28.

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 green line with slope 1 paints pixel by incrementing 1 in \(x\) as well as \(y\) direction. Horizontal step is of length 1

2. The blue line with slope 4 paints pixel by incrementing ~4 in \(x\)  and 1 in \(y\) direction. Horizontal step is of length 4 (Notice that the last and first stair is of length 2)

3. The yellow line with slope intermediate between 1 and 4 paints pixel accordingly and without loss of symmetry. Horizontal step is of length 1 as well as 2

Purushottam Abhisheikh @abhisheikh 11 Sep 2017 07:35 pm

I 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.

Ranita Biswas @ranita 11 Sep 2017 08:20 am

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.

Gautam Choudhary @gautamchoudhary 11 Sep 2017 08:26 am

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.

Purushottam Abhisheikh @abhisheikh 11 Sep 2017 10:30 pm

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\).