Marching Square学习笔记

Marching Square是一种等值线轮廓的算法，具体可以参考wiki Marching Square

算法解释

英语好的可以直接看wiki中的解释，还可以参考这片文档 算法原理解释 感谢这篇博主的作者，让我这个英语不好的看明白了这个算法

相关代码

这里只列举java实现的 code 代码解释： 下载上述链接中的最新版本，我是用作者原始版本看的，最新版本实现了原始版本的并行化（但是我没运行出相同的结果）

package marchingsquares; import java.awt.Color; import java.awt.Dimension; import java.awt.Graphics; import java.awt.Graphics2D; import java.awt.Toolkit; import java.awt.geom.AffineTransform; import java.awt.geom.GeneralPath; import java.util.ArrayList; import java.util.Random; import javax.swing.JFrame; import marchingsquares.util.FileUtils; import marchingsquares.util.RandomColor; /** * http://udel.edu/~mm/code/marchingSquares/ * * * */ public class MarchingSquareTest extends JFrame { /** * */ private static final long serialVersionUID = 1L; public static void main(String[] args) { JFrame t = new MarchingSquareTest(); Dimension screensize = Toolkit.getDefaultToolkit().getScreenSize(); int w = screensize.width; int h = screensize.height; t.setSize(w, h); t.setVisible(true); t.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); } public void paint(Graphics g) { // Generate Isolines double[][] data_mW = getData("data.txt", 87, 61); // 是用来画等值线的数据 double[] levels_mW = getThresholdValue(); // 轮廓线的取值 MarchingSquares marchingSquares = new MarchingSquares(); GeneralPath[] isolines = marchingSquares.mkIsos(data_mW, levels_mW); // 创建轮廓线的核心接口 //下面是把轮廓线可视化展示，需要进行坐标转换 Dimension screensize = Toolkit.getDefaultToolkit().getScreenSize(); int w = screensize.width; int h = screensize.height; setSize(w, h); AffineTransform xf = new AffineTransform(); double lon0=0; double lat0 =0; double lat1 = h-100; double lon1 = w-100; double cellX = data_mW.length+2; double cellY = data_mW[0].length+2; double coffx = (lon1 - lon0) / (cellX - 0); double coffy = (lat1 - lat0) / (cellY - 0); coffx = Math.min(coffx, coffy);//缩放系数 xf.translate(lon0, lat0); // Because MxN data was padded to (M+2)x(N+2). xf.scale(coffx,coffy); xf.translate(10, 10); for (int i = 0; i < isolines.length; i++) { isolines[i].transform(xf); // Permanent mapping to world coords. } //画图 Graphics2D g2 = (Graphics2D) g; Random random = new Random(); float start = 0; float add =20; float f1 = 0.5f; float f2 =0.90f; for(int i=0;i<isolines.length;i++){ GeneralPath iso = isolines[i]; // Draw Isolines Color isoColor = RandomColor.HSVtoRGB(start+add*i, f1, f2); // g2.setColor(isoColor); // g2.fill(iso); // Color iso. g2.setColor(isoColor); g2.draw(iso); // Outline iso. } } private static double[] getThresholdValue() { int min = 90; int max = 195; int add = 5; double[] value = new double[(max - min) / add + 1]; for (int i = 0; i < value.length; i++) { value[i] = min + i * add; } return value; } public static double[][] getData(String fileName, int width, int height) { ArrayList<String> contents = FileUtils.getStringFromFile(fileName); if (contents.size() == 1) { String line = contents.get(0).replaceAll("[\\[|\\]]", ""); String[] line2Array = line.split(","); double[][] data = new double[height][width]; double min = Double.MAX_VALUE; for (int i = 0; i < line2Array.length; i++) { double d = Double.parseDouble(line2Array[i]); data[i / width][i % width] = d; min = Math.min(min, d); } System.out.println("min="+min); return data; } return null; } } public static ArrayList<String> getStringFromFile(String filePath){ BufferedReader br=null; ArrayList<String> hs =null; try { hs = new ArrayList<String>(); File aidFile = new File(filePath); if (!aidFile.exists()) { return hs; } FileReader fr = new FileReader(aidFile); String line = null; br = new BufferedReader(fr); while ((line = br.readLine()) != null) { hs.add(line); } }catch(Exception e){ e.printStackTrace(); } finally { try { br.close(); } catch(IOException e) { // ignore... } } return hs; } /* * 想构造一系列平滑过渡的颜色，用HSV颜色空间容易，用RGB较难。 * * 将色彩由HSV空间转换到RGB空间 * * h 颜色 用角度表示，范围：0到360度 s 色度 0.0到1.0 0为白色，越高颜色越“纯” v 亮度 0.0到1.0 0为黑色，越高越亮 */ public static Color HSVtoRGB(float h /* 0~360 degrees */, float s /* 0 ~ 1.0 */, float v /* 0 ~ 1.0 */ ) { float f, p, q, t; if (s == 0) { // achromatic (grey) return makeColor(v, v, v); } h /= 60; // sector 0 to 5 int i = (int) Math.floor(h); f = h - i; // factorial part of h p = v * (1 - s); q = v * (1 - s * f); t = v * (1 - s * (1 - f)); switch (i) { case 0: return makeColor(v, t, p); case 1: return makeColor(q, v, p); case 2: return makeColor(p, v, t); case 3: return makeColor(p, q, v); case 4: return makeColor(t, p, v); default: // case 5: return makeColor(v, p, q); } } public static Color makeColor(float v, float p, float q) { return new Color(v, p, q); }

参考文献

[1]https://en.wikipedia.org/wiki/Marching_squares [2]http://www.tomgibara.com/computer-vision/marching-squares [3]https://blog.csdn.net/silangquan/article/details/47054309#commentBox [4]http://udel.edu/~mm/code/marchingSquares/