Boolean matrix operators for computing binary topological relations between complex regions

Complex regions are composed of a finite number of simple regions, and are always defined by hierarchical representation methods. This article focuses on a unified method for computing <i>n</i>-intersection-based binary topological relations between complex regions based on hierarchical characteristics, using known topological relations between simple regions. The hierarchical representation of complex regions is defined as the recursive process of region decomposition using a context-free grammar. To distinguish multiple components of a region and whether the interior of a hole is a part of the inner exterior or the outer exterior, three region operators are proposed to describe the configuration of a region represented as a formal expression. Then, three corresponding 25-intersection (25I) based Boolean matrix operators are proposed to compute topological relations based on the relationships between decomposed regions. Herein, the invalid conditions of the operators are verified in detail, and the invalidities can be eliminated by either applying our definition of complex regions or with the inclusion of additional information. The proposed 25I-based operators, as shown in our cases, can be used as a ‘bridge’ to link different <i>n</i>-intersection models, and as a useful computation tool for analyzing topological relations between regions with specific configurations.

复杂区域由有限个简单区域构成，且始终采用层级表示方法进行定义。本文基于层级特征，利用已知的简单区域间拓扑关系，提出了一种统一的计算方法，用于求解复杂区域间基于n交（n-intersection）模型的二元拓扑关系。复杂区域的层级表示被定义为采用上下文无关文法实现区域分解的递归过程。为区分区域的多个组成部分，并明确孔洞的内部究竟属于内外部还是外部外部，本文提出三种区域算子，用于描述以形式化表达式表示的区域构型。随后，本文提出三种对应的基于25交（25-intersection）的布尔矩阵算子，基于分解后区域间的关系计算拓扑关系。本文详细验证了这些算子的无效条件，并指出可通过采用本文提出的复杂区域定义，或补充额外信息来消除这些无效情形。本文提出的基于25交的算子，如案例所示，可作为连接不同n交模型的“桥梁”，同时也可作为分析特定构型区域间拓扑关系的实用计算工具。