如果不用向量的方法，可以用凸多边形理论求解。
设三角形的三顶点为A、B、C，现有点P(点P不是点A、B、C)，过A、P两点作直线交BC所在直线于点D，若点D位于线段BC上，则点P一定位于该三角形内。代码如下：
#include<stdio.h>
#include "math.h"
#define DBL_MIN 2.2250738585072014e-308
struct Point { /* (x,y) */
double x;
double y;
};
struct Line { /* a*x+b*y=c */
double a;
double b;
double c;
};
struct Triangle {
struct Point A;
struct Point B;
struct Point C;
};
struct Line createLine(struct Point p1, struct Point p2) {
struct Line line;
line.a = p1.y - p2.y;
line.b = p2.x - p1.x;
line.c = p1.x * (p1.y - p2.y) + p1.y * (p2.x - p1.x);
return line;
}
int isInTriangle(struct Triangle* tri, struct Point* P) {
/*P落在三角形顶点上*/
if (((fabs(P->x - tri->A.x) < DBL_MIN && fabs(P->y - tri->A.y) < DBL_MIN))
|| ((fabs(P->x - tri->B.x) < DBL_MIN && fabs(P->y - tri->B.y) < DBL_MIN))
|| ((fabs(P->x - tri->C.x) < DBL_MIN && fabs(P->y - tri->C.y) < DBL_MIN)))
return 1;
struct Line line1 = createLine(tri->A, *P);
struct Line line2 = createLine(tri->B, tri->C);
struct Point D;
if (fabs(line1.a * line2.b - line2.a * line1.b) >= DBL_MIN) {/* 不平行或不重合 */
D.x = (line2.b * line1.c - line1.b * line2.c) / (line1.a * line2.b - line2.a * line1.b);
D.y = (line1.a * line2.c - line2.a * line1.c) / (line1.a * line2.b - line2.a * line1.b);
if (((tri->B.x <= D.x && D.x <= tri->C.x) || (tri->C.x <= D.x && D.x <= tri->B.x))
&&((tri->B.y <= D.y && D.y <= tri->C.y) || (tri->C.y <= D.y && D.y <= tri->B.y)))
return 1;
}
return 0;
}
int isTriangle(struct Triangle tri) {
double AB, BC, AC;
AB = sqrt((tri.A.x - tri.B.x)*(tri.A.x - tri.B.x)+(tri.A.y - tri.B.y)*(tri.A.y - tri.B.y));
BC = sqrt((tri.C.x - tri.B.x)*(tri.C.x - tri.B.x)+(tri.C.y - tri.B.y)*(tri.C.y - tri.B.y));
AC = sqrt((tri.A.x - tri.C.x)*(tri.A.x - tri.C.x)+(tri.A.y - tri.C.y)*(tri.A.y - tri.C.y));
if (AB + BC > AC && BC + AC > AB && AC + AB > BC)
return 1;
else
return 0;
}
int main(int argc, char** argv) {
struct Triangle triangle = {{-2, 0},{2, 3}, {2, 0} };//三角形
struct Point points[] = {{-1.999,0.0001},{0, 0},{1,1},{2,3},{-1, 2} }; //测试点数组
if (isTriangle(triangle)) {
int i;
for (i = 0; i < 5; i++) {
if (isInTriangle(&triangle, &points[i]))
printf("点(%f,%f)在三角形内。\n", points[i].x, points[i].y);
else
printf("点(%f,%f)不在三角形内。\n", points[i].x, points[i].y);
}
} else
printf("不构成三角形！\n");
return 0;
}
运行结果：
//
// Do not forget my qq:573827574, thanks
//
#include "stdafx.h"
#include "math.h"
#include<stdio.h>
#include<stdlib.h>
typedef struct Point{
float x;
float y;
};
//输入参数：设定 A为原点 ；B为射线上的一点， BA组成一条射线
//输出参数：输出射线BA与X轴的夹角
double slope(Point A,Point B)
{
float tansita;
float sita;
float subEBx;
subEBx = abs(B.x - A.x );
if (B.x == A.x) subEBx = 0.0001;
tansita =(abs(B.y - A.y ))/subEBx;
sita = atan(tansita);
if ((B.x >=A.x )&&(B.y >=A.y )) return sita;
if ((B.x <=A.x )&&(B.y >=A.y )) return 3.1416 - sita;
if ((B.x <=A.x )&&(B.y <=A.y )) return 3.1416 +sita;
if ((B.x >=A.x )&&(B.y <=A.y )) return 2*3.1416 -sita;
}
//函数功能：判断射线DB是否在角ABC范围内，通过判断射线的与X轴的夹角是否在射线AB、CB范围之内
//输入参数：输入三个点，ABC，我们约定以B点为原点，射线AB，CB组成角ABC；
//输入参数：第四点为所要判断的点D ，如果射线DB在角ABC的范围内，
//输出参数：true = 该点在角ABC内，false = 该点不在角ABC内
bool InAngleArea(Point A,Point B,Point C,Point D)
{
float StartAngle,EndAngle;
float DAAngle;
StartAngle = slope(B,A);
EndAngle = slope(B,C);
if (EndAngle == 0.0 ) EndAngle = 2*3.1416;
DAAngle = slope(B,D);
//printf("\nn%f %f - %f\n",StartAngle,EndAngle,DAAngle);
if ((DAAngle>StartAngle )&&(DAAngle< EndAngle ))
return true;
else return false;
}
/////////////////////////////////////////////////
//***重要提示：请确保点参数A B C按逆时针输入***//
/////////////////////////////////////////////////
bool PointInTriangle(Point A,Point B,Point C,Point D)
{
bool aa,bb,cc;
aa = InAngleArea(C,B,A,D);
bb = InAngleArea(B,A,C,D);
cc = InAngleArea( A,C,B,D);
if (aa &&bb &&cc)
//if ( InAngleArea(A,B,C,D) && InAngleArea(B,C,A,D)&& InAngleArea( C,A,B,D))
return true ;
else
return false;
}
void main()
{
Point A,B,C,D;
printf("请输入三个点(按逆时针输入)的坐标（X，Y）\n");
scanf("%f%f",&A.x ,&A.y );
scanf("%f%f",&B.x ,&B.y );
scanf("%f%f",&C.x ,&C.y );
printf("请输入第四个点的坐标（X，Y）\n");
scanf("%f%f",&D.x ,&D.y );
printf("\n%f, %f",A.x , A.y );
printf("\n%f, %f",B.x , B.y );
printf("\n%f, %f",C.x , C.y );
printf("\n%f, %f\n",D.x , D.y );
if (PointInTriangle(A,B,C,D) == true)
printf("第四个点在三角形ABC中。\n");
else
printf("第四个点不在三角形ABC中。\n");
getchar();
system("pause");
}
点如果在三角形内，其与3顶点会形成3条线段。这3条新线段两两组合与三角形的三边形成3个新3角型。点在三角形里的条件就是原角型的3边都是新三角形里的最长边。ABC 顶i点d
(Ad<AB&&Bd<AB)&&....
你看是否简单易懂。别人说的射线太难了。
假设三角形三个顶点 A (x1, y1), B (x2, y2), C (x3, y3), 需要判定的点 P (x0, y0)
现在, 以A 为原点, 判断向量 AP, 与 AB, AC 的关系, 最简单的办法就是看它们的向量积
AP x AB = [ (x0 - x1)* (y2 - y1) - (x2 - x1)*(y0 - y1) ] i = Kb i
其中 i 是垂直于平面方向的单位向量
AP x AC = [ (x0 - x1)* (y3 - y1) - (x3 - x1)*(y0 - y1) ] i = Kc i
如果 AP 在 AB, AC 之间, 那么 Kb, Kc 符号相反, 看起来比较聪明的方式是把他们相乘, 不过这显然增加了运算量, 其实还是用逻辑判断比较好,
double Kb, Kc;
Kb = (x0 - x1)* (y2 - y1) - (x2 - x1)*(y0 - y1);
Kc = (x0 - x1)* (y3 - y1) - (x3 - x1)*(y0 - y1);
if ( ((0 > Kb) && (0 < Kc)) || ((0 < Kb) && (0 > Kc)) ) PinBC = 1;
else PinBC = 0;
.....
然后, 以 B, C 为原点, 分别判断 PinAC, PinAB.......
PinBC, PinAC, PinAB 只要有一个不满足, 就可以判断 P 不在三角形内了....
可以写成函数比较简洁
int PinAB ( double x0, double y0, double x1, double y1, double x2, double y2)
{
double Kb, Kc;
Kb = x0*y1 - x1*y0;
Kc = x0*y2 - x2*y1;
if ( ((0 > Kb) && (0 < Kc)) || ((0 < Kb) && (0 > Kc)) ) return 1;
return 0;
}
int PinABC ( double x0, double y0, double x1, double y1, double x2, double y2, double x3, double y3)
{
if ( PinAB ( x0 - x1, y0 -y1, x2 - x1, y2 - y1, x3 - x1, y3 - y1) &&
PinAB ( x0 - x2, y0 -y2, x3 - x2, y3 - y2, x1 - x2, y1 - y2) &&
PinAB ( x0 - x3, y0 -y3, x2 - x3, y2 - y3, x1 - x3, y1 - y3) ) return 1;
return 0;
}
当然这个算法没能利用 cpu 的向量计算能力, 如果 cpu 支持向量计算, 直接算向量的差/积要快不少....
