city_main.java

城市轮廓线算法。采用分治发算法

package city;
import java.io.*;
import java.util.Vector;

public class city_main {

	public static void main(String[] args) throws IOException {
		Vector<point> borderlst = new Vector<point>();
		Vector<house> buildlst = new Vector<house>();
		house cur_house;
		String data = "data1.txt";
		File loadedFile = new File(data);
		FileInputStream inputstream;
		InputStreamReader fileinData;
		int num = 0;

		inputstream = new FileInputStream(loadedFile);
		fileinData = new InputStreamReader(inputstream);
		BufferedReader reader = new BufferedReader(fileinData);
		String line, strBuff = "";

		if ((line = reader.readLine()) != null) {
			strBuff = line;
		}
		num = Integer.parseInt(strBuff);
		// System.out.print(num);
		String[] str_tmps = new String[3];
		double left, height, right;
		for (int i = 0; i < num; i++) {
			if ((line = reader.readLine()) != null) {
				strBuff = line.substring(0, line.length() );
			}
			str_tmps = strBuff.split(" ");
			left = new Double(str_tmps[0]);
			height = new Double(str_tmps[1]);
			right = new Double(str_tmps[2]);
			cur_house = new house(left, height, right);
			buildlst.addElement(cur_house);
		}

		
		borderlst = combine(buildlst);
		
		PrintWriter out = new PrintWriter("result1.txt");
		
		for (int i = 0; i < borderlst.size(); i++) {
			out.println(borderlst.elementAt(i).toString());
		}
		out.close();
		
		java.util.ArrayList<point>borderlst1 = new java.util.ArrayList<point>();
		borderlst1 = new city_main().get_ext(buildlst,0,num);
		for(int i = 1; i < borderlst1.size()-1; i++){
			if(borderlst1.get(i).get_x()!= borderlst1.get(i-1).get_x()){
				if((borderlst1.get(i+1).get_height()-borderlst1.get(i).get_height())/(borderlst1.get(i+1).get_x()-borderlst1.get(i).get_x())
						==(borderlst1.get(i).get_height()-borderlst1.get(i-1).get_height())/(borderlst1.get(i).get_x()-borderlst1.get(i-1).get_x()))
					borderlst1.remove(i);
			}
		}
		
		for(int i=0;i<borderlst1.size()-2;i++)
			if (
					(borderlst1.get(i+2).get_height()-borderlst1.get(i+1).get_height())
					/(borderlst1.get(i+2).get_x()-borderlst1.get(i+1).get_x())==
						(borderlst1.get(i+1).get_height()-borderlst1.get(i).get_height())
						/(borderlst1.get(i+1).get_x()-borderlst1.get(i).get_x())){
				borderlst1.remove(i+1);
			}
		PrintWriter out1 = new PrintWriter("result1_ext.txt");
		
		for (int i = 1; i < borderlst1.size(); i++) {
			out1.println(borderlst1.get(i).toString());
		}
		out1.close();

	}
	public static Vector<point> combinebuild(Vector<house> buildlist) {
		house tmp_house_1, tmp_house_2;
		Vector<point> result = new Vector<point>();
		if (buildlist.size() == 1) {
			tmp_house_1 = buildlist.elementAt(0);
			result.addElement(new point(tmp_house_1.get_left(), tmp_house_1
					.get_height()));
			result.addElement(new point(tmp_house_1.get_right(), 0));
			return result;
		}
		if (buildlist.size() == 2) {
			tmp_house_1 = buildlist.elementAt(0);
			tmp_house_2 = buildlist.elementAt(1);
			if (tmp_house_1.get_left() > tmp_house_2.get_left()) {
				house tmp_house = tmp_house_1;
				tmp_house_1 = tmp_house_2;
				tmp_house_2 = tmp_house;
			}
			result.addElement(new point(tmp_house_1.get_left(), tmp_house_1
					.get_height()));
			if (tmp_house_2.get_left() < tmp_house_1.get_right()) {
				if (tmp_house_2.get_height() > tmp_house_1.get_height()) {
					result.addElement(new point(tmp_house_2.get_left(),
							tmp_house_2.get_height()));
				}
			} else {
				result.addElement(new point(tmp_house_1.get_right(), 0));
				result.addElement(new point(tmp_house_2.get_left(), tmp_house_2
						.get_height()));
				result.addElement(new point(tmp_house_2.get_right(), 0));
				return result;
			}
			if (tmp_house_2.get_right() < tmp_house_1.get_right()) {
				if (tmp_house_2.get_height() > tmp_house_1.get_height()) {
					result.addElement(new point(tmp_house_2.get_right(),
							tmp_house_1.get_height()));
				}
				result.addElement(new point(tmp_house_1.get_right(), 0));
			} else {
				if (tmp_house_2.get_height() < tmp_house_1.get_height()) {
					result.addElement(new point(tmp_house_1.get_right(),
							tmp_house_2.get_height()));
				}
				result.addElement(new point(tmp_house_2.get_right(), 0));
			}
			return result;
		}
		return result;
	}
	public static Vector<point> combineborder(Vector<point> borderlst1,
			Vector<point> borderlst2) {
		Vector<point> result = new Vector<point>();
		int max_x = 0, i, cur_h = 0, cur1_h = 0, cur2_h = 0;
		for (i = 0; i < borderlst1.size(); i++) {
			if (borderlst1.elementAt(i).get_x() > max_x)
				max_x = (int) borderlst1.elementAt(i).get_x();
		}
		for (i = 0; i < borderlst2.size(); i++) {
			if (borderlst2.elementAt(i).get_x() > max_x)
				max_x = (int) borderlst2.elementAt(i).get_x();
		}
		int j = 0, k = 0;
		for (i = 0; i <= max_x; i++) {
			if (j < borderlst1.size()) {
				if (borderlst1.elementAt(j).get_x() == i) {
					if (borderlst1.elementAt(j).get_height() > cur_h) {
						cur1_h = (int) borderlst1.elementAt(j).get_height();
						cur_h = cur1_h;
						result.add(borderlst1.elementAt(j));
					} else {
						if (cur_h == cur1_h) {
							if (cur2_h > borderlst1.elementAt(j).get_height()) {
								cur_h = cur2_h;
								result.add(new point(i, cur_h));
							} else {
								cur_h = (int) borderlst1.elementAt(j).get_height();
								result.add(new point(i, cur_h));
							}
						}
						cur1_h = (int) borderlst1.elementAt(j).get_height();
					}
					j++;
				}
			}
			if (k < borderlst2.size()) {
				if (borderlst2.elementAt(k).get_x() == i) {
					if (borderlst2.elementAt(k).get_height() > cur_h) {
						cur2_h = (int) borderlst2.elementAt(k).get_height();
						cur_h = cur2_h;
						result.add(borderlst2.elementAt(k));
					} else {
						if (cur_h == cur2_h) {
							if (cur1_h > borderlst2.elementAt(k).get_height()) {
								cur_h = cur1_h;
								result.add(new point(i, cur_h));
							} else {
								cur_h = (int) borderlst2.elementAt(k).get_height();
								result.add(new point(i, cur_h));
							}
						}
						cur2_h = (int) borderlst2.elementAt(k).get_height();
					}
					k++;
				}
			}
		}
		return result;
	}
	public static Vector<point> combine(Vector<house> buildlist) {
		if (buildlist.size() < 3) {
			return combinebuild(buildlist);
		} else {
			Vector<house> subbuildlist1 = new Vector<house>();
			Vector<house> subbuildlist2 = new Vector<house>();
			int i = 0;
			for (; i < buildlist.size() / 2; i++) {
				subbuildlist1.add(buildlist.elementAt(i));
			}
			for (; i < buildlist.size(); i++) {
				subbuildlist2.add(buildlist.elementAt(i));
			}
			Vector<point> tmp1 = combine(subbuildlist1);
			Vector<point> tmp2 = combine(subbuildlist2);
			return combineborder(tmp1, tmp2);
		}
	}
	
	public java.util.ArrayList<point> get_ext(Vector<house> buildlst,int begin, int end){
		java.util.ArrayList<point> result = new java.util.ArrayList<point>();
		if((end - begin) == 1){
			house tmp = buildlst.elementAt(begin);
			result.add(new point(tmp.get_left(),0));
			result.add(new point(tmp.get_left(),tmp.get_height()));
			result.add(new point(1.0*(tmp.get_left()+tmp.get_right())/2,tmp.get_height()+1.0*(tmp.get_right()-tmp.get_left())/2));
			result.add(new point(tmp.get_right(),tmp.get_height()));
			result.add(new point(tmp.get_right(),0));
			return result;
		}
		java.util.ArrayList<point> result1 = new java.util.ArrayList<point>();
		java.util.ArrayList<point> result2 = new java.util.ArrayList<point>();
		result1 = get_ext(buildlst,begin,(begin+end)/2);
		result2 = get_ext(buildlst,(begin+end)/2,end);
		/*for(int i = 0; i < result1.size(); i++){
			System.out.println(result1.get(i));
		}
		System.out.println("**********************");
		for(int i = 0; i < result2.size(); i++){
			System.out.println(result2.get(i));
		}
		System.out.println("**********************");*/
		int j = 0;
		int i = 0;
		for(; i < result1.size() || j < result2.size();){
			if(i==result1.size()){
				for(; j < result2.size(); j++)
					result.add(result2.get(j));
				break;
			}
			if(j==result2.size()){
				for(; i < result1.size(); i++)
					result.add(result1.get(i));
				break;
			}
			if(result1.get(i).get_x() < result2.get(j).get_x()){
				if(j==0){
					result.add(result1.get(i));
				}
				else{
					
					if(result2.get(j-1).get_height() > result2.get(j).get_height()){
						double tmp = result1.get(i).get_height()+result1.get(i).get_x()-result2.get(j).get_height()-result2.get(j).get_x();
						if(tmp<0){
							if(i > 0 &&result1.get(i-1).get_x()==result1.get(i).get_x()){
								double y = result2.get(j-1).get_height()-(result1.get(i).get_x()-result2.get(j-1).get_x());
								if(y < result1.get(i-1).get_height())
									result.add(new point(result1.get(i).get_x(),y));
							}
						}
						else if(tmp>0){
							if(i > 0){
								if(result1.get(i-1).get_x()==result1.get(i).get_x()){
									double y = result2.get(j-1).get_height()-(result1.get(i).get_x()-result2.get(j-1).get_x());
									if(y > result1.get(i-1).get_height())
										result.add(new point(result1.get(i).get_x(),y));
								}
								else if(result1.get(i-1).get_height()<result1.get(i).get_height()){
									double y = 1.0*(result2.get(j).get_height()+result1.get(i).get_height()-(result1.get(i).get_x()-result2.get(j).get_x()))/2;
									if(y < result1.get(i-1).get_height() && y > result1.get(i).get_height())
										result.add(new point(result1.get(i).get_x()-(result1.get(i).get_height() - y),y));
								}
							}
							result.add(result1.get(i));
						}
						else{
							if(result1.get(i).get_x()!=result2.get(j-1).get_x()&&i<result1.size()-1&&result1.get(i+1).get_height()>result1.get(i).get_height())
								result.add(result1.get(i));
						}
					}
					else if(result2.get(j-1).get_height() < result2.get(j).get_height()){
						double tmp = result2.get(j).get_height()-result1.get(i).get_height()+result1.get(i).get_x()-result2.get(j).get_x();
						if(tmp > 0){
							if(i > 0){
								if(result1.get(i-1).get_x()==result1.get(i).get_x()){
									double y = result2.get(j-1).get_height()+(result1.get(i).get_x()-result2.get(j-1).get_x());
									if(y < result1.get(i-1).get_height())
										result.add(new point(result1.get(i).get_x(),y));
								}
								else if(result1.get(i-1).get_x()>result1.get(i).get_x()){
									double y = 1.0*(result2.get(j).get_height()+result1.get(i).get_height()+(result1.get(i).get_x()-result2.get(j).get_x()))/2;
									if(y > result1.get(i-1).get_height() && y < result1.get(i).get_height())
										result.add(new point(result1.get(i).get_x()-(result1.get(i).get_height() - y),y));
								}
							}
						}
						else if(tmp < 0){
							if(i > 0 &&result1.get(i-1).get_x()==result1.get(i).get_x()){
								double y = result2.get(j-1).get_height()+(result1.get(i).get_x()-result2.get(j-1).get_x());
								if(y > result1.get(i-1).get_height())
									result.add(new point(result1.get(i).get_x(),y));
							}
							result.add(result1.get(i));
						}
						else if(tmp==0){
							if(i>0&&result1.get(i).get_height() < result1.get(i-1).get_height()&&result1.get(i).get_x()!=result2.get(j-1).get_x())
								result.add(result1.get(i));
						}
					}
				}
				i++;
			}
			else if(result1.get(i).get_x() > result2.get(j).get_x()){
				if(i==0){
					result.add(result2.get(j));
				}
				else{
					if(result1.get(i-1).get_height() > result1.get(i).get_height()){
						double tmp = result2.get(j).get_height()+result2.get(j).get_x()-result1.get(i).get_height()-result1.get(i).get_x();
						if(tmp<0){
							if(j > 0 &&result2.get(j-1).get_x()==result2.get(j).get_x()){
								double y = result1.get(i-1).get_height()-(result2.get(j).get_x()-result1.get(i-1).get_x());
								if(y < result2.get(j-1).get_height())
									result.add(new point(result2.get(j).get_x(),y));
							}
						}
						else if(tmp>0){
							if(j > 0){
								if(result2.get(j-1).get_x()==result2.get(j).get_x()){
									double y = result1.get(i-1).get_height()-(result2.get(j).get_x()-result1.get(i-1).get_x());
									if(y > result2.get(j-1).get_height())
										result.add(new point(result2.get(j).get_x(),y));
								}
								else if(result2.get(j-1).get_height()<result2.get(j).get_height()){
									double y = 1.0*(result2.get(j).get_height()+result1.get(i).get_height()-(result2.get(j).get_x()-result1.get(i).get_x()))/2;
									if(y < result2.get(j-1).get_height() && y > result2.get(j).get_height())
										result.add(new point(result2.get(j).get_x()-(result2.get(j).get_height() - y),y));
								}
							}
							result.add(result2.get(j));
						}
						else{
							if(result2.get(j).get_x()!=result1.get(i-1).get_x()&&j<result2.size()-1&&result2.get(j+1).get_height()>result2.get(j).get_height())
								result.add(result2.get(j));
						}
					}
					else if(result1.get(i-1).get_height() < result1.get(i).get_height()){
						double tmp = result1.get(i).get_height()-result2.get(j).get_height()+result2.get(j).get_x()-result1.get(i).get_x();
						if(tmp > 0){
							if(j > 0){
								if(result2.get(j-1).get_x()==result2.get(j).get_x()){
									double y = result1.get(i-1).get_height()+(result2.get(j).get_x()-result1.get(i-1).get_x());
									if(y < result2.get(j-1).get_height())
										result.add(new point(result2.get(j).get_x(),y));
								}
								else if(result2.get(j-1).get_x()>result2.get(j).get_x()){
									double y = 1.0*(result1.get(i).get_height()+result2.get(j).get_height()+(result2.get(j).get_x()-result1.get(i).get_x()))/2;
									if(y > result2.get(j-1).get_height() && y < result2.get(j).get_height())
										result.add(new point(result2.get(j).get_x()-(result2.get(j).get_height() - y),y));
								}
							}
						}
						if(tmp < 0){
							if(i > 0 &&result2.get(j-1).get_x()==result2.get(j).get_x()){
								double y = result1.get(i-1).get_height()+(result2.get(j).get_x()-result1.get(i-1).get_x());
								if(y > result2.get(j-1).get_height())
									result.add(new point(result2.get(j).get_x(),y));
								result.add(result2.get(j));
							}
						}
						if(tmp==0){
							if(j>0&&result2.get(j).get_height()<result2.get(j-1).get_height()&&result2.get(j).get_x()!=result1.get(i-1).get_x());
								result.add(result2.get(j));
						}
					}
				}
				j++;
			}
			else{
				if(result1.get(i).get_height() < result2.get(j).get_height())
					result.add(result2.get(j));
				else 
					result.add(result1.get(i));
				i++;
				j++;
			}
		}
		return result;
	}
}