旋转比特矩阵

Question

旋转比特矩阵

6

假设我使用一个大小为8的char数组来表示图像的碰撞掩码。每个char位代表一个像素。实际上，我将使用一个long[64]数组来表示一个64x64矩阵。

因此，一个框将显示为：

一个 45 度的示例输出应该是这样的，尽管旋转角度可以是任意角度。由于我是手动操作的，因此此形状可能不准确。

以下是带有小幅度向右旋转的另一个输出示例--10度？由于我无法确切地知道它将如何旋转，因此这些值可能不正确，但我认为可以安全地假设，如果每个位覆盖了旧形状的50％以上，则为1。

没有旋转，使用位移操作可以快速找到这些位掩码之间的碰撞，具体实现请参考stackoverflow回答: https://dev59.com/SXRC5IYBdhLWcg3wUvUS#336615 过去我曾经使用Path2D、Rectangles、Shapes等类并使用AffineTransform来旋转对象。Path2D是唯一提供所需复杂形状的类，但其“链表式”访问每个点的行为不如我所希望的那么快。

在Java中，最佳方法是什么以便旋转二进制地图？

另外，看起来Java库用于矩阵运算也不是最快的。

- Anthony Korzan

1

你能否更新问题并说明你想要实现的输出结果吗？我不确定你的意图。 - Andy Guibert

@aguibert 我添加了一些例子。45度的旋转可以手动转换，但对于较小的旋转来说就不那么容易了，但我尝试通过手动模拟来实现它。希望这将使我能够使用长整型而不是字符表示位来创建更复杂的形状。我将从PNG的alpha通道中创建这些形状。例如，飞机精灵并不准确地由矩形界定，因此使用Rectangle2D对象进行碰撞检测并不理想。Path2D允许我创建更准确的碰撞框 - 但对于复杂的形状来说速度非常慢。 - Anthony Korzan

2个回答

1

我同意一般情况下映射输出的条目会更好，但这已足够检测碰撞。如果您没有非常小的物体可以跳入其他物体，您可以将内部点设置为0，使其更加稀疏：

...

// simple algorithm to remove inner 1s with a sliding window,
// here shown with 3x3 but I think it has to be 5x5 (you can omit the corners)
int[][] inputSparse = new int[input.length][input[0].length];
// assuming the border is 0 anyway
// not the best way to implement it, but it shows the idea and it only has to be done once
for (int i = 1; i < inputSparse.length - 1; i++) {
  for (int j = 1; j < inputSparse[0].length - 1; j++) {
    if (input[i-1][j-1] != 1 || input[i-1][j] != 1 || input[i-1][j+1] !=1 ||
        input[i][j-1] != 1 || input[i][j] != 1 || input[i][j+1] != 1 ||
        input[i+1][j-1] != 1 || input[i+1][j] != 1 || input[i+1][j+1] !=1) {
      inputSparse[i][j] = input[i][j];
    } else {
      inputSparse[i][j] = 0; // just to show that a one is removed, you don't need the else
    }
  }
}
...
output = rotate(inputSparse, 10); // example
...
private int[][] rotate(int[][] input, double degrees) {
  double rad = Math.toRadians(degrees);
  double sin = Math.sin(rad);
  double cos = Math.cos(rad);
  int[][] output = new int[input.length][input[0].length];
  for (int i = 0;  i < input.length; i++) {
    double oldY = i - (input.length - 1) / 2.0;
    for (int j = 0; j < input[0].length; j++) {
      if (input[i][j] == 1) { // <-- this is the big gain !!!
        double oldX = j - (input[0].length - 1) / 2.0;
        int x = (int)(cos * oldX + sin * oldY + input[0].length / 2.0);
        int y = (int)(-sin * oldX + cos * oldY + input.length / 2.0);
        output[y][x] = 1;
      }
    }
  }
  return output;
}

旧回答： 我不知道这是否足够好，但您可以仅转换那些数字1，希望这有意义，我不知道您是否会得到“空洞”（即在数字1之间的0），而且只有当您周围有足够的0时才有效，否则索引将超出范围，无论如何，这是我的建议：

