Drawing Interactive Euler Diagrams from Region Connection Calculus Specifications

摘要

This paper describes methods for generating interactive Euler diagrams. User interaction is needed to improve the aesthetic quality of the drawing without writing tedious formal specifications. More precisely, the user can modify the diagram’s layout on the fly by mouse control. We prove that the satisfiability problem is in ({textsf {PSPACE}}) and we provide two syntactic fragments such that the corresponding restricted satisfiability problem is already ({textsf {NP}})-hard. We describe (1) an improved local search based approach, (2) a method inspired from the gradient method and a hybrid method mixing both (1) and (2). A software tool was implemented and its implementation is described. We also experimentally compare the different methods. We first see that the improved local search and the hybrid method outperforms the local search from the literature and the gradient method for generating a diagram. Concerning interaction, the local search approach is not suitable but hybrid method and gradient method give both good results in terms of quality of drawings and stability. Specifications are written using region connection calculus (({mathbf{RCC-8 }})), radius constraints and disjunctions. Euler diagrams are described as set of circles.