编写程序，输入A,B,C,D四个点的坐标，假设A,B,C三点可以构成一个三角形，判断D点是否落在三角形内。
解题思路：
假设三角形的三个点按照顺时针（或者逆时针）顺序是A,B,C。对于某一点P，求出三个向量PA,PB,PC, 然后计算以下三个叉乘（^表示叉乘符号）：
t1 = PA^PB,
t2 = PB^PC,
t3 = PC^PA,
如果t1，t2，t3同号（同正或同负），那么P在三角形内部，否则在外部。
(更多在代码后)
本题代码如下：
#include<stdio.h>
#include<math.h>
typedef struct Point
{
double x,y;
}Point;
Point decPoint(Point p1,Point p2)//计算p1-p2向量
{
Point ret;
ret.x=p1.x-p2.x;
ret.y=p1.y-p2.y;
return ret;
}
double multiPoint(Point p1,Point p2)//计算向量叉乘
{
return(p1.x*p2.y-p1.y*p2.x);
}
double crossByThreePoint(Point A,Point B,Point C)//叉乘(A
{
return multiPoint(decPoint(B,A),decPoint(C,A));
}
int sign(double x)//对x进行正负判断返回标志符
{
double eps=1e-8;
if(fabs(x)<eps) return 0;
if(x>0) return 1;
return -1;
}
int main()
{
int i,j,k;
Point pts[4];
double x,y;
int sgn[3];
for(int i=0;i<4;i++)//将A,B,C,D四个点存放在数组中
{
scanf("%lf%lf",&pts[i].x,&pts[i].y);
}
sgn[0]=sign(crossByThreePoint(pts[0],pts[1],pts[2]));//D点都参与形成向量
sgn[1]=sign(crossByThreePoint(pts[1],pts[2],pts[3]));
sgn[2]=sign(crossByThreePoint(pts[2],pts[0],pts[3]));
if(sgn[0]==0||sgn[1]==0||sgn[2]==0)//若D在三条边上
{
printf("Point D is on the triangle!\n");
}
else if(sgn[0]==sgn[1]&&sgn[1]==sgn[2])//若D在三角形内部
{
printf("Point D is on the triangle!\n");
}
else
{
printf("Point D is out of the triangle!\n");
}
return 0;
}https://blog.csdn.net/zxj1988/article/details/6260576
数学知识：
https://www.cnblogs.com/TenosDoIt/p/4024413.html
二维平面上判断点是否在三角形内
最近在项目中碰到的这个问题，在此记录一下。已知三角形的三个顶点坐标，判断某个点是否在三角形中（在三角形的边上，我们也视作在三角形中），本文给出了三种方法。
算法1
利用面积法，如上图所示，如果点P在三角形ABC的内部，则三个小三角形PAB, PBC, PAC的面积之和 = ABC的面积，反之则不相等。
已知三角形的三个顶点坐标求其面积，可以根据向量的叉乘，参考here。
该算法详见后面代码中的函数：IsPointInTriangle1
算法2
首先看一下这个问题，如何判断某两个点在某条直线的同一侧（代码中函数：IsPointAtSameSideOfLine）？
根据向量的叉乘以及右手螺旋定则，AB^AM （^表示叉乘，这里向量省略了字母上面的箭头符号）的方向为向外指出屏幕，AB^AN也是向外指出屏幕，但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) = 4*2 - 0*1 = 8
AB^AN = (4，0)^(3，4) = 4*4 – 0*3 = 16
AB^AO = (4,0)^(3,-4) = 4*-4 – 0*3 = –16
由上面的数值可知，可以根据数值的正负判断叉乘后向量的方向。即，如果叉积AB^AM 和 AB^AN的结果同号，那么M,N两点就在直线的同侧，否则不在同一侧。特殊地，如果点M在直线AB上，则AB^AM的值为0。（如果是在三维坐标系中，求出的叉积是一个向量，可以根据两个向量的点积结果正负来判断两个向量的是否指向同一侧） 本文地址
以上的问题解决了，就很容易的用来判断某个点是否在三角形内，如果P在三角形ABC内部，则满足以下三个条件：P,A在BC的同侧、P,B在AC的同侧、PC在AB的同侧。某一个不满足则表示P不在三角形内部。
该算法详见后面代码中的函数：IsPointInTriangle2
算法3
该方法也用到了向量。对于三角形ABC和一点P，可以有如下的向量表示：
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的计算量最少。
以下是代码，定义了两个类：二维向量类 和 三角形类
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 |
|