求不规则图形外接圆的算法 (附：三角形外接圆计算公式) |
您所在的位置：网站首页 › cad如何求不规则图形面积和周长的公式 › 求不规则图形外接圆的算法 (附：三角形外接圆计算公式) |
求不规则图形外接圆的算法 (附：三角形外接圆计算公式)
|
算法一：（可靠性未知，建议算法二） 1. 在点集中任取1点A。 2. 遍历所有点找到距离最远的点B，记录最远距离S1。 3. 再以B为起点，找到距离最远的点C，记录S2； 4. 如果S2 > S1 ,则重复步骤3，直到 Si = Si+1 5. 以最后两个距离最长的点（以BC为例）做中垂线，BC中点为E，以BC为直径做圆，如果其他所有点的都在该圆内，则BC就是外接圆的直径，E为圆心；否则在圆之外的点集中距离E最远的点作为点A，重复步骤2； 4.结束 算法二：（建议） 寻找最近点对”是用到分治策略降低复杂度，而“寻找最远点对”可利用几何性质。注意到：对于平面上有n个点，这一对最远点必然存在于这n个点所构成的一个凸包上（证明略），那么可以排除大量点，如下图所示：
在得到凸包以后，可以只在顶点上面找最远点了。同样，如果不O(n^2)两两枚举，可以想象有两条平行线， “卡”住这个凸包，然后卡紧的情况下旋转一圈，肯定就能找到凸包直径，也就找到了最远的点对。或许这就是为啥叫“旋转卡壳法”。
总结起来，问题解决步骤为： 1、用Graham's Scanning求凸包 2、用Rotating Calipers求凸包直径，也就找到了最远点对。 该算法的平均复杂度为O(nlogn) 。最坏的情况下，如果这n个点本身就构成了一个凸包，时间复杂度为O(n^2)。 旋转卡壳可以用于求凸包的直径、宽度，两个不相交凸包间的最大距离和最小距离等。 补充 计算不规则图形上最远点对（距离最远的两点）代码： // 求最远点对 #include #include using namespace std; struct point { int x , y; }p[50005]; int top , stack[50005]; // 凸包的点存在于stack[]中 inline double dis(const point &a , const point &b) { return (a.x - b.x)*(a.x - b.x)+(a.y - b.y)*(a.y - b.y); } inline int max(int a , int b) { return a > b ? a : b; } inline int xmult(const point &p1 , const point &p2 , const point &p0) { //计算叉乘--线段旋转方向和对应的四边形的面积--返回(p1-p0)*(p2-p0)叉积 //if叉积为正--p0p1在p0p2的顺时针方向; if(x==0)共线 return (p1.x-p0.x)*(p2.y-p0.y) - (p1.y-p0.y)*(p2.x-p0.x); } int cmp(const void * a , const void * b) //逆时针排序 返回正数要交换 { struct point *p1 = (struct point *)a; struct point *p2 = (struct point *)b; int ans = xmult(*p1 , *p2 , p[0]); //向量叉乘 if(ans < 0) //p0p1线段在p0p2线段的上方，需要交换 return 1; else if(ans == 0 && ( (*p1).x >= (*p2).x)) //斜率相等时，距离近的点在先 return 1; else return -1; } void graham(int n) //形成凸包 { qsort(p+1 , n-1 , sizeof(point) , cmp); int i; stack[0] = 0 , stack[1] = 1; top = 1; for(i = 2 ; i < n ; ++i) { while(top > 0 && xmult( p[stack[top]] , p[i] , p[stack[top-1]]) = 0 ; --i) { while(top > temp && xmult(p[stack[top]] , p[i] , p[stack[top-1]]) xmult( p[stack[i+1]] , p[stack[q]] , p[stack[i]] ) ) q = (q+1)%(top); ans = max(ans , max( dis(p[stack[i]] , p[stack[q]]) , dis(p[stack[i+1]] , p[stack[q+1]]))); } return ans; } int main(void) { int i , n , leftdown; while(scanf("%d",&n) != EOF) { leftdown = 0; for(i = 0 ; i < n ; ++i) { scanf("%d %d",&p[i].x,&p[i].y); if(p[i].y < p[leftdown].y || (p[i].y == p[leftdown].y && p[i].x < p[leftdown].x)) //找到最左下角的点 leftdown = i; } swap(p[0] , p[leftdown]); graham(n); printf("%d\n",rotating_calipers()); } return 0; }附：任意三角形外接圆计算公式 已知三角形三个顶点坐标：A（x1,y1） B (x2,y2) C (x3,y3) 设圆心坐标：O（x，y） x=((y2-y1)*(y3*y3-y1*y1+x3*x3-x1*x1)-(y3-y1)*(y2*y2-y1*y1+x2*x2-x1*x1))/(2*(x3-x1)*(y2-y1)-2*((x2-x1)*(y3-y1))); y=((x2-x1)*(x3*x3-x1*x1+y3*y3-y1*y1)-(x3-x1)*(x2*x2-x1*x1+y2*y2-y1*y1))/(2*(y3-y1)*(x2-x1)-2*((y2-y1)*(x3-x1))); |
【本文地址】
今日新闻 |
推荐新闻 |