PHP - Bug in polygon GD library?

Question

I have run into some trouble with the gd library's imagefilledpolygon().

For some reason some of my lines were ending up 1px out of place so I decided to debug it using imagepixelset to set the colour of my shapes points to red.

alt text http://www.degreeshowcase.com/other/1.gif if you look at the picture you can see some of the points are inside the shape ... some are outside....its very illogical.

(the picture has been scaled up to make it more visible)

Does anyone have a solution?

Update:

My points for the shape above were: 0,0 40,0 40,20 20,20 20,40 0,40

I require that the height and width of the shape produced should be a multiple of 20.... but for some reason some of the shape ends up 21 px high or wide.

I have made a script to work out what the points would be to get the shape I wanted but I can not work out why and so I can't work out a script to correct all my shapes.

<?php

// set up array of points for polygon
$values = array(0,0, 39,0, 39,20, 19,20, 19,39, 0,39);

//My original values were 0,0 40,0 40,20 20,20 20,40 0,40
//I do not understand why some values require minus 1 and others can remain as they were (a multiple of 20)

// create image
$image = imagecreatetruecolor(40, 40);

// allocate colors
$bg   = imagecolorallocate($image, 200, 200, 200);
$blue = imagecolorallocate($image, 0, 0, 255);

// fill the background
imagefilledrectangle($image, 0, 0, 39, 39, $bg);

// draw a polygon
imagefilledpolygon($image, $values, 6, $blue);

// flush image
header('Content-type: image/png');
imagepng($image);
imagedestroy($image);


?>

Answer 1

I spoke to the guy who currently develops the GD library he explained that it follows the 'Winding number algorithm' - can be found here. Having looked at my example image, it does match how the 'winding number algorithm' works, however the function should take this into account and produce the shape that was input.

As far as I can see the only way to accurately (to the pixel) generate a concave polygon with this function is to write another function that also applies the winding rule to your coordinates and adjusts them accordingly and then put it into the function.

Answer 2

My guess is that you're mixing up width with position.

For example a line from 0px to 9px is 10px long... if you used length as the second parameter instead of position, it would end up 11px long.

If I could see some code I could confirm this.

Answer 3

Normal polygon rendering ensures that each pixel can only be in one polygon, if the 2 polygons share an edge. If you imagine drawing 2 squares, next to each other, so they share a common edge, you don't want to render the pixels along that edge twice.

There is an explanation of determining which pixels on the edge of a polygon should be considered inside the polygon here: http://www.gameprogrammer.com/5-poly.html

A common solution is to say that "pixels on the left and top edges of a polygon belong to the polygon and pixels on the right and bottom edges don't". I am not 100% sure what solution GD uses, as I could not find any documentation on it, but I expect it is something similar to this.