intersection.java

实现垂直水平线计算交点的算法

package ex3_intersection;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Scanner;
import java.util.TreeSet;

public class Intersection {
    private  int numOfV;
    private  int numOfH;
     horiz[]  horizon;                      // horizonal line
    vert[]   vertic;                      //vertical line
     X[]    x;
     public int  total_num=0;
     public ArrayList  al;
	/**
	 * @param args
	 * @throws FileNotFoundException 
	 */
	public void Intersect(FileInputStream fr) throws FileNotFoundException {
		al=new ArrayList();
		   //Read File
		Scanner s=new Scanner(fr);
        numOfH=s.nextInt();
        numOfV=s.nextInt();
        horizon=new horiz[numOfH];
        vertic=new vert[numOfV];
        TreeSet<Integer> tree=new TreeSet<Integer>();  //候选集                  
        x=new X[2*numOfH+numOfV];                //x坐标集合
        int l=0;
        for(int i=0;i<numOfH;i++)               //读入x轴数据,存于数组X中
        {   
        	horizon[i]=new horiz();
        	x[l]=new X();
         	horizon[i].xleft=s.nextInt();
        	x[l].position=horizon[i].xleft;
        	x[l].belong=i;
        	x[l].LorR=0;
        	l++;
        	x[l]=new X();
        	horizon[i].xright=s.nextInt();
        	x[l].position=horizon[i].xright;
        	x[l].belong=i;
        	x[l].LorR=1;
        	l++;
        	horizon[i].y=s.nextInt();
        }
        for(int j=0;j<numOfV;j++)
        {
        	vertic[j]=new vert();
        	vertic[j].ydown=s.nextInt();
        	vertic[j].yup=s.nextInt();
        	vertic[j].x=s.nextInt();
        	x[l]=new X();
        	x[l].position=vertic[j].x;
        	x[l].belong=numOfH+j;
        	x[l].LorR=3;
        	l++;
        }
        sort(0,2*numOfH+numOfV-1);         //用归并排序进行排序
//        for(int i=0;i<2*numOfH+numOfV;i++)
//        	System.out.println(x[i].position+" "+x[i].belong);
        for(int i=0;i<2*numOfH+numOfV;i++)
        {
        	if(x[i].belong<numOfH&&x[i].LorR==1)   //若为水平线且为右节点则从候选集中删除
        		tree.remove(new Integer(x[i].belong));
        	else if(x[i].belong<numOfH&&x[i].LorR==0) //水平线且左节点则加入候选集
        		tree.add(new Integer(x[i].belong));
        	else              //竖直线
        	{
        		Iterator iter= tree.iterator();
        		while(iter.hasNext())
        		{
        			int j=(Integer) iter.next();
        				if(horizon[j].y>=vertic[x[i].belong-numOfH].ydown&&horizon[j].y<=vertic[x[i].belong-numOfH].yup)
        				{
        					total_num++;                               //计数
        					al.add(new cord(x[i].position,horizon[j].y)); //添加
//        					System.out.println(x[i].position+","+horizon[j].y);
        				}
//        			  System.out.println(horizon[j].xleft+" "+horizon[j].xright+" "+horizon[j].y+" vertical: "+vertic[x[i].belong-numOfH].yup+" "
//        					  +vertic[x[i].belong-numOfH].ydown+" "+vertic[x[i].belong-numOfH].x);
        		}
        		 System.out.println();
        	}
        }
	}
	 public  void sort(int a,int b)
	 {
         if(a==b);
			 
		 else
		 {
		 sort(a,(a+b)/2);
		 sort((a+b)/2+1,b);
		 int i=a;
		 int middle=(a+b)/2;
		 int j=middle+1;
		 int k=-1;
		 X[] temp=new X[b-a+1];
		 while(i<=middle&&j<=b)
		 {
			 k++;
			 if(x[i].position<x[j].position)
			 {
				 temp[k]=x[i];
			     i++;
			 }
			 else
				 if(x[i].position==x[j].position&&x[i].belong>=numOfH&&x[j].belong<numOfH&&x[j].LorR==1)
				 {
					 temp[k]=x[i];
					 i++;
				 }
				 else
					 if(x[i].position==x[j].position&&x[i].belong>=numOfH&&x[j].belong<numOfH&&x[j].LorR==0)
					 {
						 temp[k]=x[j];
						 j++;
					 }
				 else
					 if(x[i].position==x[j].position&&x[i].belong<numOfH&&x[j].belong>=numOfH&&x[i].LorR==0)
			 {
				 temp[k]=x[i];
				 i++;
			 }
					 else
						 if(x[i].position==x[j].position&&x[i].belong<numOfH&&x[j].belong>=numOfH&&x[i].LorR==1)
				 {
					 temp[k]=x[j];
					 j++;
				 }
					 else
					 {
						 temp[k]=x[j];
						 j++;
					 }
			 
		 }
		 k++;
		 if(i<=middle)
		 {
			 for(;k<=b-a;k++)
			 {
				 temp[k]=x[i];
				 i++;
			 }
		 }
		 if(j<=b)
		 {
			 for(;k<=b-a;k++)
			 {
				 temp[k]=x[j];
				 j++;
			 }
		 }
		 for(int t=a;t<=b;t++)
		 {
			 x[t]=temp[t-a];
		 }
		 }
	 }
	public void change(X a, X b)
	{
	X temp;
	temp=a;
	a=b;
	b=temp;
	}

}
class horiz{
	int xleft;
	int xright;
	int y;
}
class vert{
	int x;
	int yup;
	int ydown;
	
}
class X{
	int position;
	int LorR;
	int belong;
	
}
class cord{
	int x;
	int y;
	cord(int x,int y)
	{
		this.x=x;
		this.y=y;
	}
}