旋转位矩阵
Rotating a bit matrix
假设我使用大小为 8 的字符数组来表示图像的碰撞遮罩。 char 的每一位代表一个像素。实际上，我将为 64x64 矩阵使用 long[64] 数组。
所以一个框将显示为：
00000000
01111110
01111110
01111110
01111110
01111110
01111110
00000000
45 度的示例输出应如下所示，但旋转可以是任何度数。这个形状对于 45 度旋转可能不准确，因为我是手工制作的。
00011000
00111100
01111110
11111111
11111111
01111110
00111100
00011000
还有另一个向右小旋转 --10 度的示例输出？这些值可能是错误的，因为在数学上我不知道它究竟会如何旋转，但我认为可以安全地假设如果每个位对旧形状的覆盖率超过 50%，那么它将是 1。
00000000
00111111
01111111
01111110
01111110
11111110
11111100
00000000
在没有旋转的情况下，可以快速找到这些位掩码之间的冲突，使用此 Whosebug 回复中定义的位移位：
现在，过去我使用过 Path2D、Rectangles、Shapes 等...并使用 AffineTransform 来旋转对象。 Path2D 是唯一 class 提供我想要的复杂形状的，但它 "linked-list like" 访问每个点的行为并不像我希望的那样快。
在 Java 中旋转二进制地图的最佳方法是什么？
似乎 Java 矩阵库也不是最快的。
我同意通常映射输出的条目更好，但这足以检测碰撞。你可以将内部点设置为 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;
}
旧答案：
我不知道这是否足够好，但你只能转换那些，希望它有意义，我不知道你是否会得到 "holes"（两者之间为 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;
}
}
}
此解决方案基于 。它不是将输入点映射到输出点，而是将输出点映射到输入矩阵 space.
中的位置
在此版本中，它仅使用最接近的整数索引点的值。使用相邻点值的距离加权和的更复杂的值计算可能会获得更好的结果。
以下是一些结果：
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;
}
}
假设我使用大小为 8 的字符数组来表示图像的碰撞遮罩。 char 的每一位代表一个像素。实际上，我将为 64x64 矩阵使用 long[64] 数组。
所以一个框将显示为：
00000000
01111110
01111110
01111110
01111110
01111110
01111110
00000000
45 度的示例输出应如下所示，但旋转可以是任何度数。这个形状对于 45 度旋转可能不准确，因为我是手工制作的。
00011000
00111100
01111110
11111111
11111111
01111110
00111100
00011000
还有另一个向右小旋转 --10 度的示例输出？这些值可能是错误的，因为在数学上我不知道它究竟会如何旋转，但我认为可以安全地假设如果每个位对旧形状的覆盖率超过 50%，那么它将是 1。
00000000
00111111
01111111
01111110
01111110
11111110
11111100
00000000
在没有旋转的情况下，可以快速找到这些位掩码之间的冲突，使用此 Whosebug 回复中定义的位移位：
现在，过去我使用过 Path2D、Rectangles、Shapes 等...并使用 AffineTransform 来旋转对象。 Path2D 是唯一 class 提供我想要的复杂形状的，但它 "linked-list like" 访问每个点的行为并不像我希望的那样快。
在 Java 中旋转二进制地图的最佳方法是什么？
似乎 Java 矩阵库也不是最快的。
我同意通常映射输出的条目更好，但这足以检测碰撞。你可以将内部点设置为 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;
}
旧答案： 我不知道这是否足够好，但你只能转换那些，希望它有意义，我不知道你是否会得到 "holes"（两者之间为 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;
}
}
}
此解决方案基于
在此版本中，它仅使用最接近的整数索引点的值。使用相邻点值的距离加权和的更复杂的值计算可能会获得更好的结果。
以下是一些结果：
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;
}
}