精华内容
下载资源
问答
  • 特殊情况:多边形中存在与点的射线重合的边,需要判断该条边前后两条边是否相对于该边是同一侧,若是同一侧,则认为点射线与该边没有交点,如果不同侧则认为射线与该边有一个交点。 原理:该算法原理是二维图形内部...

    思路:做从点出发垂直于x轴的向下的射线,射线于多边形的交点个数为奇数则在内部,偶数则在外部

    特殊情况:多边形中存在与点的射线重合的边,需要判断该条边前后两条边是否相对于该边是同一侧,若是同一侧,则认为点射线与该边没有交点,如果不同侧则认为射线与该边有一个交点。

    原理:该算法原理是二维图形内部的点向任意方向的射线总是穿过二维图形奇数次。

    展开全文
  • 思路:考虑任意两点,如果a和b之间船不能通过,则连一条边,则问题转化为判断是否在多边形中。先进行坐标变换,将船变到原点,以从起点到每个点的有向角作为状态,每条边的边权这条边对有向角的改变量,那么点在...

    大致题意:在二维平面上,给一些圆形岛屿的坐标和半径,以及圆形船的位置和半径,问能否划到无穷远的地方去

    思路:考虑任意两点,如果a和b之间船不能通过,则连一条边,则问题转化为判断点是否在多边形中。先进行坐标变换,将船变到原点,以从起点到每个点的有向角作为状态,每条边的边权为这条边对有向角的改变量,那么点在多边形内相当于存在负权环,从每个点出发跑一下SPFA判负环即可。

     

    #pragma comment(linker, "/STACK:10240000")
    #include <map>
    #include <set>
    #include <cmath>
    #include <ctime>
    #include <deque>
    #include <queue>
    #include <stack>
    #include <vector>
    #include <cstdio>
    #include <string>
    #include <cstdlib>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    #define X                   first
    #define Y                   second
    #define pb                  push_back
    #define mp                  make_pair
    #define all(a)              (a).begin(), (a).end()
    #define fillchar(a, x)      memset(a, x, sizeof(a))
    #define fillarray(a, b)     memcpy(a, b, sizeof(a))
    
    typedef long long ll;
    typedef pair<int, int> pii;
    typedef unsigned long long ull;
    
    #ifndef ONLINE_JUDGE
    namespace Debug {
    void RI(vector<int>&a,int n){a.resize(n);for(int i=0;i<n;i++)scanf("%d",&a[i]);}
    void RI(){}void RI(int&X){scanf("%d",&X);}template<typename...R>
    void RI(int&f,R&...r){RI(f);RI(r...);}void RI(int*p,int*q){int d=p<q?1:-1;
    while(p!=q){scanf("%d",p);p+=d;}}void print(){cout<<endl;}template<typename T>
    void print(const T t){cout<<t<<endl;}template<typename F,typename...R>
    void print(const F f,const R...r){cout<<f<<", ";print(r...);}template<typename T>
    void print(T*p, T*q){int d=p<q?1:-1;while(p!=q){cout<<*p<<", ";p+=d;}cout<<endl;}
    }
    #endif // ONLINE_JUDGE
    
    template<typename T>bool umax(T&a, const T&b){return b<=a?false:(a=b,true);}
    template<typename T>bool umin(T&a, const T&b){return b>=a?false:(a=b,true);}
    
    const double PI = acos(-1.0);
    const int INF = 0x3f3f3f3f;
    const double EPS = 1e-8;
    
    /* -------------------------------------------------------------------------------- */
    
    const int maxn = 3e2 + 7;
    
    int dcmp(double x) {
        if (fabs(x) < EPS) return 0;
        return x > 0? 1 : - 1;
    }
    
    struct Circle {
        double x, y, r;
        Circle(double x, double y, double r) {
            this->x = x;
            this->y = y;
            this->r = r;
        }
        void read() {
            scanf("%lf%lf%lf", &x, &y, &r);
        }
        Circle() {}
    };
    Circle p[maxn];
    
    double e[maxn][maxn], d[maxn];
    bool vis[maxn];
    int n, cnt[maxn];
    
    double dist(double x1, double y1, double x2, double y2) {
        return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
    }
    
    bool relax(double u, double w, double &v) {
        if (dcmp(v - u - w) > 0) {
            v = u + w;
            return true;
        }
        return false;
    }
    
    bool spfa(int s) {
        queue<int> Q;
        Q.push(s);
        fillchar(vis, 0);
        for (int i = 0; i < n; i ++) {
            d[i] = INF;
        }
        fillchar(cnt, 0);
        d[s] = 0;
        while (!Q.empty()) {
            int H = Q.front(); Q.pop();
            vis[H] = false;
            for (int i = 0; i < n; i ++) {
                if (e[H][i] < INF) {
                    if (relax(d[H], e[H][i], d[i]) && !vis[i]) {
                        if (cnt[i] >= n) return true;
                        Q.push(i);
                        vis[i] = true;
                        cnt[i] ++;
                    }
                }
            }
        }
        return false;
    }
    
    void work() {
        for (int i = 0; i < n; i ++) {
            if (spfa(i)) {
                puts("NO");
                return ;
            }
        }
        puts("YES");
    }
    
    double calcangle(int i, int j) {
        Circle a = p[i], b = p[j];
        double angle = acos((a.x * b.x + a.y * b.y) / dist(a.x, a.y, 0, 0) / dist(b.x, b.y, 0, 0));
        if (dcmp(a.x * b.y - a.y * b.x) <= 0) return angle;
        return - angle;
    }
    
    int main() {
    #ifndef ONLINE_JUDGE
        freopen("in.txt", "r", stdin);
        //freopen("out.txt", "w", stdout);
    #endif // ONLINE_JUDGE
        while (cin >> n) {
            for (int i = 0; i < n; i ++) {
                p[i].read();
            }
            Circle me;
            me.read();
            for (int i = 0; i < n; i ++) {
                p[i].x -= me.x;
                p[i].y -= me.y;
            }
            for (int i = 0; i < n; i ++) {
                for (int j = 0; j < n; j ++) {
                    e[i][j] = INF + 1;
                }
            }
            for (int i = 0; i < n; i ++) {
                for (int j = i + 1; j < n; j ++) {
                    double buf = dist(p[i].x, p[i].y, p[j].x, p[j].y) - p[i].r - p[j].r;
                    if (dcmp(buf - me.r * 2) < 0) {
                        e[i][j] = calcangle(i, j);
                        e[j][i] = - e[i][j];
                        //Debug::print(i, j, e[i][j]);
                    }
                }
            }
            work();
        }
        return 0;
    }
    

    转载于:https://www.cnblogs.com/jklongint/p/4759186.html

    展开全文
  • 一个简单的例子:在平面坐标里有四个圆分别以(2,2),(2,-2),(-2,-2),(-2,2)圆心,现取平面内任意一点,问其是否落于圆内。 算法思路:四个圆关于原点中心对称,可以对所求点取绝对值,放在第一象限内...

    判断图形相交
    一个简单的例子:在平面坐标里有四个圆分别以(2,2),(2,-2),(-2,-2),(-2,2)为圆心,现取平面内任意一点,问其是否落于圆内。
    算法思路:四个圆关于原点中心对称,可以对所求点取绝对值,放在第一象限内求解,若所求点与圆心距离小于半径,则其落于圆上。
    伪代码:
    double a,b;
    scanf("%d%d",&a,&b);
    a=fabs(a);
    b=fabs(b);
    if((a-2)(a-2)+(b-2)(b-2)<=1)
    printf(”所取的点落于圆上”);
    else
    printf(“所取的点落于圆外”);

    如何判断两个矩形是否相交可以采取类似的思想,用easyx所做的矩形有四个参数,分别代表矩形左上角和右下角的点。当两矩形相交(相切也算在内)则两个矩形x轴两点最大距离之差小于等于其长度之和,同理y轴坐标之差也小于等于其长度之和。
    例如:
    rectangle(a,b,c,d);
    rectangle(w,x,y,z);
    if(fab(c-a)+fab(y-w)<=fab(y-a)&&fab(d-b)+fab(z-x)<=fab(z-b))
    printf(”两矩形相交”);

    展开全文
  • 031 判断字符串是否回文 032 通讯录的输入输出 033 扑克牌的结构表示 034 用“结构”统计学生成绩 035 报数游戏 036 模拟社会关系 037 统计文件的字符数 038 同时显示两个文件的内容 039 简单的文本编辑器 ...
  • 031 判断字符串是否回文 032 通讯录的输入输出 033 扑克牌的结构表示 034 用“结构”统计学生成绩 035 报数游戏 036 模拟社会关系 037 统计文件的字符数 038 同时显示两个文件的内容 039 简单的文本编辑器 ...
  • 若穿过阴影体,深度缓存加一,穿出减一,最后通过模板测试判断是否为阴影。 阴影贴图 最常用的是阴影贴图。我们首先以光源位置进行一次深度记录,记录的内容是光源离最近表面的距离。并将改深度缓存存储到纹理空间。...

    阴影

    投影阴影
    我们我们根据点光源和多边形进行相似变换,通过变换矩阵实现,前提是我们只能投影到一个平面上。比如草原上的人的影子,马的影子,只要是影子都投影到草原上可以用到。

    阴影体
    首先要计算出处于阴影的阴影空间。然后判断我们看到的点是否在其中,若在,则减少其光照亮度。若穿过阴影体,深度缓存加一,穿出减一,最后通过模板测试判断是否为阴影。

    阴影贴图
    最常用的是阴影贴图。我们首先以光源位置进行一次深度记录,记录的内容是光源离最近表面的距离。并将改深度缓存存储到纹理空间。当我们第二次实际渲染的时候,投影之后将点映射到纹理空间,若大于纹理空间的值,说明是阴影。即从光源角度看,到该点的射线中有其它表面遮挡,因为纹理中记录射线方向有更近的点。

    实现过程首先有LookAt矩阵,将视点放到光源。记录深度并放到纹理中,并且关闭颜色计算。第二次正常计算,投影后比较深度,我们可以减少漫反射和镜面反射来实现阴影。

    同时存在着问题,因为第二次映射到纹理空间的时候,由于取舍可能会造成误差。我们会取错纹理中的点,或者认为相同的点,但是第二次的值比第一次的大。比如第一次是5.01,记录成了5,但是第二次会认为最近的是5,而将表面设置为阴影,即为阴影痤疮。

    可以将第一次的值设置的大一点,在第二次还原回去,此时又会产生纹理空间的值超过0和1,会出现重复绘制的情况。那么我们设置为舍去超出范围来解决。

    此外还有阴影柔和,目的是为了阴影去掉锯齿,并且模拟离阴影近的更暗一些,远的阴影淡一些的效果。我们通过采样平均来进行阴影柔和。但是在片段着色器中我们不知道其它点的情况,但是我们可以通过该点获取纹理中相邻的情况。

    展开全文
  • Luogu P4196 半平面交(S&I算法) 求多条直线左侧包围图形 逆时针确定每条直线...判断队首和(队首+1)的交点是否在新直线的右侧 先判交点个数,>2>2>2才会有交,否则0 叉积求面积 #include&l...
  • 《计算机图形学(OpenGL版)第3版》是一本国外很有影响的教材,许多国外著名大学所采用。《计算机图形学(OpenGL版)第3版》通过最能代表技术发展状况的示例综合介绍了计算机图形学方面的原则和技巧,《计算机图形学...
  • Matplotlib入门05-直方

    2020-04-13 23:48:34
    直方 官方文档 1.直方 在统计数据时,按照频数分布表,在平面直角坐标系中,横轴标出每个组的端点,纵轴...作直方的目的就是通过观察的形状,判断生产过程是否稳定,预测生产过程的质量。 2.绘制简单图形 ...
  • 一、应用场景:地图应用中判断一个位置是否在一个区域内。我曾经应用在百度地图上,代码js实现。据我了解,目前百度地图api已经提供该功能。 二、概要: 1、行政区划边界是多边形; 2、多边形分为凸多边形和凹...
  • 1. 引例(如何描述动点的轨迹?) ...3. 竖直判断法判断图形是否为函数图形 4. 曲线的参数方程 5. 直角坐标方程化为参数方程 6. 摆线 7. 常见曲线的参数方程 ...
  • 031 判断字符串是否回文 032 通讯录的输入输出 033 扑克牌的结构表示 034 用“结构”统计学生成绩 035 报数游戏 036 模拟社会关系 037 统计文件的字符数 038 同时显示两个文件的内容 039 简单的文本编辑器 ...
  • 透视学的应用(六)

    2016-12-28 18:34:46
    4、透视的类型,日常生活中的透视 ...我们判断几何图形是否具有透视条件,最基本的验证就是它是否存在灭点(消失点)。 可见,数学立体几何图形并没有灭点,因为在平面BCED中,DE和BC两条平行线,BD和CE亦是互
  • 随机算法学习笔记

    2019-01-24 17:08:00
    随机算法 数值概率算法 数值概率算法是一类用于数值问题求解的算法。 例1 计算面积 给定平面上的一个封闭图形...随机在 \(x,y\) 范围的正方形内取若干个点,判断是否图形内,计算落在该图形内概率 \(P\),面积 \...
  • Sicily 1094 Cude解题报告

    2012-04-28 21:05:56
    立体图形的相关问题可以转化为平面图形来研究,但是我的空间想象能力较差,只有通过探索总结出规律才能解决问题。 一、立方体平面展开中的特点 1、当我们从立方体的某顶点出发,最多只能观察到三个面,这三个面...
  • 这题要用到图论中的欧拉定理,即V−E+F=2V-E+F=2V−E+F=2,其中VVV点数,EEE边数,FFF面数(包括整个图形以外的部分),可以用归纳法证明,对任意连通平面图成立。 那么在这题里把黑格看成点,可以通过判断...
  • 计算几何

    2021-04-13 14:29:42
    判断2条线段是否相交 求叉积 计算几何经典算法 求凸包 求最近点对 判断是否在多边形内等等 几何题的类型 纯粹的计算求解题 比如求直线的斜率时,直线的斜率无穷大,求2条直线的交点时,2直线平行,等等。 解...
  • [Jzoj] 1956. 矩形

    2019-11-05 15:39:52
    现我们定义满足如下性质的图形为一个块:  每一个矩形都是一个块;  如果两个块有一段公共的部分,那么这两个块就会形成一个新的块,否则这两个块就是不同的。 题目解析 这题就是判断矩形是否联通,用到并查集...
  • 判断集合C和T的交集是否非空。 输入格式: (第一行)正整数N,代表接下来有N组测试数据。 (接下来的N行,每一行格式是:)r x0 y0 x1 y1 x2 y2 x3 y3 (解释:r圆半径,(x0, y0)圆心坐标...
  • 曲线数字化软件windig

    2013-07-28 18:03:07
    中红色方框部分显示windig软件系统的坐标值,品红色方框标识放大工具,利用放大工具,可以判断鼠标是否和曲线(坐标轴)重合得完好。 第三步:定义截取数据的真实数据平面。在windig菜单栏中点“Scale”,然后再点...
  • 200个经典C程序【源码】

    千次下载 热门讨论 2013-08-08 10:48:40
    031 判断字符串是否回文 032 通讯录的输入输出 033 扑克牌的结构表示 034 用“结构”统计学生成绩 035 报数游戏 036 模拟社会关系 037 统计文件的字符数 038 同时显示两个文件的内容 039 简单的文本编辑器 ...
  • 031 判断字符串是否回文 032 通讯录的输入输出 033 扑克牌的结构表示 034 用“结构”统计学生成绩 035 报数游戏 036 模拟社会关系 037 统计文件的字符数 038 同时显示两个文件的内容 039 简单的文本编辑器 040 文件...
  • 200个C程序.rar

    2021-05-06 12:46:56
    031 判断字符串是否回文 032 通讯录的输入输出 033 扑克牌的结构表示 034 用“结构”统计学生成绩 035 报数游戏 036 模拟社会关系 037 统计文件的字符数 038 同时显示两个文件的内容 039 简单的文本编辑器 ...
  • 如果点到平面的距离0,则点在平面上,否则不在平面上。  直线是否平面上  平面和直线的交点 通过调用其他功能可以实现的功能:  平面的法向量平行于直线,则平面和直线垂直  平面的法向量垂直于直线,则...
  • 16.3 判断用户输入是否为中文 16.4 验证列表框中的值是否重复 16.5 检测输入框的统一方法 16.6 Email的验证 16.7 不使用正则验证IP地址 16.8 IP地址输入框 16.9 判断变量是否已经定义 16.10 判断方法是否已经定义 ...
  • 031 判断字符串是否回文 032 通讯录的输入输出 033 扑克牌的结构表示 034 用“结构”统计学生成绩 035 报数游戏 036 模拟社会关系 037 统计文件的字符数 038 同时显示两个文件的内容 039 简单的文本编辑器 ...
  • 16.3 判断用户输入是否为中文 16.4 验证列表框中的值是否重复 16.5 检测输入框的统一方法 16.6 Email的验证 16.7 不使用正则验证IP地址 16.8 IP地址输入框 16.9 判断变量是否已经定义 16.10 判断方法是否已经定义 ...
  • 在进行裁剪时,书上只是提到w分量大于零(《计算机图形学(opengl版)》第三版,321页最上,“aw只取正值“)使用z+w(近裁剪面)经行测试,判断是否需要裁剪。但是如果w分量是负值,我使用相同方法计算直线和裁剪...

空空如也

空空如也

1 2 3 4
收藏数 68
精华内容 27
关键字:

判断图形是否为平面图