两种2D相交性测试场景的优化技能

两种2D相交性测试场景的优化技巧

1. 点和多边形 相交线测试优化

最近在做gis数据处理相关工作，从原始数据中提取的城市的城市行政面 按照图幅进行切割的结果。为了直观我们首先对其进行一系列合并：结果是多个最大连通分量。

最后实际测试多边形合并后反而引入了一个性能问题，举北京的例子，如下：

左边是原始的行政区划集合，右边的合并后行政区划面由2013个顶点组成。

使用右边合并后的区域判断某个点是否在城市之内算法大概如下：

bool is_point_in_admin_area(point)
{
	foreach part:
		if ( !part.bbox.contains(point) )  
			continue;
		if (part.polygon.intersect(point))
			return true;
			
	return false;
}

城市行政面合并后的结果可能仍由多个part组成。对于每个part首先会根据包围盒进行预过滤，如果与包围盒相交，则遍历多边形所有边进行相交线测试（结果为边上，区域内部，区域外部）。实测性能十分慢。思考了很久以后突然发现问题所在：城市的包围盒很大，大约90%的输入顶点都通过了第一个if测试，然后进入第二个if测试，点和多边形相交测试是个O(n)的算法。当多边形顶点数达到一个量以后计算量十分大。

优化：直接使用未合并的行政区划作为输入，执行上面is_point_in_admin_area测试。发现果然性能提升了一倍，实测Linux 64机器上run：

合并后的C_AdmArea	06:31	几个part，每个part顶点数十分多
合并前的C_AdmArea	03:46	成百上千个小part，每个part顶点数十分少

从6分到3分钟，整整快了近一倍。左图 合并前的每个part的顶点量级小，虽然foreach循环次数多，但是输入的某个顶点一定是属于某个小part之内，可能只有10%的可能性进入第二个if判断，而且此时多边形和点相交的量级是多边形顶点的数百分之一。

2. 地图中文字相交性测试优化：

OOBB并不一定最优 计算量十分大，参见次数：http://blog.****.net/ryfdizuo/article/details/12655855

地图中需要实时判断两个文字是否重叠，如果使用OOBB，需要为每个文字进行实时建模然后进行判读，虽然OOBB测试结果十分精确，但是计算量也很大。

如下图将每个字单独做成AABB：

而AABB相交只是比较大小，速度非常快。这种方式实际上是一种近似求交，每个文字AABB计算的时候，需要向外扩充几个像素。