本文共 1868 字，大约阅读时间需要 6 分钟。

几何问题中的分治法

1.最近对问题

问题描述:

设p1=(x1,y1),p2=(x2,y2),…,pn=(xn,yn)一共n个点构成点集S，最近点对问题就是找出集合中距离最近的两个点，严格来说最近点对可能多于一个，但我们简单起见只找出一对即可。

算法思路:

(1)划分:将集合S分成两个子集S1和S2，根据平衡子问题原则，每个子集中大约有n/2个点,设集合S的最近点对是pi与pj(1<=i,j<=n),则会出现三种情况。

①pi在S1中，pj在S1中

②pi在S2中，pj在S2中

③pi在S1中，pj在S2中

(2)划分①②可以递归，划分③比较麻烦

(3)合并，比较三种情况取最小值返回即可

下面讨论情况③:

代码:

import org.junit.Test;public class AVL {
       //最近点对问题   @Test    public  void Test()    {
           Point p1 = new Point();        p1.setX(0.1);        p1.setY(0.2);        Point p2 = new Point();        p2.setX(0.4);        p2.setY(0.3);        Point p3 = new Point();        p3.setX(0.2);        p3.setY(0.1);        Point points[]=new Point[]{
   p1,p2,p3};        Point[] points_help = new Point[points.length];        for(int i=0;i
   
    =temp.x)               j--;           points[i]=points[j];           while(i
    
     <=temp.x)               i++;           points[j]=points[i];       }       else{
              while(i
     
      =temp.y)                   j--;               points[i]=points[j];               while(i
      
       <=temp.y)                   i++;               points[j]=points[i];           }       }       points[i]=temp;       return i;    }    void  sort(Point points[],int left,int right,int condtion){
          if(left
       
        =left;i--){
               if(points[mid].x-points[i].x<=d)                points_help[index++]=points[i];            else                break;        }        for(int j=mid+1;j<=right;j++){
               if(points[j].x-points[mid].x<=d){
                   points_help[index++]=points[j];            }            else                break;        }        //现在已经收集好了我们将其按照y轴的方向从小到大排序        sort(points_help,0,index-1,1);        for(int i=0;i
       
      
     
    
   

输出:

2.凸包问题

问题描述：设p1=(x1,y1),p2=(x2,y2),…,pn=(xn,yn)是平面上n个点构成的集合S,凸包问题是为集合S构造最小凸多边形。

转载地址：http://rplzi.baihongyu.com/