凸包问题（蛮力法）

蛮力法）"/>

凸包问题（蛮力法）

蛮力法求解凸包问题的基本思想：对于由n个点构成的集合S中的两个点Pi和Pj，当且仅当该集合中的其他点都位于穿过这两点的直线的同一边时（假定不存在三点同线的情况），它们的连线是该集合凸包边界的一部分。对每一对顶点都检验一遍后，满足条件的线段构成了该凸包的边界。

在平面上，穿过两个点（x1,y1）和（x2,y2）的直线是由下面的方程定义的：

            ax+by=c   （其中，a=y2-y1,b=x1-x2,c=x1y2-x2y1）

这样一条直线把平面分成了两个半平面，其中一个半平面中的点都满足ax+by>c，另一个半平面都满足ax+by<c，因此，为了检验这些点是否都位于这条直线的同一边，可以简单的把每个点代入方程ax+by=c，检验这些表达式的符号是否相同。当然，如果这时有ax+by=c，这说明第三个点和前面两点共线，这时可以重新审核可能的凸包边界，即这三点中靠两侧的点是可能的极点，而中间的点则不是。

public class hello {public static void main(String[] args) {// TODO Auto-generated method stubA a=new A();a.ConvexHull();}}
class Date{float x[]= {0,1,1,1,2};float y[]= {1,2,0,1,1};float flag[]= {0,0,0,0,0};
} 
class A{Date date=new Date();float a,b,c;int n=date.x.length;int i,j,k;void ConvexHull() {//System.out.println(n);for(i=0;i<n;i++) {for(j=i+1;j<n;j++) {a=date.y[j]-date.y[i];b=date.x[i]-date.x[j];c=date.x[i]*date.y[j]-date.y[i]*date.x[j];int sign1=0;int sign2=0;for(k=0;k<n;k++) {if( k==j  ||  k==i ) continue;if((a*date.x[k]+b*date.y[k])==c) {sign1++;sign2++;}if((a*date.x[k]+b*date.y[k])>c) {sign1++;}if((a*date.x[k]+b*date.y[k])<c) {sign2++;} }if( sign1==(n-2) || sign2==(n-2) ) {date.flag[i]=1;date.flag[j]=1;}sign1=0;sign2=0;}}for(i=0;i<n;i++) {if(date.flag[i]==1) {System.out.println(date.x[i]+" "+date.y[i]);}}}
}

结果：

0.0 1.0
1.0 2.0
1.0 0.0
2.0 1.0