【面试】【二维平面上判断点是否在三角形内】_android 判断一个点是否在三角形内-程序员宅基地

技术标签: 面试  算法  

二维平面上判断点是否在三角形内

算法1
在这里插入图片描述

利用面积法,如上图所示,如果点P在三角形ABC的内部,则三个小三角形PAB, PBC, PAC的面积之和 = ABC的面积,反之则不相等。
已知三角形的三个顶点坐标求其面积,可以根据向量的叉乘,参考here
该算法详见后面代码中的函数:IsPointInTriangle1

算法2
首先看一下这个问题,如何判断某两个点在某条直线的同一侧(代码中函数:IsPointAtSameSideOfLine)?
在这里插入图片描述

根据向量的叉乘以及右手螺旋定则,AB^AM (表示叉乘,这里向量省略了字母上面的箭头符号)的方向为向外指出屏幕,ABAN也是向外指出屏幕,但AB^AO的方向是向内指向屏幕,因此M,N在直线AB的同侧,M ,O在直线AB的两侧。实际计算时,只需要考虑叉积的数值正负
假设以上各点坐标为A(0,0), B(4,0), M(1,2), N(3,4), O(3,-4), 则:
AB^AM = (4,0)^(1,2) = 42 - 01 = 8
AB^AN = (4,0)^(3,4) = 44 – 03 = 16
AB^AO = (4,0)^(3,-4) = 4*-4 – 0*3 = –16
由上面的数值可知,可以根据数值的正负判断叉乘后向量的方向。即,如果叉积AB^AM 和 ABAN的结果同号,那么M,N两点就在直线的同侧,否则不在同一侧。特殊地,如果点M在直线AB上,则ABAM的值为0。(如果是在三维坐标系中,求出的叉积是一个向量,可以根据两个向量的点积结果正负来判断两个向量的是否指向同一侧) 本文地址

以上的问题解决了,就很容易的用来判断某个点是否在三角形内,如果P在三角形ABC内部,则满足以下三个条件:P,A在BC的同侧、P,B在AC的同侧、PC在AB的同侧。某一个不满足则表示P不在三角形内部。
该算法详见后面代码中的函数:IsPointInTriangle2

算法3
该方法也用到了向量。对于三角形ABC和一点P,可以有如下的向量表示:
image
p点在三角形内部的充分必要条件是:1 >= u >= 0, 1 >= v >= 0, u+v <= 1。
已知A,B,C,P四个点的坐标,可以求出u,v,把上面的式子分别点乘向量AC和向量AB
解方程解出u,v后只需要看他们是否满足“1 >= u >= 0, 1 >= v >= 0, u+v <= 1”,如满足,则,p 在三角形内。
(u = 0时,p在AB上, v = 0时,p在AC上,两者均为0时,p和A重合)
该算法详见后面代码中的函数:IsPointInTriangle3

算法4

该算法和算法2类似,可以看作是对算法2的简化,也是用到向量的叉乘。假设三角形的三个点按照顺时针(或者逆时针)顺序是A,B,C。对于某一点P,求出三个向量PA,PB,PC, 然后计算以下三个叉乘(^表示叉乘符号):

t1 = PA^PB,

t2 = PB^PC,

t3 = PC^PA,

如果t1,t2,t3同号(同正或同负),那么P在三角形内部,否则在外部。

该算法详见后面代码中的函数:IsPointInTriangle4

经过测试,算法4最快,算法3次之,接着算法2,算法1最慢。直观的从计算量上来看,也是算法4的计算量最少。

以下是代码,定义了两个类:二维向量类 和 三角形类

//类定义:二维向量
class Vector2d
{
    
public:
    double x_;
    double y_;
 
public:
    Vector2d(double x, double y):x_(x), y_(y){
    }
    Vector2d():x_(0), y_(0){
    }
 
    //二维向量叉乘, 叉乘的结果其实是向量,方向垂直于两个向量组成的平面,这里我们只需要其大小和方向
    double CrossProduct(const Vector2d vec)
    {
    
        return x_*vec.y_ - y_*vec.x_;
    }
 
    //二维向量点积
    double DotProduct(const Vector2d vec)
    {
    
        return x_ * vec.x_ + y_ * vec.y_;
    }
 
    //二维向量减法
    Vector2d Minus(const Vector2d vec) const
    {
    
        return Vector2d(x_ - vec.x_, y_ - vec.y_);
    }
 
    //判断点M,N是否在直线AB的同一侧
    static bool IsPointAtSameSideOfLine(const Vector2d &pointM, const Vector2d &pointN, 
                                        const Vector2d &pointA, const Vector2d &pointB)
    {
    
        Vector2d AB = pointB.Minus(pointA);
        Vector2d AM = pointM.Minus(pointA);
        Vector2d AN = pointN.Minus(pointA);
 
        //等于0时表示某个点在直线上
        return AB.CrossProduct(AM) * AB.CrossProduct(AN) >= 0;
    }
};
 
