java - 在两个点之间对角地遍历2D数组

Question

我有一个二维数组，我想在其中对角迭代。我想限制两点之间的范围，创建一个45 *偏移的矩形区域。

一些例子：

| - - - - - - - -     | - - - - - - - -     | - - - - - - - - 
| - - - * - - - -     | - - - * - - - -     | - - - - - * - - 
| - - 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 -     | - - - * - - - -     | - * - - - - - - 
| - - - - - * - -     | - - - - - - - -     | - - - - - - - - 
| - - - - - - - -     | - - - - - - - -     | - - - - - - - - 

* =输入点

1 =指向迭代

我的问题是：我将如何以一种干净有效的方式来做（或处理）这样的事情？顺序无所谓。

Answer 1

这是一个有趣的问题！这是我要解决的方法：

让我们确定9种不同的可能情况：



（我将圆圈放在那里作为引导眼睛的方式。我将两个点可视化为彼此“环绕”。）


A是两个坐标都相同的平凡情况
B和F是基本上只需要画一条对角线的情况
C，D和E是点之间的y距离大于x距离的情况
G，H和I是点之间的x距离大于y距离的情况


从技术上讲，案例B到案例I分别对应两种情况，具体取决于是先给出顶部/左侧坐标还是底部/右侧坐标，但让我们为这些点定义所需的顺序，并在需要时进行切换。

可以将需要处理的区域分解为一个平行四边形（绿色）和两个三角形：



在C，D和E的情况下，可以“垂直”处理平行四边形（即，对于每个x位置，沿垂直方向运行一定数量的点），在G，H和I情况下，可以被“水平”处理。

垂直平行四边形中每一列的高度和水平平行四边形中每一行的宽度仅是两个点的y差与两个点的x差之间的绝对差。

我们仅处理4种情况即可涵盖所有情况：C，E，G和I。B和D可以看作是C的一种特殊情况，其中平行四边形的高度或宽度分别为0。同样，F只是E的特例，H可以与I一起处理。A也可以与C一起抛出，但是由于它很容易识别，因此我们将其分开处理以提高性能。

为了使程序通用，让我为Processor定义一个接口，该接口与您的数组进行交互，并会为需要处理的所有坐标被调用：

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

代码有点长，但是并不是特别困难，所以让我发布一下：

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);
            }
        }
    }
}

process(...)方法只是简单地指出我们有9种情况中的哪一种，并且可以直接处理案例A，或者如上所述调用 processHorizontally(...)或 processVertically(...)。然后，这些方法首先运行各个平行四边形，然后填充平行四边形周围的三角形。

需要注意的几件事：


基本上， processHorizontally(...)和 processVertically(...)完全相同，只是交换了x和y。
循环非常紧密，并且不包含任何繁琐的数学运算，因此此代码应该相当有效，但是肯定还有改进的空间（例如，内联 processor.process(...)，以更优化的方式分别处理案例B和F）。 ..）。
此代码不检查数组边界！例如， process(...)可能用负坐标调用！
可能会说：情况G和情况E看起来很像同一情况。您不能只计算矩形的其他两个角以将案例G映射到案例E，将H映射到D并将我映射到C，而不是将它们视为单独的案例吗？而且，在理想情况下，这是一个非常有效的声明，除了在其他角的坐标不为整数的情况下不起作用。例如，在OP的第一个示例中就是这种情况。在那里，您在左侧和右侧都有一个“切碎”的角（一列中只有两个1）。如果要计算并舍入矩形的左，右角而不是顶部和底部的角，则最终将在顶部和底部具有“切碎的”角。


希望这可以帮助。如果您需要更详细的代码说明，请告诉我。