Vertical lines drawn with draw.line have one extra width pixel

[Terseus]

When using the line method of a Draw object on a newly created image to draw vertical lines, all lines drawn with more than 1 pixel width are one pixel widther (a 2 pixels width line is drawn with a 3 pixels width).

How to reproduce the problem:

This "proof of concept" program reproduces the problem creating a 10x10 image with a centered cross of two lines 2 pixels width, one horizontal and one vertical, where the vertical one is clearly widther than the horizontal.

from PIL import Image, ImageDraw

img = Image.new('RGB', (10, 10), (255, 255, 255))
draw = ImageDraw.Draw(img)
draw.line((0, 5, 10, 5), (0, 0, 0), 2)
draw.line((5, 0, 5, 10), (0, 0, 0), 2)
img.save("test-bad-lines.png", 'PNG')

Expected result:

A cross of two lines, both with the same width, 2 pixels.

Current result:

A cross with the horizontal line 2 pixels width and the vertical line 3 pixels width.

Additional information:

This bug only happens when drawing vertical lines with at least two pixels width.
1 pixel width vertical lines and horizontal lines of any width doesn't seem to have this problem.

[wiredfool]

Ok, I've got this reproduced as a test case. Will dig a bit.

[wiredfool]

Notes on what's going on: in Draw.c, about line 690 in ImagingDrawWideLine. The wide line is broken into a polygon with 4 corners, each corner an integral +-dx,dy from the actual endpoints. Since dx and dy are integers, a dx of 1 corresponding to a line width of 2 gives x points from x-1 to x+1, or 3 pixels wide. A line width of 3 gives dx=2, or 5 pixels. 4:2, 5:3 or 7px. I'm getting some inconsistent info out of the debugger on this one, though, the odd ones appear a pixel too high. The same thing applies for horizontal lines, but with a difference.

The polygon draw function fills the lines by drawing horizontal lines, one y value at a time. So, horizontal and vertical endpoints are treated differently here. ymin==4, ymax==6, y ranges from ymin+0.5 to ymax-0.5, so the third horizontal line is never drawn. It has issues with 3px wide lines though, they wind up 4px wide.

[aclark4life]

Last call for 2.3.0

[wiredfool]

Not happening for now. Pretty sure that this dates back to PIL code. It can probably be fixed, but it's more than a little off by one bug somewhere, it's going to take a bit of a rethink to get the line drawing code right.

[aclark4life]

Now targeting 2.4.0

[Terseus]

@wiredfool I'm trying to fix this bug but, as you said, the polygon functions seems to treat differently x and y axis, and to me this looks like the root of the problem.

However I'm not sure of the implications of changing the behavior of the polygon functions due to the possible side-effects and I'm not familiar enough with the PIL code to evaluate it, what do you think about it? If I change the polygon behavior to treat consistently both axis, can it break other Pillow parts?

[Terseus]

After a lot of learning and work, I've reached a point where I don't know what the expected behavior should be when drawing polygons, and I need to know it in order to draw lines of arbitrary width correctly.

Consider a square that goes from (2,2) to (8,8) drawn in a image with size 10x10, defined as a polygon with four vertices: (2,2), (2,8), (8,8), (8,2).

This is the result when drawn with the current master branch of Pillow (10x zoom):

The polygon is clearly inconsistent, the X size it's 1 pixel greater than the Y size.

Now, this is the result of the same polygon with my current branch after some fixes to the polygon function:

Now the polygon is consistent, it's a square as expected.

The problem is, I understand that if I draw a line from X=2 to X=8, this line should have a length of 8-2=6, but in my current implementation it ends up with a length of 7.
I tried to make it so the maximum XY coordinates are never drawn, as I read in some sites that this is how it should be done, but then other symmetrical polygons (specially diagonal rectangles of 45 inclination) end up being deformed and not symmetrical, which I think is worse.

This is my first implementation of a polygon draw algorithm so I'm really lost here, I'm not sure how a polygon should be drawn to be considered consistent.
Should I left it as is in the last example (my current branch) where the polygon ends up having 1 extra pixel in XY? Do you think it's acceptable?

[hugovk]

The problem is, I understand that if I draw a line from X=2 to X=8, this line should have a length of 8-2=6, but in my current implementation it ends up with a length of 7.

I don't think that's a problem. I'd expect the line to include both endpoints. The pixels at 2 and 8 should be filled, and all those in between. So 8-2+1=7.

0123456789
----------
--XXXXXXX-
----------

A horizontal line is a polygon with a height of only one pixel. If you squash the squares in your screenshots to one-pixel-high lines, this is the same line, from 2 to 8 inclusive.

@wiredfool, @aclark4life, comments?

[aclark4life]

Let's try getting to this for 2.5.0 due in 3 months

[hugovk]

(Correction: "Let's try getting to this for 2.5.0 due in 3 months")

[aclark4life]

Thanks, fixed

[Terseus]

Sorry, I was planning making a pull request the past week but I've been busy, if nothing goes wrong I will send it in the next days after writing some basic polygon tests.

