如何判断点与三角形的位置关系
2021/9/26 23:41:40
本文主要是介绍如何判断点与三角形的位置关系,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
这个问题比较容易,写这篇文章的目的在于记录模板
- 如下图,点和三角形之间的位置关系有下面几种
- 其中点在三角形边上或者是在顶点上判断起来比较容易,只要枚举每一条边,如果发现这个点到两个端点之间的距离等于边长,那就是说这个点在三角形的一条边上,特判一下点和其他点重合的情况即可
- 那么如何判断点是在三角形外部还是内部呢?
- 如果从高中数学的角度来看,我们可能会想去把这三条直线方程写出来,通过看这个点是不是在这三条直线中间来判断,可能笔算起来比较容易,但是如果编程实现,那就太复杂了,不说点在直线两侧的若干情况需要讨论,直线方程也需要讨论斜率是否存在,除非山穷水尽实在没办法,我们不考虑这种办法
- 我们能够发现如果一个点在三角形内部,那么它和三个顶点的连线与原三角形的边构成的三个三角形的面积和等于原三角形的面积,如下图
- 如果一个点在三角形的外部,那么它和三个顶点的连线与原三角形的边构成的三个三角形的面积和大于原三角形,如下图
- 通过这个性质我们可以很方便的判断,编程细节,三角形面积通过海伦公式和向量叉积来求取,放个海伦公式复习一下,设三条边长分别为
a
,
b
,
c
a,b,c
a,b,c,
p
=
1
2
(
a
+
b
+
c
)
p=\frac{1}{2}(a+b+c)
p=21(a+b+c),那么三角形面积为
S = p × ( p − a ) × ( p − b ) × ( p − c ) S=\sqrt {p\times(p-a)\times(p-b)\times(p-c)} S=p×(p−a)×(p−b)×(p−c)
上一道例题
https://www.luogu.com.cn/problem/P1355
#include <bits/stdc++.h> using namespace std; inline int read(){ int x = 0, f = 1;char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = (x << 1) + (x << 3) + (c ^ 48);c=getchar();} return x*f; } const double eps = 1e-8; const int MAXN = 1e6 + 100; int sgn(double x){ if(fabs(x) < eps) return 0; return x < 0 ? -1 : 1; } struct Point{ double x, y; Point(){} Point(double x, double y): x(x), y(y){} bool operator == (const Point &B)const{ return x == B.x && y == B.y; } Point operator - (const Point &B)const{ return Point(x - B.x, y - B.y); } }s[MAXN]; typedef Point Vector; double Cross(Vector A, Vector B){ return A.x * B.y - A.y * B.x; } double distance(Point A, Point B){ return hypot(A.x - B.x, A.y - B.y); } void solve(){ double a, b; a = 1.0 * read(); b = 1.0 * read(); double p = 0.0; for(int i=0;i<3;i++){ if(Point(a, b) == s[i]){ cout << 4; return; } p += distance(s[i], s[(i + 1) % 3]); } p /= 2; for(int i=0;i<3;i++){ if(sgn(distance(s[i], s[(i + 1) % 3]) - distance(Point(a, b), s[i]) - distance(Point(a, b), s[(i + 1) % 3])) == 0){ cout << 3; return; } } double S2 = 0.0; double x = distance(s[0], s[1]); double y = distance(s[1], s[2]); double z = distance(s[2], s[0]); double S = sqrt(p * (p - x) * (p - y) * (p - z)); for(int i=0;i<3;i++){ S2 += fabs(Cross(Point(a, b) - s[i], Point(a, b) - s[(i + 1) % 3])); } S2 /= 2; if(sgn(S - S2) == 0) cout << 1; else if(sgn(S - S2) < 0) cout << 2; } int main(){ for(int i=0;i<3;i++){ s[i].x = 1.0 * read(); s[i].y = 1.0 * read(); } solve(); return 0; }
- 注意向量叉积的正负性
这篇关于如何判断点与三角形的位置关系的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-04TiDB 资源管控的对撞测试以及最佳实践架构
- 2024-07-03万字长文聊聊Web3的组成架构
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 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的分布式主键实现