点在三角形或多边形内的判断.docVIP

点在三角形或多边形内的判断 by jack 2013-06-08 1、点与直线的位置关系 点在直线上，方程 0，如方程y x, 1,1 代入方程结果为0。 点不在直线上，方程 0或 0。即有两点在同侧，两方程的乘积必大于0；在异侧，则必小于0。 2、点在三角型或凸多边形内 在三角形三条边所在的直线同侧的点的集合即为此三角形，图中阴影部分。 3、代码 /** * 点在直线上 result 0 * 点在直线外 result 0 或 result 0, result1 * result2 必大于0 */ float PointInPoly::lineResult Point lpart1, // line part 1 三角形的端点1 Point lpart2, // line part 2 三角形的端点2 Point pt // 输入的点 要判断的点 float result 0; if lpart1.x lpart2.x // x a; 垂直于x轴 result pt.x – lpart1.x; else if lpart1.y lpart2.y // y a; 垂直于y轴 result pt.y – lpart1.y; else float a1 pt.y – lpart1.y; float a2 lpart2.y – lpart1.y; float b1 pt.x – lpart1.x; float b2 lpart2.x – lpart1.x; // 两点式方程 // y – y1 / y2 – y1 – x – x1 / x2 - x1 result a1/a2 – b1/b2 ; return result; /** * 点在三条直线同侧 * 该集合为三角形 */ bool PointInTriangle Point p1, Point p2, Point p3, Point pt float res1 lineResult p1, p2, pt * lineResult p1, p2, p3 ; if res1 0 return false; float res2 lineResult p1, p3, pt * lineResult p1, p3, p2 ; if res2 0 return false; float res3 lineResult p2, p3, pt * lineResult p2, p3, p1 ; if res3 0 return false; return true; /** * 用多个三角形组成凸多边形来判断点是否在凸多边形内 * PointArr 必须是顺序的 */ bool isPtInPoly Point *pointArr, unsigned int num, Point pt for unsigned int i 0; i num-2; ++i if isPtInTriangle pointArr[0], pointArr[i+1], pointArr[i+2], pt return true; return false; 附1 如果没有定义Point,可定义如下 struct Point float x; float y; Point x 0.0f; y 0.0f; Point float x1, float y1 x x1; y y1; ; 附2 网络上的相关资料 /question/座机电话号码.html thanks 月随 设三角形三个点 A a1,a2 ,B b1,b2 ,C c1,c2 三条边方程 BC:fa x,y 0 AC:fb x,y 0 AB:fc x,y 0 以BC为例，在三角形内的点必须与点A在BC的同侧 所以对于点D x,y 在三角形内首先要满足fa x,y *fa a1,a2 0 其他边也同理 所以只要比较 fa x,y *fa a1,a2 fb x,y *fb b1,b2 fc x,y *fc c1,c2 这三个数的正负性 1三个数都是正数：D在三角形内 2至少有一个负数：D在三角形外 3有且只有一个0，另两个为正数：在三角形边上 4有且只有一个0，一个正数一个负数：在三角形边的延长线上，也算在三角形外，因为满足2 5有二个0：在三角形的顶点上 6不可能出现3个0，或3个负数，或一个0两个负数的情况 该侧点代入方程y-ax 0 该侧点代入方程y-ax 0 该侧点代入方程y-ax 0 该侧