BTW, I'd checked out the issue #463 and its problem have the same source, since the ellipses are generated as polygons with 360 edges, so probably it'll be fixed too.

@hugovk for lines it makes sense, but for polygons like the square it makes more sense to me to be (in the example) 6 pixels width/height instead of 7; I'm leaving that behavior for consistency with the rest of the library but I'm not completely satisfied with the result.

[hugovk]

I still think 7 pixels is correct for polygons: if I draw a square from X=2 to X=8, and Y=2 to Y=8, I'd expect the top-left corner to include pixel (2,2) and the bottom-right corner to include pixel (8,8).

[Terseus]

You see, that's the problem: you think and I think :)
I would be much more relaxed having some formal method to verify the correctness of simple polygons, specially triangles.

[Terseus]

Ok, I've uploaded the new version (without tests) to a new branch in my fork, just in case I don't have time to write the tests this week, so now you can test it, people :) https://github.com/Terseus/Pillow/tree/fix-367_bad-line-width

Feedback will be very appreciated.

[aclark4life]

@Terseus How about sending a pull request?

[Terseus]

@aclark4life PR sended

[hugovk]

Regarding which end-pixels to draw, we still need a definitive spec.

For starters here's the Pillow documentation (largely inherited from PIL) for ImageDraw.

Line:

Draws a line between the coordinates in the xy list.

Parameters:

• xy – Sequence of either 2-tuples like [(x, y), (x, y), ...] or numeric values like [x, y, x, y, ...].

Polygon:

The polygon outline consists of straight lines between the given coordinates, plus a straight line between the last and the first coordinate.

Parameters:

• xy – Sequence of either 2-tuples like [(x, y), (x, y), ...] or numeric values like [x, y, x, y, ...].

Rectangle:

Draws a rectangle.

Parameters:

• xy – Four points to define the bounding box. Sequence of either [(x0, y0), (x1, y1)] or [x0, y0, x1, y1]. The second point is just outside the drawn rectangle.

So rectangle() explicitly says the "second point is just outside the drawn rectangle". Polygon is defined as a sequence of lines, and line is "between the coordinates in the xy list", but doesn't explicitly define edge pixels.

Therefore, following this, draw.rectangle((2, 2, 7, 7), BLACK) would create a 5x5px square from from 2,2 to 6,6 (filling 2,2 and 6,6 and everything in between but not 7,7), but square.png shows a 6x6px from 2,2 to 7,7.

00123456789
0----------           
1----------
2--xxxxx---
3--xxxxx---
4--xxxxx---
5--xxxxx---
6--xxxxx---
7----------
8----------
9----------

Similarly, draw.rectangle((7, 7, 2, 2), BLACK) would create a 5x5px square from 7,7 to 3,3 (filling 3,3 and 7,7 and everything in between but not 2,2). This is different to square.png and the previous square!

00123456789
0----------           
1----------
2----------
3---xxxxx--
4---xxxxx--
5---xxxxx--
6---xxxxx--
7---xxxxx--
8----------
9----------

polygon()'s documentation is ambiguous and it may be it draws a different square too. It may be useful to check some other drawing libraries' APIs.

[Terseus]

@hugovk I found that most of the PIL docs are outdated as it doesn't always match the code, the draw.rectangle method is a good example; rectangles are drawn with their own dedicated C function, ImagingDrawRectangle, this function uses two different functions, hline and line, depending on if the rectangle should be filled or not, and those functions draw always both end points of the line, as we talked before.
That's one of the reasons why I chose to follow the "draw all endpoints" approach: for consistency with the rest of the library.

Looking into another library sounds like a good idea but I'm not familiar with another draw API and, honestly, for me dig into this one has been enough for now :)

[aclark4life]

😕

[aclark4life]

Targeting Future

[benjimin]

The PIL documentation explicitly asserts that the coordinate origin is at the top left corner (not the centre) of the top left pixel. (E.g. see http://pillow.readthedocs.org/en/3.0.x/handbook/concepts.html#coordinate-system) Thus a square 10 pixel by 10 pixel image canvas spans from (0,0) to (10,10) in coordinate space; (10,10) is the coordinate for the bottom-right corner of the last pixel.

Therefore, in Terseus example, the polygon [(2,2), (2,8), (8,8), (8,2)] should be a square with sides of length 6 pixels. Not seven, because that would encroach (overlap) on the polygon [(8,8), (8,10), (10,10), (10,8)], which clearly does not overlap in coordinate space (and is already perfectly aligned with the edges of the pixels). Trying to "include endpoints" can't make consistent sense (since in geometry, it is arbitrary which side you call the start versus the end).

[Lonami]

I've ran this code under Pillow 5.4.1 and got the following results. Note that I added the colours afterwards and zoomed in to make it easy to count the pixels:

Here's the original:

It seems like the vertical line is only two pixels wide.

[radarhere]

#367 (comment)

So rectangle() explicitly says the "second point is just outside the drawn rectangle".

This was changed with #6625 to say that "The bounding box is inclusive of both endpoints."

[radarhere]

@Lonami looks like the original problem here was resolved by #737

The rest of this is a debate about whether shapes should include their endpoints or not.