int[][] input = {{0, 0, 0, 0, 0, 0, 0, 0},
                 {0, 0, 0, 0, 0, 0, 0, 0},
                 {0, 0, 1, 1, 1, 1, 0, 0},
                 {0, 0, 1, 1, 1, 1, 0, 0},
                 {0, 0, 1, 1, 1, 1, 0, 0},
                 {0, 0, 1, 1, 1, 1, 0, 0},
                 {0, 0, 0, 0, 0, 0, 0, 0},
                 {0, 0, 0, 0, 0, 0, 0, 0}};

double rad = Math.toRadians(10); // 10 * Math.PI / 180;
double sin = Math.sin(rad);
double cos = Math.cos(rad);

int[][] output = new int[8][8];
// or: int[][] output = new int[input.lengh][input[0].lengh];

for (int i = 0;  i < 8; i++) {
  double oldX = i - 3.5; // move to center
  for (int j = 0; j < 8; j++) {
   if (input[i][j] == 1) {
     double oldY = j - 3.5; // move to center
     int x = (int)(cos * oldX + sin * oldY + 4); // + 3.5 to shift back, +0.5 to simulate rounding
     int y = (int)(-sin * oldX + cos * oldY + 4);
     output[x][y] = 1;
   }
  }
}

- maraca

当rad = Math.toRadians（45）时，存在一个洞。 00000000 00001000 00011000 00101100 01111110 00011000 00001000 00000000这个洞似乎也是由于在中心点生成的洞造成的，该洞与四舍五入的结果相反。但对于如此小的样本大小，很难确定是否这是唯一的边缘情况。我正在阅读有关旋转矩阵的信息，因为它似乎是解决这个问题的方法。 - Anthony Korzan

当我将数组扩大到12x12，并删除四舍五入以更好地对齐调试孔时，由于所有孔都会因四舍五入而移动1个单位，因此会有更多的孔。

000001000000 000011100000 000110110000 001011101000 011111111100 110110110110 011111111100 001011101000 000110110000 000011100000 000001000000 000000000000

- Anthony Korzan

@AnthonyKorzan 对，但是这些孔对于碰撞检测真的很重要吗？我认为即使有碰撞，你也不会像两个拼图一样神奇地拼合在一起。 - maraca

@AnthonyKorzan 更新了我的答案，向您展示了我为什么这样做以及如何进行更多优化。 - maraca

不客气，很高兴能帮到你。如果您有“平面”对象，即在一个维度上很大而在另一个维度上不大，则简单的x和y（即i和j）的最小/最大值可能是一个很大的改进。因此，不要使输入稀疏计算最小值和最大值，然后您就可以使用rotate(int[][] input, double degrees, int minX, int maxX, int minY, int maxY)，并在内部使用for (int i = minY; i <= maxY; i++)。 - maraca

显示剩余2条评论

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Patricia Shanahan · Accepted Answer

这个解决方案基于之前的答案。它不是将输入点映射到输出点，而是将输出点映射到输入矩阵空间中的位置。

在这个版本中，它只是使用最接近整数索引点的值。如果使用邻居点的距离加权值总和的更复杂的值计算，可能会获得更好的结果。

以下是一些结果：

Angle: 10.0 degrees
00000000 00000000
00000000 00000000
00111100 00011000
00111100 00011110
00111100 00111110
00111100 00111100
00000000 00001100
00000000 00000000

Angle: 45.0 degrees
00000000000000000000 00000000000000000000
00000000000000000000 00000000000000000000
00000000000000000000 00000000000000000000
00000000000000000000 00000000001000000000
00000000000000000000 00000000011100000000
00000111111111100000 00000000111110000000
00000111111111100000 00000001111111000000
00000111111111100000 00000011111111100000
00000111111111100000 00000111111111110000
00000111111111100000 00001111111111111000
00000111111111100000 00011111111111111100
00000111111111100000 00001111111111111000
00000111111111100000 00000111111111110000
00000111111111100000 00000011111111100000
00000111111111100000 00000001111111000000
00000000000000000000 00000000111110000000
00000000000000000000 00000000011100000000
00000000000000000000 00000000001000000000
00000000000000000000 00000000000000000000
00000000000000000000 00000000000000000000

