Iterating Through a 2D Array Diagonally Between Two Points

Question

I have a two dimensional array in which I would like to iterate diagonally. I want to limit the range between two points, creating a 45* offset rectangular area.

Some examples:

| - - - - - - - -     | - - - - - - - -     | - - - - - - - - 
| - - - * - - - -     | - - - * - - - -     | - - - - - * - - 
| - - 1 1 1 - - -     | - - 1 1 1 - - -     | - - - - 1 - - - 
| - - 1 1 1 1 - -     | - 1 1 1 1 1 - -     | - - - 1 - - - - 
| - - - 1 1 1 1 -     | - - 1 1 1 - - -     | - - 1 - - - - - 
| - - - - 1 1 1 -     | - - - * - - - -     | - * - - - - - - 
| - - - - - * - -     | - - - - - - - -     | - - - - - - - - 
| - - - - - - - -     | - - - - - - - -     | - - - - - - - - 

* = input point

1 = point to iterate through

My question is: how would I do (or approach) something like this in a clean and efficient way? Order does not matter.

Answer 1

This is a fun problem! Here's how I would solve it:

Let's identify 9 different possible scenarios:

(I put the circles there as a guide for the eye. I was visualizing the two points as "orbiting" each other.)

• A is the trivial case where both coordinates are the same
• B and F are the cases where you basically only have to draw a diagonal line
• C, D, and E are cases where the y-distance between the dots is larger than the x-distance
• G, H, and I are cases where the x-distance between the dots is larger than the y-distance

Technically, cases B through I each correspond to two cases, depending on whether the top/left coordinate is given first or the bottom/right one, but let's just define a desired order for the points and switch them if needed.

The area that needs to be processed can be broken up into a parallelogram (green) and two triangles:

In the cases C, D, and E, the parallelogram can be processed "vertically" (i.e. for every x-position, you run through a certain number of points along the vertical) and in the cases G, H, and I it can be processed "horizontally".

The height of each column in the vertical parallelogram and the width of each row of the horizontal parallelogram are just the absolute difference between the y-difference of the two points and the x-difference of the two points.

We can cover all scenarios by only handling 4 cases: C, E, G, and I. B, and D can be thought of as a special case of C where the parallelogram has a height or width of 0 respectively. Likewise, F is just a special case of E, and H can be handled along with I. A could also be thrown in with C, but since it's easy enough to identify, let's treat it separately for increased performance.

To make the program generic, let me define an interface for a Processor that interacts with your array and will get called for all coordinates that need to be processed:

public interface Processor {
    public void process(int x, int y);
}

The code is a bit long, but it's not particularly difficult, so let me just post it:

public void process(Processor processor, int x1, int y1, int x2, int y2) {
    int dy = Math.abs(y2 - y1);
    int dx = Math.abs(x2 - x1);
    if (dx<=dy) {
        if (dy==0) {
            // Case A
            processor.process(x1, y1);
            return;
        }
        // Cases B, C, D, E, and F
        if (y2>y1) processVertically  (processor, x1, y1, x2, y2, dy - dx);
              else processVertically  (processor, x2, y2, x1, y1, dy - dx);
    } else {
        // Cases G, H, and I
        if (x2>x1) processHorizontally(processor, x1, y1, x2, y2, dx - dy);
              else processHorizontally(processor, x2, y2, x1, y1, dx - dy);
    }
}

private void processVertically(Processor processor, int x1, int y1, int x2, int y2, int h) {
    if (x2<x1) {
        // Cases E and F
        // Fill in parallelogram 
        int y = y2;
        for (int x=x2; x<=x1; x++) {
            for (int dy=0; dy<=h; dy++)
                processor.process(x, y-dy);
            y--;
        }
        // Fill in triangles
        for (h-=2; h>=0; h-=2) {
            x1++; y1++;
            x2--; y2--;
            for (int dy=0; dy<=h; dy++) {
                processor.process(x1, y1+dy);
                processor.process(x2, y2-dy);
            }
        }
    } else {
        // Cases B, C and D
        // Fill in parallelogram 
        int y = y1;
        for (int x=x1; x<=x2; x++) {
            for (int dy=0; dy<=h; dy++)
                processor.process(x, y+dy);
            y++;
        }
        // Fill in triangles
        for (h-=2; h>=0; h-=2) {
            x1--; y1++;
            x2++; y2--;
            for (int dy=0; dy<=h; dy++) {
                processor.process(x1, y1+dy);
                processor.process(x2, y2-dy);
            }
        }
    }
}

private void processHorizontally(Processor processor, int x1, int y1, int x2, int y2, int w) {
    if (y2<y1) {
        // Case G
        // Fill in parallelogram 
        int x = x2;
        for (int y=y2; y<=y1; y++) {
            for (int dx=0; dx<=w; dx++)
                processor.process(x-dx, y);
            x--;
        }
        // Fill in triangles
        for (w-=2; w>=0; w-=2) {
            x1++; y1++;
            x2--; y2--;
            for (int dx=0; dx<=w; dx++) {
                processor.process(x1+dx, y1);
                processor.process(x2-dx, y2);
            }
        }
    } else {
        // Cases H and I
        // Fill in parallelogram 
        int x = x1;
        for (int y=y1; y<=y2; y++) {
            for (int dx=0; dx<=w; dx++)
                processor.process(x+dx, y);
            x++;
        }
        // Fill in triangles
        for (w-=2; w>=0; w-=2) {
            x1++; y1--;
            x2--; y2++;
            for (int dx=0; dx<=w; dx++) {
                processor.process(x1+dx, y1);
                processor.process(x2-dx, y2);
            }
        }
    }
}

The process(...)-method simply figures out which one of the 9 cases we have and either handles case A directly or calls processHorizontally(...) or processVertically(...) as described above. Those methods then run through the respective parallelograms first and fill in the triangles around the parallelogram after.

A couple of things to note:

1. Basically, processHorizontally(...) and processVertically(...) are exactly the same, except x and y are exchanged.
2. The loops are pretty tight and don't include any heavy math, so this code should be fairly efficient, but there is definitely still room for improvement (e.g. inlining processor.process(...), handling cases B and F separately in a more optimized way, ...).
3. This code does not check for array boundaries! For example, process(...) might be called with negative coordinates!
4. One might say: Case G and case E look pretty much like the same case. Can't you just calculate the other two corners of the rectangle to map case G onto case E and H onto D and I onto C instead rather than treating them as separate cases? And, in ideal-math-land, this is a perfectly valid statement, except it doesn't work in cases where the coordinates of the other corners don't come out to be integers. For instance, this is the case in the OP's first example. There, you have a "chopped" corner (only two 1's in a column) on the left and right. If you were to calculate and round the left and right corners of the rectangle rather than the top and bottom corners, you will end up with the "chopped" corners at the top and bottom.

Hope this helps. Let me know if you need a more detailed explanation of the code.