Bit matrix rotation

Question

Let's say I use a char array of size 8 to represent the collision mask for the image. Each char bit is a pixel. In fact, I will use a long array [64] for a 64x64 matrix.

So the field will appear as:

00000000 01111110 01111110 01111110 01111110 01111110 01111110 00000000 

An example of 45 degrees output should look like this, although rotations can be of any degree. This shape may not be accurate to rotate 45 degrees, since I did it manually.

 00011000 00111100 01111110 11111111 11111111 01111110 00111100 00011000 

And another example of output with a slight rotation to the right - 10 degrees? The values ​​are probably incorrect, because mathematically I don’t know exactly how it will rotate, but I think it is safe to assume that if each bit has more than 50% coverage of the old form, then this will be 1.

 00000000 00111111 01111111 01111110 01111110 11111110 11111100 00000000 

Without rotation, collision searches between these bitmasks are performed quickly using bit offsets as defined in this stackoverflow answer: https://stackoverflow.com/a/4646262

In the past, I used Path2D, Rectangles, Shapes, etc .... and used AffineTransform to rotate objects. Path2D was the only class to offer the complex forms I wanted, but the behavior of a “linked list” to access each point is not as fast as we would like.

What is the best way to move a binary map in Java?

It also seems that the Java libraries for Matrices are also not the fastest.

Answer 1

This solution is based on the previous answer . Instead of displaying an entry point at 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 nearest integer index point. This can lead to better results with a more complicated calculation of a value that uses a distance-weighted sum of values ​​for neighboring 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 

Testing 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 that it is best to display output records as a whole, but this may be enough to detect a collision. And you can set the internal points to 0 to make them even more sparse (unless you 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 enough, but you can only convert them, I hope it makes some sense, I don’t know if you will get “holes” (0s between them), and also it works, only if you have enough 0s around them or the index goes beyond one way or another, 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; } } }