公司项目, 要实现用户在矩形的红外图像上圈一块区域, 计算该区域内部的平均温度, 最大, 最小温度, 圈的区域有可能是矩形, 椭圆, 或者任意由多条线段构成的多边形, 实现这个需求可以转换为求一个点是否在该几何图形内部, 下面总结一下各种几何图形的判断方法.
1. 矩形
判断点是否在矩形内, 只要确定点的坐标在矩形四个顶点限定范围内即可
如上图, 满足 x<=x2&&x>x1&&y>y1&&y<y 即可
2. 椭圆
判断点是否在椭圆内, 可以根据椭圆表达式求得
如上图, 如果 a>b, 即焦点在 x 轴上, 则满足 (x*x/a/a+y*y/b/b <1) 的点在椭圆内, 如果 a<b, 即焦点在 y 轴上, 则满足 (y*y/a/a+x*x/b/b<1) 的点在椭圆内
3. 由多个点构成的不规则图形
对于不规则图形, 可以通过射线法判断, 即计算射线与多边形各边的交点, 如果是偶数, 则点在多边形外, 否则在多边形内
算法代码如下:
- public bool Contains(Point test)
- {
- int i;
- int j;
- bool result = false;
- for (i = 0, j = _pointList.Count - 1; i < _pointList.Count; j = i++)
- {
- if ((_pointList[i].Y> test.Y) != (_pointList[j].Y> test.Y) &&
- (test.X <(_pointList[j].X - _pointList[i].X) * (test.Y - _pointList[i].Y) / (_pointList[j].Y - _pointList[i].Y) + _pointList[i].X))
- {
- result = !result;
- }
- }
- return result;
- }
要计算射线与线段的交叉, 可以观察下图:
t 点与线段 (v1-v2) 要发生相交, t.y 必须在线段的两个顶点的 y 值之间, 即 t.y<v2.y&&t.y>v1.y
满足上面这个条件以后, 只需要判断该点在线段的左侧还是右侧, 如果在线段左侧, 则该射线与线段相交, 要判断 t 在左侧还是右侧, 需要先求得水平线与线段的交点 c 的 x 坐标: c.x=(t.y-v1.y)*(v2.x-v1.x)/(v2.y-v1.y)+v1.x
由上两条, 可以推得, t 点与线段相交的条件为: t.y<v2.y && t.y>v1.y && c.x<((t.y-v1.y)*(v2.x-v1.x)/(v2.y-v1.y)+v1.x)
接下来考虑一些特殊情况:
v1.y==v2.y, 即射线与线段重合, 该情况不满足第一个条件, 因而对结果没有影响
射线在顶点上相交, 有如下几种情况:
A 顶点为交叉计数提供奇数(1),B,C 为交叉计数提供偶数(分别是 0,2), 正好符合算法条件, A 是多边形真正的交叉, B,C 不是
算法测试结果如下:
测试程序地址: https://github.com/xienb/SpatialRelationTest
来源: https://www.cnblogs.com/xienb/p/10532087.html