Discretizing a line segment with pixels which satisfies the Pythagorean theorem

Question

There are plenty of line drawing algorithms to discretize line segments using pixels. The Bresenham's algorithm gives a line where the number of pixels in the segment is the same as its width (in x-direction) or height (y-direction), whichever is largest.

One can also imagine an algorithm where one starts in one of the points, and choose the lattice path between start and end point which minimizes total distance squared of pixel centers to the true geometric line. The number of pixels produced is the width+height, as we have a lattice path.

Note that the (geometric) length of the line segment is somewhere between the number of pixels produced by the two approaches above.

My question is, is there some (standard) algorithm where the number of pixels in the constructed line segment is equal to the the (rounded to nearest integer) length of the line segment? We want the line-segment to be connected, in the sense that every x-coordinate between the endpoints are covered by at least one pixel (and same for y-coordinates).

Of course, one can take the lattice path approach above, and iteratively remove pixels furthest from the true geometric line, but this seems inefficient, and might not guarantee connectednes.

Answer 1

I think this question makes sense if we extend the planar grid with a certain collection of diagonals, and require that the drawn segment between two points always use a shortest path in this graph. It was posed in this form by Pach, Pollack and Spencer 30 years ago, and it is still open.

Answer 2

I might not really understand the question, but one very simple-minded idea to plot a line segment using $n$ pixels is to find $n$ points evenly spaced along the line segment, and then replace each one with the nearest lattice point. As long as $n$ is greater than the horizontal distance plus one, successive points will be less than $1$ unit apart horizontally and therefore the result will be horizontally connected, and similarly for vertical connectedness.

Of course, if $n$ is too large then multiple points could be sent to the same pixel. But if $n$ is the length of the segment then non-adjacent points will be two units apart and cannot have the same closest lattice point. There could be adjacent pairs that go to the same pixel; in that case, if we really want exactly $n$ pixels we could adopt a rule for moving the second point. E.g., if the line goes from $(0,0)$ to $(a,b)$ with $0 \leq b \leq a$, then whenever the closest lattice point has already been taken, plot the pixel just above it, or whatever.

The case where $a = b$ might be good to think about. There are only $a + 1$ lattice points on the $x = y$ diagonal between $(0,0)$ and $(a,a)$, so if you insist on plotting $\sqrt{2}a$ points you'll have to do something like what I said above.

Answer 3

Not certain this answers your question, but it might be a step toward your goal:

Tobias Christ, Dömötör Pálvölgyi, Miloš Stojaković. "Digitalizing line segments." Electronic Notes in Discrete Mathematics Volume 38, 1 December 2011, Pages 273-278. DOI link. Preliminary arXiv abs.

Abstract. We introduce a novel and general approach for digitalization of line segments in the plane that satisfies a set of axioms naturally arising from Euclidean axioms. In particular, we show how to derive such a system of digital segments from any total order on the integers. As a consequence, using a well-chosen total order, we manage to define a system of digital segments such that all digital segments are, in Hausdorff metric, optimally close to their corresponding Euclidean segments, thus giving an explicit construction that resolves the main question of [J. Chun, M. Korman, M. Nöllenburg, and T. Tokuyama. Consistent digital rays. Discrete Comput. Geom., 42(3):359–378, 2009].

     

Answer 4

let the pixels be unit squares with integral corner coordinates, and the line segments be defined by two points $\lbrace p_0:=(x_0,\,y_0),\ p_1:=(x_1,\,y_1)\,|\,x_i,y_i\in\mathbb{R}\rbrace$.

The extremal cases are then $\lbrace p_0=(1.0-\varepsilon,\,0),\ p_1=(n+\varepsilon,\,0)\rbrace$ requiring $n+1$ pixel to cover a line-segment of length $n-1+2\varepsilon$; in that case the rounded nearest integer length would be $n-1$ for sufficiently small positive $\epsilon$ requiring $n+1$ pixels for covering, thus disproving the existence of a line-drawing algorithm with the sought properties.

The other extreme are line-segments with slope 1: let $\lbrace p_0,\,p_1\rbrace = \lbrace (+\varepsilon,\,+\varepsilon),\ (n+1-\varepsilon,\,n+1-\varepsilon)\rbrace$ requiring $n+1$ pixel for covering a rounded length of $(n+1-2\varepsilon)\sqrt{2}$ which implies that the absolute error can grow linearly with the length of the line-segment.

Addendum:

one aspect of the question, that hasn't been made explicit, is the set of pixels generated by Bresenham's algorithm are 8-way connected, meaning that removing from the a discrete set of points may disconnect them and it also means the set of generated pixels need not cover the line entirely.

Now to the question for a line-rasterization that simultaneously approximates euclidean length via the number of generated pixels:

whenever the a pixel generated by the Bresenham algorithm only shares a corner with the previously generated one, the difference between partial segment-length and number of generated pixels is compared and, whenever that error exceeds $1$ we add of the two pixels that are adjacent to the current one and the previous one, the one whose center is closer to the line-segment.