在两点之间对角地迭代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箱子覆盖所有场景Ç,ē,摹,和我. 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(...)-method简单地计算出的9例,我们有哪一个与任一处理的情况下甲直接或呼叫processHorizontally(...)或processVertically(...)如上所述.然后,这些方法首先贯穿各自的平行四边形,然后填充平行四边形周围的三角形.

有几点需要注意:

1. 基本上,processHorizontally(...)并且processVertically(...)完全相同,除了交换x和y.
2. 循环非常紧,不包含任何繁重的数学,所以这段代码应该相当高效,但仍然有改进的余地(例如内联processor.process(...),以更优化的方式分别处理案例B和F,......) .
3. 此代码不检查数组边界!例如,process(...)可能会使用负坐标调用!
4. 有人可能会说:案例G和案例E看起来非常像同一个案例.难道你不能只计算矩形的另外两个角来将情况G映射到案例E和H映射到D和I映射到C而不是将它们视为单独的情况吗？而且,在理想数学领域,这是一个非常有效的陈述,除非它在其他角落的坐标不是整数的情况下不起作用.例如,OP的第一个例子就是这种情况.在那里,左右两侧有一个"切碎的"角(一列中只有两个1).如果你要计算并围绕矩形的左右角而不是顶角和底角,你将最终得到顶部和底部的"切碎"角.

希望这可以帮助.如果您需要更详细的代码说明,请与我们联系.