• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

旋转卡壳算法

开发技术 开发技术 2周前 (04-30) 4次浏览

用途:求凸包的直径、宽度,两个不相交凸包间的最大距离和最小距离等
旋转卡壳,顾名思义,用某种东西去卡凸多边形,去旋转某种东西,得到想要的信息.这里使用平行线去进行旋转卡壳.
有两种卡壳的情况:

算法

1.按照两个点去卡.(A)
2.按照一条边和边所对应的最远点去卡.(B)
这里使用第二种方法.
现在根据图片中的多边形描述过程.
在确定好凸多边形后,例如ABCDEFG点构成的多边形.

先让AB作为一条边,先确立距离AB最远的点.
因为AB和其它点构成的三角形的面积会由小变大再变小,所以在遍历其它点的时候,只需要找到构成的最大三角形面积的点,就是最远点了.这里是点E.比较AE和BE的距离,最大为当前边扫描出的两点之间最大距离

第二次旋转

旋转AB边的直线到BC.在直线旋转的过程中,最远点也会按照相同的方向去移动.因为第一次已经找到了最远点E,所以这次可以直接从E开始向后找最大的点.这里是F,比较BF和CF,最大的为当前边扫描出的两点之间最大距离
…….
这样可以找到所有的最大点.在这些点和对边构成的距离中,最大的就是多边形的直径.
同样可以计算最小距离确认多边形的宽度.

以▲ABC为例三角形面积S=x = |AB||AC|*sin<AB,AC>.

题目:选美大赛—计算多边形的直径
(有错误……)

import java.util.*;

public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
List<int[]> point = new ArrayList<int[]>();
int min = 0;
for(int i = 0;i<N;i++){ int[] s = new int[]{sc.nextInt(),sc.nextInt()}; point.add(s); if(point.get(min)[0]>s[0]){
min = i;
}
else if(point.get(min)[0] == s[0] && point.get(min)[1]>s[1]){
min = i;
}
}
final int[] compareP = new int[]{point.get(min)[0],point.get(min)[1]};
//点排序
Collections.sort(point, new Comparator<int[]>() {
public int compare(int[] ints, int[] t1) {
int[] vec1 = new int[]{ints[0]-compareP[0],ints[1]-compareP[1]};
int[] vec2 = new int[]{t1[0]-compareP[0],t1[1]-compareP[1]};
if(vec1[0]vec2[1]-vec1[1]vec2[0]>0){
return -1;
}
else if(vec1[0]vec2[1]-vec1[1]vec2[0]==0){
if(Math.pow(vec1[0],2)+Math.pow(vec1[1],2)-Math.pow(vec2[0],2)-Math.pow(vec2[1],2)>0){
return 1;
}
else{
return -1;
}
}
return 1;
}
});
//确定凸包
Stack stack = new Stack();
stack.push(0);
stack.push(1);
stack.push(2);

for(int i = 3;i<point.size();i++){ while(true){ int compareIndex = stack.pop(); int[] point0 = point.get(compareIndex); int[] point1 = point.get(stack.peek()); int[] point2 = point.get(i); int sinRes = sinZeroCompare(point1,point0,point2); if(sinRes>0){
stack.push(compareIndex);
break;
}
}
stack.push(i);
}

List<int[]> pointSideList = new ArrayList<int[]>();
while (!stack.isEmpty()){
pointSideList.add(point.get(stack.pop()));
}
int tempSquare = -1;
int pointCnt = pointSideList.size();
int compareStartIdx=2;
pointSideList.add(pointSideList.get(0));
double maxDist = -1;
for(int i = 0;i<pointCnt;i++){
int currentMaxSquare = -1;
double currentMaxDist = 0;
int compareIdx = 0;
for(int j = compareStartIdx;j<pointCnt*2;j++){ compareIdx = j; if(compareIdx>=pointCnt){
compareIdx = j%pointCnt;
}
tempSquare = getSquare(pointSideList.get(i),pointSideList.get(i+1),pointSideList.get(compareIdx));
if(currentMaxSquare>tempSquare){
break;
}
else if(currentMaxSquare<tempSquare){ currentMaxSquare = tempSquare; currentMaxDist = Math.max(getDistance(pointSideList.get(i),pointSideList.get(compareIdx)),getDistance(pointSideList.get(i+1),pointSideList.get(compareIdx))); } else{ double tempDist = Math.max(getDistance(pointSideList.get(i),pointSideList.get(compareIdx)),getDistance(pointSideList.get(i+1),pointSideList.get(compareIdx))); if(tempDist>currentMaxDist){
currentMaxDist = tempDist;
currentMaxSquare = tempSquare;
break;
}
}
}
compareStartIdx = compareIdx+pointCnt-1;
maxDist = Math.max(maxDist,currentMaxDist);
}

System.out.println((int)maxDist);
}

private static double getDistance(int[] p1,int[] p2){
return Math.pow(p1[0]-p2[0],2)+Math.pow(p1[1]-p2[1],2);
}
//<p0,p1>,<p0,p2> private static int getSquare(int[] p0,int[] p1,int[] p2){
int[] v1 = new int[]{p1[0]-p0[0],p1[1]-p0[1]};
int[] v2 = new int[]{p2[0]-p0[0],p2[1]-p0[1]};
return Math.abs(v1[0]v2[1]-v1[1]v2[0]);
}

private static int sinZeroCompare(int[] p0,int[] p1,int[] p2){
int[] p01 = new int[]{p1[0]-p0[0],p1[1]-p0[1]};
int[] p12 = new int[]{p2[0]-p0[0],p2[1]-p0[1]};
return p01[0]p12[1]-p01[1]p12[0]>0?1:-1;
}
}


程序员灯塔
转载请注明原文链接:旋转卡壳算法
喜欢 (0)