Angle: 10.0 degrees
00000000000000000000 00000000000000000000
00000000000000000000 00000000000000000000
00000000000000000000 00000000000000000000
00000000000000000000 00000000000000000000
00000000000000000000 00000000000000000000
00000111111111100000 00000011111000000000
00000111111111100000 00000011111111110000
00000111111111100000 00000011111111110000
00000111111111100000 00000011111111110000
00000111111111100000 00000011111111110000
00000111111111100000 00000111111111110000
00000111111111100000 00000111111111100000
00000111111111100000 00000111111111100000
00000111111111100000 00000111111111100000
00000111111111100000 00000111111111100000
00000000000000000000 00000000001111100000
00000000000000000000 00000000000000000000
00000000000000000000 00000000000000000000
00000000000000000000 00000000000000000000
00000000000000000000 00000000000000000000

Angle: 90.0 degrees
00000000000000000000 00000000000000000000
00000000000000000000 00000000000000000000
00000000000000000000 00000000000000000000
00000000000000000000 00000000000000000000
00000000000000000000 00000000000000000000
00000111111111100000 00000011111111110000
00000111111111100000 00000011111111110000
00000111111111100000 00000011111111110000
00000111111111100000 00000011111111110000
00000111111111100000 00000011111111110000
00000111111111100000 00000011111111110000
00000111111111100000 00000011111111110000
00000111111111100000 00000011111111110000
00000111111111100000 00000011111111110000
00000111111111100000 00000011111111110000
00000000000000000000 00000000000000000000
00000000000000000000 00000000000000000000
00000000000000000000 00000000000000000000
00000000000000000000 00000000000000000000
00000000000000000000 00000000000000000000

测试程序：

public class Test {
  public static void main(String args[]) {
    int[][] input1 = { { 0, 0, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0 },
        { 0, 0, 1, 1, 1, 1, 0, 0 }, { 0, 0, 1, 1, 1, 1, 0, 0 },
        { 0, 0, 1, 1, 1, 1, 0, 0 }, { 0, 0, 1, 1, 1, 1, 0, 0 },
        { 0, 0, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0 } };

    testit(input1, 10);

    int[][] input2 = new int[20][20];
    for(int i=5; i<15; i++){
      for(int j = 5; j<15; j++){
        input2[i][j] = 1;
      }
    }

    testit(input2, 45);
    testit(input2, 10);
    testit(input2, 90);
  }

  private static void testit(int[][] input, double degrees) {
    int[][] output = rotate(input, degrees);
    System.out.println("Angle: "+degrees+" degrees");
    for (int i = 0; i < input.length; i++) {
      for (int j = 0; j < input[i].length; j++) {
        System.out.print(input[i][j]);
      }
      System.out.print(" ");
      for (int j = 0; j < output[i].length; j++) {
        System.out.print(output[i][j]);
      }
      System.out.println();
    }
    System.out.println();
  }

  private static int[][] rotate(int[][] input, double degrees) {

    double rad = Math.toRadians(degrees);
    double sin = Math.sin(-rad);
    double cos = Math.cos(-rad);

    int[][] output = new int[input.length][input[0].length];

    for (int i = 0; i < output.length; i++) {
      double oldX = i - output.length / 2.0; // move to center
      for (int j = 0; j < input[i].length; j++) {
        {
          double oldY = j - output[i].length / 2.0; // move to center
          double x = (int) (cos * oldX + sin * oldY + input.length / 2.0);
          double y = (int) (-sin * oldX + cos * oldY + input[i].length / 2.0);
          output[i][j] = getNearestVal(input, x, y);
        }
      }
    }
    return output;
  }

  private static int getNearestVal(int[][] input, double x, double y) {
    int xLow = (int) Math.floor(x);
    int xHigh = (int) Math.ceil(x);
    int yLow = (int) Math.floor(y);
    int yHigh = (int) Math.ceil(y);
    int[][] points = { { xLow, yLow }, { xLow, yHigh }, { xHigh, yLow },
        { xHigh, yHigh } };
    double minDistance = Double.POSITIVE_INFINITY;
    int minDistanceValue = 0;
    for (int[] point : points) {
      double distance = (point[0] - x) * (point[0] - x) + (point[1] - y)
          * (point[1] - y);
      if (distance < minDistance) {
        minDistance = distance;
        if (point[0] >= 0 && point[0] < input.length && point[1] >= 0
            && point[1] < input[point[0]].length) {
          minDistanceValue = input[point[0]][point[1]];
        } else {
          minDistanceValue = 0;
        }
      }
    }
    return minDistanceValue;
  }
}