6

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.

Community
  • 1
  • 1
Anthony Korzan
  • 63
  • 6
  • 1
    can you update the question with the output you are trying to achieve? not sure what you are going for. – Andy Guibert May 01 '15 at 03:12
  • @aguibert I added a few examples. The 45 degree one is straight forward to transform by hand, not so much for a smaller rotation, but I tried to emulate it by hand. Hopefully this will allow me to create more complex shapes represented by the bits, using longs instead of chars. I'll be creating these shapes from the alpha channel of PNGs. For example an airplane sprite is not accurately bounded by rectangles, so using a Rectangle2D object for collision detection isn't ideal. Path2D allowed me to create more accurate collision boxes--but it is very very slow for complicated shapes. – Anthony Korzan May 01 '15 at 03:23

2 Answers2

3

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;
  }
}
Community
  • 1
  • 1
Patricia Shanahan
  • 25,849
  • 4
  • 38
  • 75
  • Mapping output to input is the better approach – Rob Audenaerde May 01 '15 at 08:45
  • @RobAu in general it is better yes, but if you only want to see if there is collision the other version can be good enough and is surely a lot faster for sparse matrices – maraca May 01 '15 at 10:08
  • correct me if I'm wrong, but shouldn't move to center be `... - output.length / 2.0 + 0.5` ? same for oldY? – maraca May 01 '15 at 10:37
  • @maraca That totally depends on how the rotation is calculated and the matrices are stored. – Rob Audenaerde May 01 '15 at 12:16
  • @RobAu you see how the rotation is calculated... I've shown it in my answer. And you can optimize things best if you indeed have some knowledge. I just don't see how this would improve things compared to the solution he already has. Or just very minor improvement. – maraca May 01 '15 at 12:32
  • 1
    @maraca This way round won't get holes, which seemed to be a concern. If you care about sparse matrix performance more than about hole-avoidance, the original solution is better. – Patricia Shanahan May 01 '15 at 13:01
  • PatriciaShanahan, your answer is great and very well written. As other's mentioned, mapping output to input avoids many of the complications with @marca's answer. The downside is the numerous branches with this approach and the additional for loop. I tested Marca's answer and the holes are only one bit large. And with simple bounds checking, I can avoid small objects entering a mask. Marca's answer is good enough and I greatly appreciate both of your time spend on this problem. I am going to convert the the matrix to an array of longs, and use bitshifts for the 2nd dimension. – Anthony Korzan May 03 '15 at 02:33
1

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;
   }
  }
}
maraca
  • 8,468
  • 3
  • 23
  • 45
  • When rad = Math.toRadians(45), there is a hole. `00000000 00001000 00011000 00101100 01111110 00011000 00001000 00000000` The hole also seems to be due to a hole generated in the center that is transposed from the rounding. But for the small sample size it is hard to tell if that is the only edge case. I am reading up on rotation matrices, as it seems that is the way I should go with this problem. – Anthony Korzan May 01 '15 at 05:25
  • And when I enlarged the array to 12x12, and removed rounding to more properly align the holes for debugging, as all the holes are transposed by 1 unit with rounding, there are more holes. `000001000000 000011100000 000110110000 001011101000 011111111100 110110110110 011111111100 001011101000 000110110000 000011100000 000001000000 000000000000` – Anthony Korzan May 01 '15 at 05:34
  • @AnthonyKorzan right, but do the holes really matter for collision detection, I don't think you will get like two pieces of a puzzle that miraculously fit together even though there would be a collision. – maraca May 01 '15 at 10:13
  • @AnthonyKorzan updated my answer to show you why I did it like this and how to optimize more – maraca May 01 '15 at 12:04
  • You could even store the first and last row and column with 1s in it and then start/end iteration there when rotating for further improvement – maraca May 01 '15 at 12:26
  • @marca, thank you. Your approach is the least complex, though with holes that are not bigger than 1 bit. Not a problem as an object shouldn't really be 1x1 pixel size unless there's scaling of the bit matrix--a 64x64 bit matrix representing a 128x128 sprite. Simple bounds checking should prevent any complications if that would be the case. – Anthony Korzan May 03 '15 at 02:35
  • You're welcome glad it helped. If you have 'flat' objects, that are only big in one dimension and not in the other, then a simple min/max for x and y (i.e. i and j) could be a big improvemet. So instead of making the input sparse calculate the mins and maxes, then you have `rotate(int[][] input, double degrees, int minX, int maxX, int minY, int maxY)` and inside `for (int i = minY; i <= maxY; i++)` – maraca May 03 '15 at 03:39