利用向量叉积计算与二叉树追踪快速搜索封闭区域

目的自动填充等值线图的难点是自动搜索出值域相同的各个封闭区域,常用的扫描线填充和区域填充方式存在计算量大、效率不高等问题。方法针对此问题,提出利用多边形特征点的向量叉积计算结果与多边形的绘制顺逆方向之间的相关性,判定等值图中断层多边形的走向,基于构成封闭等值区域的等值线及其属性值具有的规律性性质,即等值线属性值是等值或等间距,追踪区域时利用填充边界或断层上的等值线端点创建追踪二叉树。追踪相邻的两个等值线端点所在的封闭区域时,将其中一个端点作为二叉树的根节点,沿边界查找左右相邻的下一条等值线端点,并将找到的端点作为左右子节点,从而实现封闭区域的快速追踪;通过封闭区域面积排序确定不同区域之间相互包含关系,据此构建拓扑相邻关系树,实现封闭区域的顺序覆盖填充,设计出更加简单、快速区分不同封闭区域的区域填充颜色选取方法。结果该方法简化了复杂的等值连通区域搜索算法,等值图的颜色变化趋势能保持一致,数据测试对比证明了所提算法的正确性。结论该算法通过一系列等值线能一次性得到组成封闭区域边界的点集合,因此,可以实现等值线和等值区域边界的完全吻合,当某些等值线发生变化时,只需更新相关的等值区域即可,提高了等值图件的编辑效率。