Rotating a bit matrix

Question

Let's say I am using a char array of size 8 to represent a collision mask for an image. Each bit of the char represents a pixel. In reality I will be using a long[64] array for a 64x64 matrix.

So a box will appear as:

00000000
01111110
01111110
01111110
01111110
01111110
01111110
00000000

An example output for 45 degrees should look like this, though the rotations can be any degrees. This shape may not be accurate for a 45 degree rotation, as I did it by hand.

00011000
00111100
01111110
11111111
11111111
01111110
00111100
00011000

And another example output with a small rotation to the right--10 degrees? The values are probably wrong, as mathematically I don't know how exactly it'll rotate, but I think it is safe to assume that if each bit has over 50% coverage of the old shape, then it'ld be 1.

00000000
00111111
01111111
01111110
01111110
11111110
11111100
00000000

Without rotation, finding collisions between these bit masks is fast, using bitshifts as defined in this stackoverflow reply: https://stackoverflow.com/a/336615/4595736

Now, in the past I have used Path2D, Rectangles, Shapes, etc... and used an AffineTransform to rotate the objects. Path2D was the only class to offer the complex shapes I desired, but it's "linked-list like" behavior for accessing each point isn't as fast as I would like it to be.

What is the best way to go around rotating a binary map in Java?

It also seems like Java libraries for Matrices aren't the fastest either.

Answer 1

This solution is based on the prior answer. Instead of mapping an input point to an output point, it maps an output point to a location in the input matrix space.

In this version, it simply uses the value for the closest integer index point. It might get better results with a more sophisticated value calculation that uses a distance-weighted sum of the values for the neighbor points.

Here are some results:

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

Test program:

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

Answer 2

I agree it is better to map the entries of the output in general, but this can be sufficient to detect collision. And you can set the inner points to 0 to make it even more sparse (if you don't have very small objects that can jump into others):

...

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

Old answer: I don't know if this is good enough, but you could only transform the ones, hope it makes any sense, I don't know if you will get "holes" (0s in between the ones) and also this only works if you have enough 0s around the ones or the index will get out of bounds, anyways here is my suggestion:

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