实例介绍
题意就是给顶一个多边形的n个点和一个钉子的半径与圆心左坐标:
1:判断多边形是否为凸多边形; 2:判断圆心是否在多边形内;3:判断圆的半径是否小于圆心到多边形的最短距离:
1:判断多边形是否为凸多边形,只要循环检查多边形任意三点形成的向量的叉积的方向相同即可,这里注意向量叉积方向的判断,右手螺旋定则;只要方向一致就可以了。
2:这一步根据黑书上说的有两种方法:
(1):环顾法,就是利用点集求角度,叉积求方向,然后求出角度后:
angle = 0 表明在在多边形外; angle = pi ||-pi在多边行的边上;angle = 2.0*pi || -2.0*Pi在多边形内;else angle 属于(0,360)的则在多边行的一个顶点上。
这样的判断凹凸多边形都适合;
(2):射线缩点法,还没实现:
(3):不过这里在判断点是否在多变内时多边行肯定已经是凸多边形了,所以就又引申了另外几种方法:a:就是想判断凸多边形一样,只要这个点在多边形内部,他的方向就不会改变;
b:可以求多边形面积(以原点为基础)和要判断的点为基础求面积(这里注意求绝对值啊),判断是否相等。
3:求距离就是先求出三角形的面积,然后利用s=低*高/2求高即可。
【实例截图】
【核心代码】
#include <cstdio> #include <cstring> #include <iostream> #include <cmath> #define maxn 1100 using namespace std; const double pi = acos(-1.0); struct point { double x,y; }p[maxn],cir; double r; int n; const double eps = 1e-8; int dblcmp(double x) { if (x > eps) return 1; else if (x < -eps) return -1; else return 0; } double det(double x1,double y1,double x2,double y2) { return x1*y2 - x2*y1; } double dotdet(double x1,double y1,double x2,double y2) { return x1*x2 y1*y2; } double cross(point a,point b,point c) { return det(b.x - a.x,b.y - a.y,c.x - a.x,c.y - a.y); } double getdis(point a,point b) { double x = a.x - b.x; double y = a.y - b.y; return sqrt(x*x y*y); } // 判断是否为凸多边形 bool isconvexpg() { int dir = 0; for (int i = 0; i <= n - 1; i) { int temp = dblcmp(cross(p[i],p[i 1],p[i 2])); if (!dir) dir = temp; if (dir*temp < 0) return false; } return true; } //利用点积求角度 double getangle(point a,point b,point c) { double dj = dotdet(b.x - a.x,b.y - a.y,c.x - a.x,c.y - a.y); double dis = getdis(a,b)*getdis(a,c); double tmp = dj/dis; return acos(tmp); } //判断是否在多边形内 bool IsIn() { int i; double angle = 0.0; for (i = 1; i <= n; i) { if (dblcmp(cross(cir,p[i],p[i 1])) >= 0) angle = getangle(cir,p[i],p[i 1]); else angle -= getangle(cir,p[i],p[i 1]); } //printf("angle == %lf\n",angle); if (dblcmp(angle) == 0) return false; else if (dblcmp(angle - pi) == 0 || dblcmp(angle pi) == 0) { if (dblcmp(r) == 0) return true; } else if (dblcmp(angle - 2.0*pi) == 0 || dblcmp(angle 2.0*pi) == 0) { return true; } else { if (dblcmp(r) == 0) return true; } return false; } //求高并判断与r的关系 bool IsR() { double ans = 0x7fffffff; for (int i = 1; i <= n - 1; i) { double temp = cross(cir,p[i],p[i 1]); if (temp < 0) temp = - temp; double d = getdis(p[i],p[i 1]); double tr = temp/d; if (dblcmp(ans - tr) > 0) ans = tr; } if (dblcmp(ans - r) >= 0) return true; else return false; } int main() { //freopen("d.txt","r",stdin); int i; while (~scanf("%d",&n)) { if (n < 3) break; scanf("%lf%lf%lf",&r,&cir.x,&cir.y); for (i = 1; i <= n; i) scanf("%lf%lf",&p[i].x,&p[i].y); p[0] = p[n]; p[n 1] = p[1]; if (!isconvexpg()) printf("HOLE IS ILL-FORMED\n"); else { bool flag1 = IsIn(); bool flag2 = IsR(); if (flag1 && flag2) printf("PEG WILL FIT\n"); else printf("PEG WILL NOT FIT\n"); } } return 0; } 这里判断圆心是否在多边形内的另外几种方法(只针对凸多边形) double getsum() { double s = 0; for (int i = 0; i <= n - 1; i) { s = fabs(cross(cir,p[i],p[i 1]));//注意这里的fabs,否则求出来的面积永远相等 } return s; } bool IsInP() { double s = 0; for (int i = 0; i <= n - 1; i) s = det(p[i].x,p[i].y,p[i 1].x,p[i 1].y); if (s < 0) s = - s; double temp = getsum(); //printf("%.3lf %.3lf\n",s*0.5,temp*0.5); if (dblcmp(s - temp) == 0) return true; else return false; } //这一种就是和判断凸多边形差不多了: bool IsInP() { int dir = 0; for (int i = 0; i <= n - 1; i) { int temp = dblcmp(cross(cir,p[i],p[i 1])); if (!dir) dir = temp; if (dir*temp < 0) return false; } return true; }
相关文章
小贴士
感谢您为本站写下的评论,您的评论对其它用户来说具有重要的参考价值,所以请认真填写。
- 类似“顶”、“沙发”之类没有营养的文字,对勤劳贡献的楼主来说是令人沮丧的反馈信息。
- 相信您也不想看到一排文字/表情墙,所以请不要反馈意义不大的重复字符,也请尽量不要纯表情的回复。
- 提问之前请再仔细看一遍楼主的说明,或许是您遗漏了。
- 请勿到处挖坑绊人、招贴广告。既占空间让人厌烦,又没人会搭理,于人于己都无利。
关于好例子网
本站旨在为广大IT学习爱好者提供一个非营利性互相学习交流分享平台。本站所有资源都可以被免费获取学习研究。本站资源来自网友分享,对搜索内容的合法性不具有预见性、识别性、控制性,仅供学习研究,请务必在下载后24小时内给予删除,不得用于其他任何用途,否则后果自负。基于互联网的特殊性,平台无法对用户传输的作品、信息、内容的权属或合法性、安全性、合规性、真实性、科学性、完整权、有效性等进行实质审查;无论平台是否已进行审查,用户均应自行承担因其传输的作品、信息、内容而可能或已经产生的侵权或权属纠纷等法律责任。本站所有资源不代表本站的观点或立场,基于网友分享,根据中国法律《信息网络传播权保护条例》第二十二与二十三条之规定,若资源存在侵权或相关问题请联系本站客服人员,点此联系我们。关于更多版权及免责申明参见 版权及免责申明
网友评论
我要评论