typedef double typev;
const double eps = 1e-8;
const int N = 50005;
int sign(double d){
return d < -eps ? -1 : (d > eps);
}
struct point{
typev x, y;
point operator-(point d){
point dd;
dd.x = this->x - d.x;
dd.y = this->y - d.y;
return dd;
}
point operator+(point d){
point dd;
dd.x = this->x + d.x;
dd.y = this->y + d.y;
return dd;
}
void read(){ scanf("%lf%lf", &x, &y); }
}ps[N];
int n, cn;
double dist(point d1, point d2){
return sqrt(pow(d1.x - d2.x, 2.0) + pow(d1.y - d2.y, 2.0));
}
double dist2(point d1, point d2){
return pow(d1.x - d2.x, 2.0) + pow(d1.y - d2.y, 2.0);
}
bool cmp(point d1, point d2){
return d1.y < d2.y || (d1.y == d2.y && d1.x < d2.x);
}
//st1-->ed1叉乘st2-->ed2的值
typev xmul(point st1, point ed1, point st2, point ed2){
return (ed1.x - st1.x) * (ed2.y - st2.y) - (ed1.y - st1.y) * (ed2.x - st2.x);
}
typev dmul(point st1, point ed1, point st2, point ed2){
return (ed1.x - st1.x) * (ed2.x - st2.x) + (ed1.y - st1.y) * (ed2.y - st2.y);
}
//多边形类
struct poly{
static const int N = 50005; //点数的最大值
point ps[N+5]; //逆时针存储多边形的点,[0,pn-1]存储点
int pn; //点数
poly() { pn = 0; }
//加进一个点
void push(point tp){
ps[pn++] = tp;
}
//第k个位置
int trim(int k){
return (k+pn)%pn;
}
void clear(){ pn = 0; }
};
//返回含有n个点的点集ps的凸包
poly graham(point* ps, int n){
sort(ps, ps + n, cmp);
poly ans;
if(n <= 2){
for(int i = 0; i < n; i++){
ans.push(ps[i]);
}
return ans;
}
ans.push(ps[0]);
ans.push(ps[1]);
point* tps = ans.ps;
int top = -1;
tps[++top] = ps[0];
tps[++top] = ps[1];
for(int i = 2; i < n; i++){
while(top > 0 && xmul(tps[top - 1], tps[top], tps[top - 1], ps[i]) <= 0) top--;
tps[++top] = ps[i];
}
int tmp = top; //注意要赋值给tmp!
for(int i = n - 2; i >= 0; i--){
while(top > tmp && xmul(tps[top - 1], tps[top], tps[top - 1], ps[i]) <= 0) top--;
tps[++top] = ps[i];
}
ans.pn = top;
return ans;
}
//求点p到st->ed的垂足,列参数方程
point getRoot(point p, point st, point ed){
point ans;
double u=((ed.x-st.x)*(ed.x-st.x)+(ed.y-st.y)*(ed.y-st.y));
u = ((ed.x-st.x)*(ed.x-p.x)+(ed.y-st.y)*(ed.y-p.y))/u;
ans.x = u*st.x+(1-u)*ed.x;
ans.y = u*st.y+(1-u)*ed.y;
return ans;
}
//next为直线(st,ed)上的点,返回next沿(st,ed)右手垂直方向延伸l之后的点
point change(point st, point ed, point next, double l){
point dd;
dd.x = -(ed - st).y;
dd.y = (ed - st).x;
double len = sqrt(dd.x * dd.x + dd.y * dd.y);
dd.x /= len, dd.y /= len;
dd.x *= l, dd.y *= l;
dd = dd + next;
return dd;
}
//求含n个点的点集ps的最小面积矩形,并把结果放在ds(ds为一个长度是4的数组即可,ds中的点是逆时针的)中,并返回这个最小面积。
double getMinAreaRect(point* ps, int n, point* ds){
int cn, i;
double ans;
point* con;
poly tpoly = graham(ps, n);
con = tpoly.ps;
cn = tpoly.pn;
if(cn <= 2){
ds[0] = con[0]; ds[1] = con[1];
ds[2] = con[1]; ds[3] = con[0];
ans=0;
}else{
int l, r, u;
double tmp, len;
con[cn] = con[0];
ans = 1e40;
l = i = 0;
while(dmul(con[i], con[i+1], con[i], con[l])
>= dmul(con[i], con[i+1], con[i], con[(l-1+cn)%cn])){
l = (l-1+cn)%cn;
}
for(r=u=i = 0; i < cn; i++){
while(xmul(con[i], con[i+1], con[i], con[u])
<= xmul(con[i], con[i+1], con[i], con[(u+1)%cn])){
u = (u+1)%cn;
}
while(dmul(con[i], con[i+1], con[i], con[r])
<= dmul(con[i], con[i+1], con[i], con[(r+1)%cn])){
r = (r+1)%cn;
}
while(dmul(con[i], con[i+1], con[i], con[l])
>= dmul(con[i], con[i+1], con[i], con[(l+1)%cn])){
l = (l+1)%cn;
}
tmp = dmul(con[i], con[i+1], con[i], con[r]) - dmul(con[i], con[i+1], con[i], con[l]);
tmp *= xmul(con[i], con[i+1], con[i], con[u]);
tmp /= dist2(con[i], con[i+1]);
len = xmul(con[i], con[i+1], con[i], con[u])/dist(con[i], con[i+1]);
if(sign(tmp - ans) < 0){
ans = tmp;
ds[0] = getRoot(con[l], con[i], con[i+1]);
ds[1] = getRoot(con[r], con[i+1], con[i]);
ds[2] = change(con[i], con[i+1], ds[1], len);
ds[3] = change(con[i], con[i+1], ds[0], len);
}
}
}
return ans+eps;
}
分享到:
相关推荐
C# 求点集的最小包围矩形,供大家参考,具体内容如下 思路: 1、求点集的中心点 2、将点集绕矩形进行一系列角度的旋转,并求记录旋转点集的包围矩形的面积和旋转角度; 3、将面积最小的矩形绕点集中心点旋转回去。 ...
用户在交互输入若干个点之后,通过选择菜单,生成并显示它的最小包围圆
凸多边形最小面积四边形包围盒算法
求包含点集的最小圆的算法 求包含点集的最小圆的算法
求取点集得凸包算法, C/C++语言。
matlab计算目标最小外接矩形,主要利用minboundrect函数。
这个是使用matlab来计算二值图像中的前景区域的最小外界矩形,图像中只能够有一个前景区域,用于单目标跟踪最好
根据各点的位置,matlab实现点集最小圆覆盖问题。
A C ++和Java库来计算 (又名分钟圈,最小球体,最小包围球体等)上的点的集合。 该代码适用于任意维度的点。 它在低维度上运行速度非常快,在 10,000 维度下实际上是有效的。 实现是基于纸张的算法由卡斯帕·...
给定点集组成任意多边形,使用matlab求出包含所有点的最小外接圆。
# 计算点集最外面的矩形边界 # 获取contour的线段点 # 保留目标区域,其他区域为零 # 根据新边界,更新mask # 4周padding一定宽度 # Mask转为segmentations,黑色背景中找白色物体 # 计算点集最外面的矩形边界 # ...
Opencv中求点集的最小外结矩使用方法minAreaRect,求点集的最小外接圆使用方法minEnclosingCircle。 minAreaRect方法原型: RotatedRect minAreaRect( InputArray points ); 输入参数points是所要求最小外结矩的...
C++最小二乘拟合圆。(这是凑字数的。这是凑字数的。这是凑字数的。这是凑字数的。这是凑字数的。这是凑字数的。)
miniball.zip,点集的最小包围球点集的最小包围球的快速计算,在低维或中高维。
点集拓扑熊金城答案点集拓扑熊金城答案点集拓扑熊金城答案
为了进一步扩展S-点集及S-点集族性质,采用理论推演方法,由S-点集族的等价定义出发,引入S-点集族表述法、S-点集之间的相互关系,进一步讨论了S-点集族的8个性质,得到S-点集族的点集运算封闭性质,从而建立了点集族实际...
朱尧辰的这本《点集偏差引论》是关于点集偏差理论的导引,包括点集偏差的基本概念和主要性质、低偏差点集的构造、偏差上界和下界估计的常用方法、点集偏差的精确计算公式、点集离差的基本结果,以及点集偏差和离差在...
输入或随机生成一组平面无序点并构造该无序点集的最小生成树
这是我做的课课程设计中的矩形窗函数源程序,自己写的比较简单,希望对大家有用
朱尧辰的这本《点集偏差引论》是关于点集偏差理论的导引,包括点集偏差的基本概念和主要性质、低偏差点集的构造、偏差上界和下界估计的常用方法、点集偏差的精确计算公式、点集离差的基本结果,以及点集偏差和离差在...