蛮力法-最近对和凸包问题

3.3.1 最近对问题

问题描述：要求找出一个包含n个点的集合中距离最近的两个点。原本思想是我们应该去比较两点之间的欧几里得距离，而实际上，我们可以去比较它们的平方，这样，我们就可以避免对平方根的近似求解。

代码实现：

/**
     * 蛮力法解决最近对问题
     * @author xiaofeig
     * @since 2015.9.16
     * @param points 对象点集
     * @return 返回包含最小对的下标
     * */
    public static int[] bruteForceClosestPoints(Point[] points){
        int dmin=(points[0].x-points[1].x)*(points[0].x-points[1].x)+(points[0].y-points[1].y)*(points[0].y-points[1].y);
        int index1=0;
        int index2=1;
        for(int i=0;i<points.length-1;i++){
            for(int j=i+1;j<points.length;j++){
                int d=(points[i].x-points[j].x)*(points[i].x-points[j].x)+(points[i].y-points[j].y)*(points[i].y-points[j].y);
                if(d<dmin){
                    index1=i;
                    index2=j;
                    dmin=d;
                }
            }
        }
        return new int[]{index1,index2};
    }

算法分析：

该算法的基本操作是求平方，每次求距离的平方值时，都要进行进行两次该操作。该算法属于θ(n²)。

3.3.2 凸包问题

凸集合：对于平面上的一个点集合（有限或无限），以集合中任意两点为端点的线段都属于该集合。

凸包：包含点集合的最小凸集合。

定理：任意包含n>2个点（不共线）的集合的凸包是以该集合中的某些点为顶点的凸多边形。

多边形的顶点称为“极点”。

凸包问题就是为一个有n个点的集合构造凸包。

要解决这个问题，我们需考虑一些几何知识，若想构建凸包，我们就必须先找到极点，如果p1，p2为多边形的两个极点，这点集中的点必然是位于直线p₁p₂一侧或直线p₁p₂上的。所以在判断极点时，先要求出经过这两点的直线，设经过点p₁(x₁,y₁)，p₂(x₂,y₂)的直线为ax+by=c(a=y₂-y₁,b=x₁-x₂,c=x₁y₂-x₂y₁)，我们只需判断所有点集中的点是否全部满足ax+by<=c或ax+by>=c，若满足，则这两点为极点，若不满足，可以尝试其它点组合，直到遍历完所有两个点的组合。

代码实现：

/**
     * 蛮力法解决凸包问题
     * @author xiaofeig
     * @since 2015.9.16
     * @param points 所有点集
     * @return 返回有序的极点集合
     * */
    public static List<Point> bruteForceConvexHull(Point[] points){
        List<Point> list=new LinkedList<Point>();
        int i=0;
        while(i<points.length){
            int j=0;
            while(j<points.length){
                if(points[i].equals(points[j])){
                    j++;
                    continue;//过滤重合的点
                }
                int a=points[j].y-points[i].y;
                int b=points[i].x-points[j].x;
                int c=points[i].x*points[j].y-points[i].y*points[j].x;
                
                int count=0;//值的正负表示点在直线的哪一侧
                int k=0;
                while(k<points.length){
                    int result=a*points[k].x+b*points[k].y-c;
                    if(result!=0&&count==0){
                        count=result;
                    }
                    if(count*result<0){//判断是否存在点不在直线的同一侧
                        break;
                    }
                    k++;
                }
                if(k==points.length&&(!list.contains(points[j]))){//判断是否找到新的极点
                    if(!list.contains(points[i])){
                        list.add(points[i]);
                    }
                    list.add(points[j]);
                    i=j;//从新的极点开始，寻找下一个极点
                    break;
                }
                j++;
            }
            if(j==points.length)
                i++;
        }
        return list;
    }

算法分析：

它是属于θ(n³)，可能上面的代码效率比这要略高一点，因为我利用了新的极点去查找下一个极点，所以中间跳过了一部分迭代过程，其实按照这个思想还可以进一步优化，比如查找到最后一个极点时，就可以直接返回集合，但我一直没想到怎样比较好地判断当前找到的新极点是否是最后一个极点，因为可能存在一种情况，就是很多点都在一条直线上，虽然这些点可能不是极点，但满足上面算法的思想，这也可能是算法不太完整的地方。