判断一个点是否在三角形内

给定平面上一点p(x0,y0)，判断该点是否在三角形ABC中，三角形顶点坐标分别为A(xa,xb),B(xb,yb),C(xc,yc)。可以使用面积法来判断，方法如下：其中S(A,B,C)表示三角形ABC的面积。

 

• 若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边上； 
• 若abs( S(A,B,C) ) < abs( S(P,B,C) ) + abs( S(A,P,C) ) + abs( S(A,B,P) ) ，则P在三角形ABC的外部； 
• 对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的面积。

巧用向量计算三角形面积，这篇文章的证明很好理解。

public static final double EPS = 1e-6;

public static class Point{
	int x, y;
	public Point(int x, int y) {
		this.x = x;
		this.y = y;
	}
}

public static double calcArea(Point a, Point b, Point c) {
	int x1 = b.x - a.x;
	int y1 = b.y - a.y;
	int x2 = c.x - a.x;
	int y2 = c.y - a.y;
	return Math.abs(x1*y2-x2*y1)/2.0;
}

public static boolean isInsideTriangle(Point a, Point b, Point c, Point p) {
	double abc = calcArea(a, b, c);
	double abcp = calcArea(a, b, p) + calcArea(a, c, p) + calcArea(b, c, p);
	return Math.abs(abc - abcp) < EPS;
}