计算几何初步
2022/1/19 6:06:37
本文主要是介绍计算几何初步,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
计算几何基础
1. 判断点是否在线段上
叉积必为 0 保证在延长线上,点积不大于 0 保证不会在线段的两侧.
int Onsegment(point tmp, point a, point b) { if(dcmp(cross(a - tmp, b - tmp)) == 0 && dcmp(dot(a - tmp, b - tmp)) <= 0) return 1; return 0; }
2. 判断两个线段是否有相交(不在端点处)
看 $\mathrm{(a,b)}$ 和 $\mathrm{(c,d)}$ 分别都在各自两侧.
// 前面是线段上,后面是不在线段上相交. int Line_Intersect(point a, point b, point c, point d) { double x1 = cross(b - a, c - a), y1 = cross(b - a, d - a); double x2 = cross(d - c, a - c), y2 = cross(d - c, b - c); if(!dcmp(x1) || !dcmp(x2) || !dcmp(y1) || !dcmp(y2)) { bool f1 = Onsegment(a, c, d); bool f2 = Onsegment(b, c, d); bool f3 = Onsegment(c, a, b); bool f4 = Onsegment(d, a, b); bool f = (f1 | f2 | f3 | f4); return f; } if(dcmp(x1) * dcmp(y1) < 0 && dcmp(x2) * dcmp(y2) < 0) return 1; return 0; }
3. 凸包
$\mathrm{Graham}$ 扫描法:
将 $\mathrm{y}$ 坐标最小的点作为基准给其他点按照角度逆时针排序.
加入新点的时候看之前加的边是否在新加的边的左侧,如果是则弹掉.
// b 在 a 的逆时针为正,夹角为 a 转到 b 的有向角度(sin) double cross(Vector a, Vector b) { return a.x * b.y - a.y * b.x; } int n ; point p[N], A[N]; bool cmp2(point i, point j) { int t = dcmp(cross(i - p[1], j - p[1])); if(t != 0) return t > 0; else { return dis(i, p[1]) < dis(j, p[1]); } } int main() { // setIO("input"); scanf("%d", &n); for(int i = 1; i <= n ; ++ i) { scanf("%lf%lf", &p[i].x, &p[i].y); // if(p[i].y < p[1].y) swap(p[i], p[1]); } sort(p + 1, p + 1 + n); sort(p + 2, p + 1 + n, cmp2); int cnt = 1; A[1] = p[1]; for(int i = 2; i <= n ; ++ i) { while(cnt > 1 && dcmp(cross(A[cnt] - A[cnt - 1], p[i] - A[cnt])) != 1) -- cnt ; A[++ cnt] = p[i]; } A[++ cnt] = p[1]; double ans = 0.0; for(int i = 1; i < cnt ; ++ i) ans += dis(A[i], A[i + 1]); printf("%.2f", ans); return 0; }
这篇关于计算几何初步的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)