I need an Algorithm that I will use to scan pixels out from the center. Problem is with different lengths and sizes, it sometimes can't get to the position (See Image below blue part).

To illustrate the problem more I will show the example output:

If you compare the pictures you will notice that it goes in a spiral and the outputs match with a regular for loop and obviously the problem that it doesn't print the blue part correctly

Here is the code:

#include<iostream>
#include<string>
#include<math.h>

int arr[] = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 };
int arrSize = sizeof(arr) / sizeof(arr[0]);
int width = 5;
int height = 3;

void normal2DArray() {
    int index = 0;
    for (int y = 0; y < height; y  ) {
        for (int x = 0; x < width; x  ) {
            std::cout << std::to_string(x) << "," << std::to_string(y) << " = " << std::to_string(arr[index]) << "\n";
            index  ;
        }
    }
}

int convertToInex(int x, int y) {
    int left = x * y; // elements to the left
    int right = (width - x) * y; // elements to the right
    return left   right   x;
}

void spiralArray() {
    // calculate middle point, which is also the start point
    int x = round((float)width / 2) - 1;
    int y = round((float)height / 2) - 1;

    int direction = 0; // 0=right, 1=up, 2=left, 3=down
    int turnCounter = 1;
    int numSteps = 1;
    int step = 1;
    int index;

    while (true) {

        index = convertToInex(x, y); // defines the index position in arr
        std::cout << std::to_string(x) << "," << std::to_string(y) << " = " << std::to_string(arr[index]) << "\n";

        switch (direction) {
        case 0: x  ; break;
        case 1: y--; break;
        case 2: x--; break;
        case 3: y  ; break;
        }
        index = convertToInex(x, y);

        if (step % numSteps == 0) {
            direction = (direction   1) % 4;
            turnCounter  ;
            if (turnCounter % 2 == 0) numSteps  ;
        }
        step  ;
        if (step > arrSize) break;
    }
}

void main() {
    std::cout << "Output of Normal 2D Array:\n";
    normal2DArray();

    std::cout << "\n"; // better spacing

    std::cout << "Output of Spiral Array:\n";
    spiralArray();
}

I tried to keep the code as simple and small as possible. It should be ready to import and use. And yes I already searched for my answer online but I didn't find anything that covered up the problem here nor had a similar setup like I have(1D arr and combined 2D array WIDTH/HEIGHT) and for sure not in c .

❗ Also I need a Solution that works with all widths and heights and arr sizes and also works for any side ❗

I hope you can provide me with helpful answers and would be grateful with good and fast algorithm implementations/optimizations

And sorry for not having enough reputation to post images.

CodePudding user response：

You can hit a dead end (meaning exit the grid) in four spots. In each case, jump to the next live pixel you would have reached, if any live cells remain.

You can do this fairly easily by keeping track of the four corners you've visited furthest from the starting pixel. Using compass coords and N for up, these are the NE, NW, SW, and SE extremes visited.

If you hit a dead end going N from the NE pixel, jump to the pixel one to the left of the NW pixel and set the movement direction to down. If that is also a dead end, jump to one below the SW pixel and set the movement direction to right. Etc... When all four corners and dead ends then you're done.

CodePudding user response：

You have multiple options to resolve this issue.

1. Divide your array into squares of whatever size you want and process those squares sequentially or if you are open to it, run them in parallel.
2. Have three cases : X > Y ; Y > X ; X == Y | Each case will run through a different spiral
3. Spiral as you do, calculate the leftover area and start a new spiral, divide and conquer until all points have been analyzed or you are done.

Option 1 would have the benefit of being easily parallelizable if you choose to go down that path. Option 2 allows you to simplify the solution, but will not be super-efficient. Option 3 can be implemented recursively as you can pass the remainder to the same algorithm and repeat until you are left with 0 or 1 pixels.

Let me know if you have any other questions! Option