index was outside the bounds of the array double C# (double)

Question

I've been trying to implement Bresenham's line algorithm from the Wikipedia Page and I've encountered a strange issue that leads to an exception.

public static int[,] Line(int x0, int y0, int x1, int y1)
    {
        int arraySizeX = x1 - x0;
        int arraySizeY = y1 - y0;
        int [,] outputArray = new int[arraySizeX, arraySizeY];
        //Bresenham's line algorithm from Wikipedia
        double deltax = x1 - x0;
        double deltay = y1 - y0;

        double deltaerr = Math.Abs(deltay / deltax); // Assume deltax != 0 (line is not vertical),
        double error;
        error = 0.0;//no error at start
        int y = 0;

        for( int x = x0; x1 >= x; x++)
        {
            outputArray[x, y] = 1;
            error += deltaerr;
            while(error >= 0.5)
            {
                y = y + Math.Sign(deltay) * 1;
                error = error - 1.0;
            }
        }

        return outputArray;
    }

And when I test it with:

Line(2, 1, 5, 3);

it return the exception:

System.IndexOutOfRangeException: 'Index was outside the bounds of the array.'

At this line:

                error += deltaerr;

This happens on the second iteration of the for loop. At that point the two values are:

  error   -0.33333333333333337    double

and

  deltaerr    0.66666666666666663 double

In my mind error should be assigned something like 0.3333. Any pointers as to what may have gone wrong?

This is my first question, so please tell me how I could improve in future. Thanks.

Solution: Pay close attention to all arrays in the code.

The error was actually on the line above where the code tried to reference an array position that didn't exist.

Given input: `Line(2, 1, 5, 3);` the multidimensional array is essentially defined as `int [,] outputArray = new int[3, 2];` you can think of this as a table of 3 rows and 2 columns. however, the issue is that the for loop iteration variable `x` goes beyond the number of rows available. you can easily sort this out by using a debugger and making sure your algorithm is correct. — Ousmane D., Nov 04 '17 at 18:36
The error `IndexOutOfRangeException` cannot happen at this line `error += deltaerr;`, because this line does not involve any indexing. It must this one `outputArray[x, y] = 1;`, where the array is indexed with`[x, y]`. I explain it in detail in my answer. — Olivier Jacot-Descombes, Nov 05 '17 at 20:21

Martin Backasch · Answer 1 · 2017-11-04T19:35:54.007

The exception occurs on the line above, when you try to access the array.

outputArray[x, y] = 1;

When you call your method Line(2, 1, 5, 3); you will create an array of the size new int[3,2]

int arraySizeX = x1 - x0;  //  5 - 2 = 3
int arraySizeY = y1 - y0;  //  3 - 1 = 2
int [,] outputArray = new int[arraySizeX, arraySizeY]; // new int[3,2]

So now your for loop will run from x0 = 2 to x1=5 so you are running out of the array range. This is what your exception is about.

To fix this you should start your for loop by x = 0 and end by x <= x1-x0-1 or start by x = 0 and end by x < x1-x0.

Olivier Jacot-Descombes · Answer 2 · 2017-11-04T19:13:43.820

If you create an array with

new int[arraySizeX, arraySizeY]

then the index ranges are

[0 .. arraySizeX - 1, 0 .. arraySizeY - 1]

You must never exceed these limits. Subtract x0 or y0 from the coordinates to get indexes that are within these limits

for (int x = x0; x1 >= x; x++)
{
    outputArray[x - x0, y - y0] = 1;
    ...
}

Another problem is that you are looping until x == x1. Therefore the array size should be int arraySizeX = x1 - x0 + 1. Same for arraySizeY (because if y0 == y1, i.e. the line is horizontal, the array size must be 1, not 0).

(Also assuming that x1 > x0 and y1 >= y0, otherwise you might get negative array sizes)

But a more realistic approach would "draw" the pixels into an array that reflects the image size instead of just the line size and the end-points of the line would have to be within the image. An extra logic would clip lines crossing the image boundaries. See: Cohen–Sutherland algorithm for Line clipping.

int[,] image = new int[imageWidth, imageHeight];

With x0 and x1 in the range [0 .. imageWidth-1] and y0 and y1 in the range [0 .. imageHeight-1].

index was outside the bounds of the array double C# (double)

2 Answers2