Last active
April 8, 2020 02:37
-
-
Save wushbin/cbeb2e9eda8ed24d227774dc48499c21 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public int hilbertCurve(int x, int y, int n) { | |
// x, y coordinator range | |
int len = 1 << n; | |
int halfLen = 1 << (n - 1); | |
int quadrant = -1; | |
int newX = -1; | |
int newY = -1; | |
if (x < halfLen && y < halfLen) { | |
quadrant = 0; | |
newX = halfLen - 1 - y; | |
newY = x; | |
} else if (x < halfLen && y >= halfLen) { | |
quadrant = 1; | |
newX = x; | |
newY = y - halfLen; | |
} else if (x >= halfLen && y >= halfLen) { | |
quadrant = 2; | |
newX = x - halfLen; | |
newY = y - halfLen; | |
} else { | |
quadrant = 3; | |
newX = y; | |
newY = len - 1 - x; | |
} | |
if (n == 1) { | |
return quadrant; | |
} | |
int quadrantNum = halfLen * halfLen ; | |
if (quadrant == 0) { | |
return quadrantNum - 1 - hilbertCurve(newX, newY, n - 1); | |
} else if (quadrant == 1) { | |
return 1 * quadrantNum + hilbertCurve(newX, newY, n - 1); | |
} else if (quadrant == 2) { | |
return 2 * quadrantNum + hilbertCurve(newX, newY, n - 1); | |
} else { | |
return 4 * quadrantNum - 1 - hilbertCurve(newX, newY, n - 1); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import org.junit.Test; | |
import java.io.*; | |
import java.util.*; | |
public class HilbertCurve { | |
class InputValues { | |
int x; | |
int y; | |
int n; | |
public InputValues(int x, int y, int n) { | |
this.x = x; | |
this.y = y; | |
this.n = n; | |
} | |
@Override | |
public String toString() { | |
return "x: " + x + "\ty: " + y + "\tn: " + n; | |
} | |
} | |
@Test | |
public void test() { | |
File[] files = readFolder("src/input/HilbertCurve"); | |
HilbertCurve.InputValues test = readFile(files[12]); | |
System.out.println(test); | |
int res = hilbertCurve(test.x, test.y, test.n); | |
System.out.println(res); | |
} | |
public void generateOutput() throws IOException { | |
File[] files = readFolder("src/input/HilbertCurve"); | |
for (int i = 0; i < files.length; i++) { | |
File file = files[i]; | |
HilbertCurve.InputValues test = readFile(file); | |
String outfileName = "src/output/HilbertCurve/" + file.getName().replace(".in", ".out"); | |
File outfile = new File(outfileName); | |
outfile.getParentFile().mkdirs(); | |
outfile.createNewFile(); | |
int result = hilbertCurve(test.x, test.y, test.n); | |
PrintWriter printWriter = new PrintWriter(new FileWriter(outfileName)); | |
printWriter.println(result); | |
printWriter.close(); | |
} | |
} | |
public int hilbertCurve(int x, int y, int n) { | |
// x, y coordinator range | |
int len = 1 << n; | |
int halfLen = 1 << (n - 1); | |
int quadrant = -1; | |
int newX = -1; | |
int newY = -1; | |
if (x < halfLen && y < halfLen) { | |
quadrant = 0; | |
newX = halfLen - 1 - y; | |
newY = x; | |
} else if (x < halfLen && y >= halfLen) { | |
quadrant = 1; | |
newX = x; | |
newY = y - halfLen; | |
} else if (x >= halfLen && y >= halfLen) { | |
quadrant = 2; | |
newX = x - halfLen; | |
newY = y - halfLen; | |
} else { | |
quadrant = 3; | |
newX = y; | |
newY = len - 1 - x; | |
} | |
if (n == 1) { | |
return quadrant; | |
} | |
int quadrantNum = halfLen * halfLen ; | |
if (quadrant == 0) { | |
return quadrantNum - 1 - hilbertCurve(newX, newY, n - 1); | |
} else if (quadrant == 1) { | |
return 1 * quadrantNum + hilbertCurve(newX, newY, n - 1); | |
} else if (quadrant == 2) { | |
return 2 * quadrantNum + hilbertCurve(newX, newY, n - 1); | |
} else { | |
return 4 * quadrantNum - 1 - hilbertCurve(newX, newY, n - 1); | |
} | |
} | |
private int getInt(String name) { | |
return Integer.parseInt(name.replaceAll("\\D", "")); | |
} | |
private File[] readFolder(String path) { | |
File folder = new File(path); | |
File[] files = folder.listFiles(); | |
Arrays.sort(files, (a, b) -> getInt(a.getName()) - getInt(b.getName())); | |
return files; | |
} | |
private HilbertCurve.InputValues readFile(File file) { | |
try { | |
// assume the input file is always valid | |
Scanner sc = new Scanner(file); | |
String[] inputs = sc.nextLine().split(" "); | |
int x = Integer.parseInt(inputs[0]), y = Integer.parseInt(inputs[1]), n = Integer.parseInt(inputs[2]); | |
sc.close(); | |
return new HilbertCurve.InputValues(x, y, n); | |
} catch (FileNotFoundException e) { | |
System.out.println(file.getName() + " not exist"); | |
} | |
return null; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment