combine.java

Java实现的采用分治算法的城市轮廓线程序

import java.util.*;

public class Combine {    // 合并轮廓类
	public ArrayList<Point> com2building(ArrayList<Building> buildlist){    // 合并建筑物函数
		Building temp1, temp2;
		ArrayList<Point> result = new ArrayList<Point>();
		if (buildlist.size() == 1){
			temp1 = buildlist.get(0);
			result.add(new Point(temp1.getb(), temp1.geth()));
			result.add(new Point(temp1.gete(),0));
			return result;
		} else {
			temp1 = buildlist.get(0);
			temp2 = buildlist.get(1);
			if(temp1.getb() > temp2.getb()) {
				Building tp = temp1;
				temp1 = temp2;
				temp2 = tp;
			}
			result.add(new Point(temp1.getb(),temp1.geth()));
			if(temp1.gete() > temp2.gete()) {
				if(temp1.geth() < temp2.geth()) {
					result.add(new Point(temp2.getb(), temp2.geth()));
					result.add(new Point(temp2.gete(), temp1.geth()));
				}
				result.add(new Point(temp1.gete(), 0));
				return result;
			}
			if(temp1.gete() < temp2.gete() && temp2.getb() < temp1.gete()) {
				if(temp1.geth() > temp2.geth()) result.add(new Point(temp1.gete(), temp2.geth()));
				else result.add(new Point(temp2.getb(), temp2.geth()));
				result.add(new Point(temp2.gete(), 0));
				return result;
			}
			if(temp2.getb() > temp1.gete()) {
				result.add(new Point(temp1.gete(), 0));
				result.add(new Point(temp2.getb(), temp2.geth()));
				result.add(new Point(temp2.gete(), 0));
				return result;
			}
		}
		return result;
	}
	
	public ArrayList<Point> com2border(ArrayList<Point> border1, ArrayList<Point> border2){    // 合并轮廓函数
		ArrayList<Point> result = new ArrayList<Point>();
		ArrayList<Point> border = new ArrayList<Point>();
		int end = 0 , j, k = 0, cur = 0;
		int[] current = {0, 0};
		int[] count = {0, 0};
		for(int i = 0; i < border1.size(); i++){
			if(border1.get(i).getx() > end) end = border1.get(i).getx();
		}
		for(int i = 0; i < border2.size(); i++){
			if(border2.get(i).getx() > end) end = border2.get(i).getx();
		}
		for(int i = 0; i<= end; i++) {
			for(j = 0; j < 2; j++) {
				if(j == 0) border = border1;
				else border = border2;
				if(count[j] < border.size()) {
				if(border.get(count[j]).getx() == i) {
					if(border.get(count[j]).gety() > cur) {
						current[j] = border.get(count[j]).gety();
						cur = current[j];
						result.add(border.get(count[j]));
					} else {
						if(cur == current[j]){
							if(j == 0) k = 1;
							else k = 0;
							if (current[k] > border.get(count[j]).gety()){
								cur = current[k];
								result.add(new Point(i, cur));
							} else {
								cur = border.get(count[j]).gety();
								result.add(new Point(i, cur));
							}
						}
						current[j] = border.get(count[j]).gety();
					}
					count[j]++;
				}
			}
			}
		}
		return result;
	}
	
	public ArrayList<Point> combine(ArrayList<Building> build){    // 合并函数
		if(build.size() < 3){
			return com2building(build);
		} else {
			ArrayList<Building> subbuild1 = new ArrayList<Building>();
			ArrayList<Building> subbuild2 = new ArrayList<Building>();
			int i = 0;
			for(; i < build.size() / 2; i++) subbuild1.add(build.get(i));
			for (; i < build.size(); i++) subbuild2.add(build.get(i));
			ArrayList<Point> tmp1 = combine(subbuild1);
			ArrayList<Point> tmp2 = combine(subbuild2);
			return com2border(tmp1,tmp2);
		}
	}
}