阅读量:3
背景
鼠标操作时,经常要判断是否命中显示控件,特开发此算法快速判断。
原理
三角形三等分点定理是指在任意三角形ABC中,可以找到三个点D、E和F,使得线段AD、BE和CF均等分三角形ABC。 这意味着三个等分点分别位于三个边界上,并且每个等分点都将三角形划分为等面积部分。
代码
#include <stdio.h> #include <math.h> // 点 typedef struct { float x; float y; } *Point; // 直线距离 float distance(Point a, Point b) { return sqrt((b->x - a->x) * (b->x - a->x) + (b->y - a->y) * (b->y - a->y)); } // 三角形面积 float area(Point a, Point b, Point c) { float ab = distance(a, b); float ac = distance(a, c); float bc = distance(b, c); return 0.5 * sqrt(4 * ab * ab * ac * ac - (ab * ab + ac * ac - bc * bc) * (ab * ab + ac * ac - bc * bc)); } // 判断点是否在三角形上 _Bool isPtOn(Point a, Point b, Point c, Point pt) { float triangleArea = area(a, b, c); float splitTriangle1 = area(a, b, pt); float splitTriangle2 = area(a, c, pt); float splitTriangle3 = area(b, c, pt); return (splitTriangle1 + splitTriangle2 + splitTriangle3 == triangleArea); } int main(int argc, char **argv) { Point a = malloc(sizeof(float) * 2); a->x = -5; a->y = 0; Point b = malloc(sizeof(float) * 2); b->x = 0; b->y = 5; Point c = malloc(sizeof(float) * 2); c->x = 5; c->y = 0; // 在三角形上 Point d = malloc(sizeof(float) * 2); d->x = 0; d->y = 1; _Bool ret = isPtOn(a, b, c, d); printf("%d\n", ret); // 不在三角形上 d->x = 0; d->y = -1; ret = isPtOn(a, b, c, d); printf("%d\n", ret); }
输出
1 0
扩展
如何判断在矩形,任意多边形上?(提示:计算多边形面积是等于点切割多边形面积和)
Qt 判断一个点是否落在三角形内(算法)_qt判断一个点在三角形内-CSDN博客