CODEWITHSUNDEEP
c#algorithmspiral
omega
omega

Reputation: 43843

Inward spiral algorithm not working

I have this c# code to iterate through a grid in an inward spiral like this:

1 2 3
8 9 4
7 6 5

Here is the code, but there is something wrong with it, for some reason it is taking much longer than expected to compute. Does anyone know why this is happening?

    static void create_spiral_img(int width, int height)
    {
        Bitmap img = new Bitmap(width, height);
        Graphics graph = Graphics.FromImage(img);

        int x = 0;
        int y = 0;
        int size = width * height;
        int max = size;
        int count = 1;
        int i, j;
        while (size > 0)
        {
            for (i = y; i <= y + size - 1; i++)
            {
                draw_pixel(count++, x, i, graph);
            }

            for (j = x + 1; j <= x + size - 1; j++)
            {
                draw_pixel(count++, j, y + size - 1, graph);
            }

            for (i = y + size - 2; i >= y; i--)
            {
                draw_pixel(count++, x + size - 1, i, graph);
            }

            for (i = x + size - 2; i >= x + 1; i--)
            {
                draw_pixel(count++, i, y, graph);
            }

            x = x + 1;
            y = y + 1;
            size = size - 2;
            Console.Write(100 * ((float)(count) / (float)max) + "% ");
        }

        graph.Dispose();
        img.Save("./" + width + "x" + height + "_spiril.png", System.Drawing.Imaging.ImageFormat.Png);
        img.Dispose();
    }

Upvotes: 2

Views: 562

Answers (2)

bruce_ricard
bruce_ricard

Reputation: 771

Assuming that

draw_pixel(c,x,y,g)

draws a point in color c at (x,y) coordinates in the graph g, you're going way too far. You're doing

for (i = y; i <= y + size - 1; i++)

to print a line that should have length width, but you're printing a line of length size.

I'm thinking I didn't understand your algorithm. If this doesn't make sense, can you explain the semantics of draw_pixel please ?

Upvotes: 0

Mark Shapiro
Mark Shapiro

Reputation: 1232

Assuming a square (width=height) it looks like you've got an O(x^4) implementation - that's going to be hideously slow.

I would recommend trying to drop it down to O(x^2). Instead of drawing it spirally, rewrite your algorithm to draw it rectangularly - that is, go by rows & columns, calculating what each pixel should be.

Upvotes: 2

Related Questions