main_city.java

用分治法实现城市轮廓问题

package ex1_cityoutline_squ;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.util.ArrayList;

public class Main_City {
	ArrayList<Building> buildingLst;
	ArrayList<CityLinePoint> lineLst;

	public Main_City(String fileName) throws Exception {
		buildingLst = new ArrayList<Building>();
		lineLst = new ArrayList<CityLinePoint>();
		setBuildingLst(fileName, buildingLst);

	}

	private void setBuildingLst(String fileName, ArrayList<Building> buildingLst)
			throws Exception {
		BufferedReader br = new BufferedReader(new FileReader(fileName));
		String line = br.readLine();
		int buildingNum;
		String[] buildingInfo = new String[3];
		Building tempBuilding = null;
		double left;
		double height;
		double right;

		if (line != null) {
			buildingNum = Integer.parseInt(line);
			System.out.println("建筑物的数目为：" + buildingNum);
		}

		while ((line = br.readLine()) != null) {
			buildingInfo = line.split(" ");
			left = Double.parseDouble(buildingInfo[0]);
			height = Double.parseDouble(buildingInfo[1]);
			right = Double.parseDouble(buildingInfo[2]);
			System.out.println("建筑物信息为---------------------------------");
			System.out.println("左界为：" + left);
			System.out.println("高度为：" + height);
			System.out.println("右界为：" + right);
			tempBuilding = new Building(left, height, right);
			buildingLst.add(tempBuilding);
		}

		br.close();
		br = null;
	}

	public void process(String fileName)throws Exception{
		getCityLine();
		writeCityLinePoint(fileName);
	}
	
	public void getCityLine() {
		lineLst = merge(buildingLst);
		System.out.println("城市轮廓线为：--------------------------------------");
		for (CityLinePoint p : lineLst) {
			System.out.println(p.toString());
		}
	}

	public ArrayList<CityLinePoint> merge(ArrayList<Building> buildingLst) {
		if (buildingLst.size() < 3) {
			return mergeBuildingLst(buildingLst);
		} else {
			// 记录Building的上下界以及中间值，用来分治法计算
			int minBuildingNum = 0;
			int maxBuildingNum = buildingLst.size();
			int middle = (minBuildingNum + maxBuildingNum) / 2;

			ArrayList<Building> tempBuildingLst1 = new ArrayList<Building>();
			ArrayList<Building> tempBuildingLst2 = new ArrayList<Building>();

			for (int i = minBuildingNum; i < middle; i++) {
				tempBuildingLst1.add(buildingLst.get(i));
			}
			for (int i = middle; i < maxBuildingNum; i++) {
				tempBuildingLst2.add(buildingLst.get(i));
			}

			ArrayList<CityLinePoint> lineLst1 = merge(tempBuildingLst1);
			ArrayList<CityLinePoint> lineLst2 = merge(tempBuildingLst2);
			return mergeLineLst(lineLst1, lineLst2);
		}
	}

