计算几何中与多边形相关的基本问题 |
您所在的位置:网站首页 › double计算 › 计算几何中与多边形相关的基本问题 |
摘要: 本文介绍计算几何中与多边形相关的基本问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,在文章 向量的实现 中,我们实现了一个二维向量的代码模板,主要是 Vector2 这个类。 此后基于二维向量的代码模板,我们解决了计算几何中关于点、直线和线段、极角中的常见问题,以及力扣中的几个相关题目。 本文我们介绍计算几何中关于多边形的常见问题,代码依然使用 Vector2。然后解决三个力扣中的题目:469、593、836。主要涉及以下内容: 凸多边形判定凸多边形点集排序简单多边形的面积简单多边形内部外部判断两个简单多边形相交1. 凸多边形判定简单多边形:边不相交的多边形凸多边形:每个内角都在 180 度以内题目:469. 凸多边形给定 X-Y 平面上的一组点 points ,其中 points[i] = [xi, yi] 。这些点按顺序连成一个多边形。 如果该多边形为 凸 多边形(凸多边形的定义)则返回 true ,否则返回 false 。 你可以假设由给定点构成的多边形总是一个 简单的多边形(简单多边形的定义)。换句话说,我们要保证每个顶点处恰好是两条边的汇合点,并且这些边 互不相交 。 提示: 3 m; int ans = 0; for(int i = 0; i < m; ++i) { int x, y; cin >> x >> y; Vector2 q(x, y); bool flag = false; for(int i = 0; i < n; ++i) { int j = (i + 1) % n; if(fabs(ccw(p[i], p[j], q)) < EPS) { if((p[j] - p[i]).norm() > (p[j] - q).norm()) { flag = true; continue; } } } if(flag) continue; if(isInside(p, q)) ++ans; } cout |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |