给定平面上一点p(x0,y0),判断该点是否在三角形ABC中,三角形顶点坐标分别为A(xa,xb),B(xb,yb),C(xc,yc)。可以使用面积法来判断,方法如下:其中S(A,B,C)表示三角形ABC的面积。
1、 若abs( S(A,B,C) ) = abs( S(P,B,C) ) + abs( S(A,P,C) ) + abs( S(A,B,P) ) ,则P在三角形ABC的内部或边上;如果还有abs( S(P,B,C) )、abs( S(A,P,C) ) 和abs( S(A,B,P) )全都大于0,则说明P在三角形ABC的内部,否则P在三角形ABC的边上,具体为:S(P,B,C)为0,则说明P在BC边上,S(A,P,C)为0,则说明P在AC边上,S(A,B,P)为0,则说明P在AB边上;
2、 若abs( S(A,B,C) ) < abs( S(P,B,C) ) + abs( S(A,P,C) ) + abs( S(A,B,P) ) ,则P在三角形ABC的外部;
3、 对abs( S(A,B,C) ) > abs( S(P,B,C) ) + abs( S(A,P,C) ) + abs( S(A,B,P) ) 情况在理论上是不存在的
此处又引出另一个问题,如何求平面中三角形的面积?这个可以使用叉乘法来实现,即S(A,B,C)为向量AB叉乘AC所得向量模的1/2,再对该值求绝对值就是三角形ABC的面积。
#include <iostream>
#include <math.h>
using namespace std;
#define ABS_FLOAT_0 0.0001
struct point_float
{
float x;
float y;
};
/**
* @brief 计算三角形面积
*/
float GetTriangleSquar(const point_float pt0, const point_float pt1, const point_float pt2)
{
point_float AB, BC;
AB.x = pt1.x - pt0.x;
AB.y = pt1.y - pt0.y;
BC.x = pt2.x - pt1.x;
BC.y = pt2.y - pt1.y;
return fabs((AB.x * BC.y - AB.y * BC.x)) / 2.0f;
}
/**
* @brief 判断给定一点是否在三角形内或边上
*/
bool IsInTriangle(const point_float A, const point_float B, const point_float C, const point_float D)
{
float SABC, SADB, SBDC, SADC;
SABC = GetTriangleSquar(A, B, C);
SADB = GetTriangleSquar(A, D, B);
SBDC = GetTriangleSquar(B, D, C);
SADC = GetTriangleSquar(A, D, C);
float SumSuqar = SADB + SBDC + SADC;
if ((-ABS_FLOAT_0 < (SABC - SumSuqar)) && ((SABC - SumSuqar) < ABS_FLOAT_0))
{
return true;
}
else
{
return false;
}
}
void main(void)
{
point_float A, B, C, P;
A.x = A.y = 1.0;
B.x = 4.0;
B.y = 1.0;
C.x = 2.0;
C.y = 5.0;
P.x = 3.0;
P.y = 2.0;
if (IsInTriangle(A, B, C, P))
{
cout<<"P is in ABC!"<<endl;
}
else
{
cout<<"P is not in ABC!"<<endl;
}
}
分享到:
相关推荐
判断一个点是否在三角形内的几种算法(2D). 一、根据面积来计算 二、利用矢量叉积来计算
路是:首先判断该点是否在三角形上,其次根据该点是否在同侧与另一点是否在同一侧 根据结果如果有全为正则为内 如果至少有一个点为负则为外!
判断某点是否在任意多边形内两种算法的比较.pdf
已知三个点的坐标,某未知点与三个已知点的距离,求未知点的坐标。利用三点的其距离,构成圆形的交点,是唯一一点,就是要求的未知点。
13.基于模拟退火算法的 TSP 算法.zip13.基于模拟退火算法的 TSP 算法.zip13.基于模拟退火算法的 TSP 算法.zip13.基于模拟退火算法的 TSP 算法.zip13.基于模拟退火算法的 TSP 算法.zip13.基于模拟退火算法的 TSP 算法...
/** 判断点在多边形内算法. * 使用计算几何中的弧线法,内角和法的一种变形. * 与射线法、内角和法一样,时间复杂度是O(n). * @param point 待判断的点 * @param poly 多边形,这里简单地看做为一个点集 */
为了准确地在三维网格模型上定位特征角点,提出了一种基于变形分析的三维Susan角点检测算法。算法首先利用邻接区域信息定义顶点的变形函数,由变形函数值得到候选角点集合;对于候选角点,设定比较区域,在区域内用...
算法判断点在多边形内
Harris角点检测算法.pptx
13.求直线的倾斜角 7 14.求点关于某直线的对称点 7 15.判断两条直线是否相交及求直线交点 7 16.判断线段是否相交,如果相交返回交点 7 ㈢ 多边形常用算法模块 1. 判断多边形是否简单多边形 8 2. 检查多边形...
基于尺度、距离、旋转测度的角点匹配算法..pdf
目标超平面上的一种对偶单纯形算法.pdf
13.求直线的倾斜角 14.求点关于某直线的对称点 15.判断两条直线是否相交及求直线交点 16.判断线段是否相交,如果相交返回交点 ㈢ 多边形常用算法模块 1. 判断多边形是否简单多边形 2. 检查多边形顶点的凸凹性 3. ...
基于弱对偶的平面三角形格网离散线转化生成算法.docx
判断直线是否在矩形内,不适用乘除法,高效率算法,仅供参考!
C#判断点是否在线上(该算法也可适用于C++,java)
基于角点检测图像配准的一种新算法.
基于FPGA实现梯形-S形算法.pdf
论文研究-修正AHP中判断矩阵一致性的加速遗传算法.pdf, 作为系统工程中典型的定性定量综合集成方法,层次分析法(AHP)在各种复杂系统综合评价和多目标决策中具有广泛的...
目标超平面上的一种原始-对偶单纯形算法.pdf