	public ArrayList<CityLinePoint> mergeBuildingLst(
			ArrayList<Building> buildingLst) {
		ArrayList<CityLinePoint> lineLst = new ArrayList<CityLinePoint>();
		Building tempBuilding = null;
		Building tempBuilding2 = null;
		CityLinePoint tempLine = null;
		if (buildingLst.size() == 0) {
			return null;
		} else if (buildingLst.size() == 1) {
			tempBuilding = buildingLst.get(0);
			double left = tempBuilding.getLeft();
			double right = tempBuilding.getRight();
			double height = tempBuilding.getHeight();
			lineLst.add(new CityLinePoint(left, height));
			lineLst.add(new CityLinePoint(right, 0));
		} else {
			tempBuilding = buildingLst.get(0);
			tempBuilding2 = buildingLst.get(1);
			double left1, left2, right1, right2, height1, height2;
			left1 = tempBuilding.getLeft();
			right1 = tempBuilding.getRight();
			height1 = tempBuilding.getHeight();
			left2 = tempBuilding2.getLeft();
			right2 = tempBuilding2.getRight();
			height2 = tempBuilding2.getHeight();

			// 确定轮廓的第一个点
			if (left1 == left2) {
				if (height1 > height2) {
					lineLst.add(new CityLinePoint(left1, height1));
				} else {
					lineLst.add(new CityLinePoint(left2, height2));
				}
			} else {
				if (left1 > left2) {
					// 此时将两座建筑物的信息交换,以方便后面的讨论
					double temp;
					temp = left1;
					left1 = left2;
					left2 = temp;
					temp = right1;
					right1 = right2;
					right2 = temp;
					temp = height1;
					height1 = height2;
					height2 = temp;
				}
				lineLst.add(new CityLinePoint(left1, height1));
			}

			// 确定轮廓接下来的点
			if (left2 < right1) {
				if (height2 > height1) {
					lineLst.add(new CityLinePoint(left2, height2));
					if (right2 < right1) {
						lineLst.add(new CityLinePoint(right2, height1));
						lineLst.add(new CityLinePoint(right1, 0));
					} else {
						lineLst.add(new CityLinePoint(right2, 0));
					}
				} else {
					if (right2 <= right1) {
						lineLst.add(new CityLinePoint(right1, 0));
					} else {
						lineLst.add(new CityLinePoint(right1, height2));
						lineLst.add(new CityLinePoint(right2, 0));
					}
				}
			} else if (left2 == right1) {
				lineLst.add(new CityLinePoint(left2, height2));
				lineLst.add(new CityLinePoint(right2, 0));
			} else if (left2 > right1) {
				lineLst.add(new CityLinePoint(right1, 0));
				lineLst.add(new CityLinePoint(left2, height2));
				lineLst.add(new CityLinePoint(right2, 0));
			}

		}

		return lineLst;

	}

	public ArrayList<CityLinePoint> mergeLineLst(
			ArrayList<CityLinePoint> lineLst1, ArrayList<CityLinePoint> lineLst2) {
		ArrayList<CityLinePoint> newLineLst = new ArrayList<CityLinePoint>();
		// 定义2个轮廓线的指针和大小
		int pointer1 = 0;
		int size1 = lineLst1.size();
		int pointer2 = 0;
		int size2 = lineLst2.size();
		// 记录轮廓线中某点之前的高度
		double previousHeight1 = 0;
		double previousHeight2 = 0;
		while (pointer1 < size1 && pointer2 < size2) {
			CityLinePoint linePoint1 = lineLst1.get(pointer1);
			CityLinePoint linePoint2 = lineLst2.get(pointer2);
			// 定义轮廓线的位置和高度变量
			double position1, position2, height1, height2;
			position1 = linePoint1.getPosition();
			height1 = linePoint1.getHeight();
			position2 = linePoint2.getPosition();
			height2 = linePoint2.getHeight();
			if (position1 == position2) {
				if (height1 > height2) {
					newLineLst.add(new CityLinePoint(position1, height1));
				} else {
					newLineLst.add(new CityLinePoint(position2, height2));
				}
				pointer1++;
				pointer2++;
			} else if (position1 < position2) {
				height2 = previousHeight2;
				if (height1 >=height2) {
					newLineLst.add(new CityLinePoint(position1, height1));
				}else{
					if(previousHeight1>height2){
						newLineLst.add(new CityLinePoint(position1, height2));
						
					}
				}
				pointer1++;
			} else {
				height1 = previousHeight1;
				if (height2 >= height1) {
					newLineLst.add(new CityLinePoint(position2, height2));
				}else{
					if(previousHeight2>height1){
						newLineLst.add(new CityLinePoint(position2, height1));
						
					}
				}
				pointer2++;
			}
			previousHeight1 = height1;
			previousHeight2 = height2;
		}

		while(pointer1<size1){
			newLineLst.add(lineLst2.get(pointer1));
			pointer1++;
		}
		while(pointer2<size2){
			newLineLst.add(lineLst2.get(pointer2));
			pointer2++;
		}
		return newLineLst;
	}

	public void writeCityLinePoint(String fileName) throws Exception{
		System.out.println("loading......");
		BufferedWriter bw=new BufferedWriter(new FileWriter(new File(fileName)));
		for(CityLinePoint p:lineLst){
			bw.write(p.toString()+"\n");
		}
		bw.flush();
		bw.close();
		System.out.println("complete!");
	}

	public static void main(String[] args) throws Exception {
		Main_City city = new Main_City("data_ex1_cityoutline\\square_data\\data3.txt");
		city.process("data_ex1_cityoutline\\square_output\\result3.txt");
	}
}