//三角形类
class Triangle
{
    
private:
    Vector2d pointA_, pointB_, pointC_;
 
public:
    Triangle(Vector2d point1, Vector2d point2, Vector2d point3)
        :pointA_(point1), pointB_(point2), pointC_(point3)
    {
    
        //todo 判断三点是否共线
    }
 
    //计算三角形面积
    double ComputeTriangleArea()
    {
    
        //依据两个向量的叉乘来计算,可参考http://blog.csdn.net/zxj1988/article/details/6260576
        Vector2d AB = pointB_.Minus(pointA_);
        Vector2d BC = pointC_.Minus(pointB_);
        return fabs(AB.CrossProduct(BC) / 2.0);
    }
 
    bool IsPointInTriangle1(const Vector2d pointP)
    {
    
        double area_ABC = ComputeTriangleArea();
        double area_PAB = Triangle(pointP, pointA_, pointB_).ComputeTriangleArea();
        double area_PAC = Triangle(pointP, pointA_, pointC_).ComputeTriangleArea();
        double area_PBC = Triangle(pointP, pointB_, pointC_).ComputeTriangleArea();
 
        if(fabs(area_PAB + area_PBC + area_PAC - area_ABC) < 0.000001)
            return true;
        else return false;
    }
 
    bool IsPointInTriangle2(const Vector2d pointP)
    {
    
        return Vector2d::IsPointAtSameSideOfLine(pointP, pointA_, pointB_, pointC_) &&
            Vector2d::IsPointAtSameSideOfLine(pointP, pointB_, pointA_, pointC_) &&
            Vector2d::IsPointAtSameSideOfLine(pointP, pointC_, pointA_, pointB_);
    }
 
    bool IsPointInTriangle3(const Vector2d pointP)
    {
    
        Vector2d AB = pointB_.Minus(pointA_);
        Vector2d AC = pointC_.Minus(pointA_);
        Vector2d AP = pointP.Minus(pointA_);
        double dot_ac_ac = AC.DotProduct(AC);
        double dot_ac_ab = AC.DotProduct(AB);
        double dot_ac_ap = AC.DotProduct(AP);
        double dot_ab_ab = AB.DotProduct(AB);
        double dot_ab_ap = AB.DotProduct(AP);
 
        double tmp = 1.0 / (dot_ac_ac * dot_ab_ab - dot_ac_ab * dot_ac_ab);
         
        double u = (dot_ab_ab * dot_ac_ap - dot_ac_ab * dot_ab_ap) * tmp;
        if(u < 0 || u > 1)
            return false;
        double v = (dot_ac_ac * dot_ab_ap - dot_ac_ab * dot_ac_ap) * tmp;
        if(v < 0 || v > 1)
            return false;
 
        return u + v <= 1;
    }
 
