Consistency Checking Of Cardinal Direction Relations Based On Graph

Consistency checking problem is a fundamental theory case, and becomes a most branch of reasoning on spatial direction relations. More and more research- ers begin to focus on the field. In general, consistency checking is NP-Comlete, most of researchers home and abroad concentrate on the subclass of convex relations. Although they use kinds of composing methods, most of their final results are built on the theory of"Path Consistency". Traditonary pure mathematics method has few breakthrouth.This paper presents a new solution for region objects and point objects, a visual checking based on directed graph, which provides a new way. Firstly, a series of definitions of graph model about region objects are illustrated, every set of directional relation is translated into directed graph by partition, namely, nodes represent objects and edges denote relations between primary object and referrence object. Then according to given rules, the graph of whole relation specifications was merged and refined, a spatial graph in vertical(SGV for short) is generated. If a cycle is detected in SGV, then the given specifications are in- consistent. Lastly this paper proves the correctness of this method in theory and by example.Immediately, the paper discusses point objects,the basic idea is to introduce the notion of coordinates graph,that is global coordinates system corresponding to geographic referrence frame, by projecting direction constraints on both X and Y axis to form coordinates graph, consistency checking is then transformed to a graph cycle detection problem. At last the paper give it's pseudo-code algorithm which can be achieved with O(n+e) time, exceeding Allen's O(n2).