在好例子网,分享、交流、成长!
您当前所在位置:首页js 开发实例Google API → 计算几何——凸多边形判断+点在多边形内判断+求点到直线距离.docx

计算几何——凸多边形判断+点在多边形内判断+求点到直线距离.docx

Google API

下载此实例
  • 开发语言:js
  • 实例大小:0.02M
  • 下载次数:14
  • 浏览次数:435
  • 发布时间:2016-01-22
  • 实例类别:Google API
  • 发 布 人:hnfjj
  • 文件格式:.rar
  • 所需积分:3
 相关标签: c d

实例介绍

【实例简介】

题意就是给顶一个多边形的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;
}

标签: c d

实例下载地址

计算几何——凸多边形判断+点在多边形内判断+求点到直线距离.docx

不能下载?内容有错? 点击这里报错 + 投诉 + 提问

好例子网口号:伸出你的我的手 — 分享

相关文章

网友评论

发表评论

(您的评论需要经过审核才能显示)

查看所有0条评论>>

小贴士

感谢您为本站写下的评论,您的评论对其它用户来说具有重要的参考价值,所以请认真填写。

  • 类似“顶”、“沙发”之类没有营养的文字,对勤劳贡献的楼主来说是令人沮丧的反馈信息。
  • 相信您也不想看到一排文字/表情墙,所以请不要反馈意义不大的重复字符,也请尽量不要纯表情的回复。
  • 提问之前请再仔细看一遍楼主的说明,或许是您遗漏了。
  • 请勿到处挖坑绊人、招贴广告。既占空间让人厌烦,又没人会搭理,于人于己都无利。

关于好例子网

本站旨在为广大IT学习爱好者提供一个非营利性互相学习交流分享平台。本站所有资源都可以被免费获取学习研究。本站资源来自网友分享,对搜索内容的合法性不具有预见性、识别性、控制性,仅供学习研究,请务必在下载后24小时内给予删除,不得用于其他任何用途,否则后果自负。基于互联网的特殊性,平台无法对用户传输的作品、信息、内容的权属或合法性、安全性、合规性、真实性、科学性、完整权、有效性等进行实质审查;无论平台是否已进行审查,用户均应自行承担因其传输的作品、信息、内容而可能或已经产生的侵权或权属纠纷等法律责任。本站所有资源不代表本站的观点或立场,基于网友分享,根据中国法律《信息网络传播权保护条例》第二十二与二十三条之规定,若资源存在侵权或相关问题请联系本站客服人员,点此联系我们。关于更多版权及免责申明参见 版权及免责申明

;
报警