    bool IsPointInTriangle4(const Vector2d pointP)
    {
    
        Vector2d PA = pointA_.Minus(pointP);
        Vector2d PB = pointB_.Minus(pointP);
        Vector2d PC = pointC_.Minus(pointP);
        double t1 = PA.CrossProduct(PB);
        double t2 = PB.CrossProduct(PC);
        double t3 = PC.CrossProduct(PA);
        return t1*t2 >= 0 && t1*t3 >= 0;
    }
};
 
 
int main()
{
    
    Triangle tri(Vector2d(0,0), Vector2d(6,6), Vector2d(12,0));
    srand(time(0));
    for(int i = 0; i < 20; ++i)
    {
    
         Vector2d point((rand()*1.0 / RAND_MAX) * 12, (rand()*1.0 / RAND_MAX) * 6);
         cout<<point.x_<<" "<<point.y_<<":     ";
         cout<<tri.IsPointInTriangle1(point)<<" ";
         cout<<tri.IsPointInTriangle2(point)<<" ";
         cout<<tri.IsPointInTriangle3(point)<<" ";
         cout<<tri.IsPointInTriangle4(point)<<endl;
 
    }
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/zoroooooo/article/details/118228592

智能推荐

Hexo中的LaTex公式渲染问题_hexo无法渲染公式-程序员宅基地

文章浏览阅读1.5k次。本文首发于我的个人博客Suixin’s blogMarkdown中插入数学公式是常有的事,而Hexo博客框架主要是Markdown格式的文档,如果不能正常渲染Latex公式,那岂不gg……下面来看看Hexo渲染数学公式遇到的问题以及解决方案。渲染下划线的问题_在Latex公式中代表脚标,是非常常用的符号,而在Markdown中代表斜体,如果直接使用,将会产生公式无法渲染的问题,因为被H..._hexo无法渲染公式

Ubuntu14.04上安装pip的方法_pipu24-程序员宅基地

文章浏览阅读6.9k次。Ubuntu14.04上安装pip的方法在Ubuntu14.04上,建议通过下面的方法安装,这是一种通用的方法,也适用于Windows,当然在Windows下手动下载下来就行了wget https://bootstrap.pypa.io/get-pip.py --no-check-certificatesudo python get-pip.py 如果在Ub_pipu24

软件测试中的测试用例复用技术详解_什么是指对一个已经经过测试的软件包进行再次测试-程序员宅基地

文章浏览阅读1.6k次。一.引言随着软件工程领域的拓展,在软件产业飞速发展的今天,软件测试成为保证软件质量的重要手段。测试用例的选择对于软件测试的成败起着决定性作用,因此如何设计最少的测试用例实现最大的测试覆盖成为自动化测试领域中的主要研究对象。测试用例是确定一组最有可能发现错误的测试数据和流程,实现系统对某个功能的测试。而测试用例的设计与测试人员的个人经验息息相关,不同测试人员的个人经验和书写格式的差异导致了测试的盲目性,以至于产生较高的后期维护费用。测试用例的复用技术一方面是为了解决由测试人员经验不足带来的问题,同时还避免了_什么是指对一个已经经过测试的软件包进行再次测试

Ext.data.xxxStore 数据解析的简单运用_ext.data autodestroy-程序员宅基地

文章浏览阅读1.8k次。Normal07.8 磅02falsefalsefalseEN-USZH-CNX-NONEMicrosoftInternetExplorer4

老卫带你学---剑指offer刷题系列(2.替换空格)-程序员宅基地

文章浏览阅读102次。2.替换空格请实现一个函数,将一个字符串中的空格替换成“%20”。例如,当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。主要思路:第一种方法:用python字符串的replace方法。第二种方法:对空格split得到list,用‘%20’连接(join)这个list复杂度:O(N)# -*- coding:utf-8 -*-class S...

django 在uwsgi下无法访问_Docker环境部署Django+Supervisor+Nginx-程序员宅基地

文章浏览阅读234次。制作django镜像环境(Commit方式)下载Ubuntu$ docker pull ubuntu运行并进入容器$ docker container run -it ubuntu /bin/bash下载python/# apt-get install python3如遇到下载问题如下图更新软件源,之后就可以正常下载python了/# apt-get update安装pip3工具/# apt-ge..._docker-compose django uwsgi log无法打开

随便推点

k-core与k-shell的区别_kshell和kcore-程序员宅基地

文章浏览阅读2.3k次。一、问题描述:在文章中看到k-core与k-shell的概念,将全局图中分成2-core与1-shell的概念?结论:图可以说明一切,如图所示:1、2-core是包含蓝色与绿色的点,3-core会包含全部的点2、1-shell指的是黄色的点3、推断:任何一个图均可以分成k-core图与(k-1)-shell..._kshell和kcore

关于Vue的各个UI框架(elementUI、mint-ui、VUX)-程序员宅基地

文章浏览阅读793次。elementUI官网:http://element.eleme.io/使用步骤:1、安装完vue-cli后,再安装 element-ui命令行:npm i element-ui -D相当于 npm install element-ui --save-dev// i -> install D -> --save-dev S ..._miniui和elementui是什么关系

DP--最长公共子序列_dp最长公共子序列-程序员宅基地

文章浏览阅读513次。继续用典型问题来讨论动态规划的两个特性(重叠子问题和最优子结构)。最长公共子序列(LCS)问题描述:给定两个序列,找出在两个序列中同时出现的最长子序列的长度。一个子序列是出现在相对顺序的序列,但不一定是连续的。例如,“ABC”,“ABG”,“BDF”,“AEG”,“acefg“,..等都是”ABCDEFG“ 序列。因此,长度为n的字符串有2 ^ n个不同的可能的序列。注意最长公共子_dp最长公共子序列

特斯拉D1芯片遭实名diss:内存到封装都成问题,网友:反正不能公开测评-程序员宅基地

文章浏览阅读160次。明敏 发自 凹非寺量子位 报道 | 公众号 QbitAI在今年特斯拉AI开放日上,D1芯片风光无限。独特的晶圆封装系统+芯片设计,让D1在训练万亿参数级神经网络时,可以拥有数量级优势。特斯..._特斯拉 d1

Spark MLlib之使用Breeze操作矩阵向量_breeze.linalg.densematrix如何打印完整数据-程序员宅基地

文章浏览阅读3.2k次。Spark MLlib 使用 Breeze 操作矩阵向量_breeze.linalg.densematrix如何打印完整数据

如何做LINPACK测试及性能优化_linpack吧-程序员宅基地

文章浏览阅读2.1w次,点赞7次,收藏45次。如何做LINPACK测试及性能优化.曹振南[email protected][email protected]年8月本文主要说明如何完成HPL测试,并介绍了一些简单的性能优化方法。一、Linpack简介Linpack是国际上最流行的用于测试高性能计算机系统浮点性能的benchmark。通过对高性能计算机采用高斯消元法求解一元N次稠密线性代数方程组的_linpack吧