Abstract
We have developed a qualitative calculus for three-dimensional directions and rotations. A direction is characterized in terms of the signs of its components relative to an absolute coordinate system. A rotation is characterized in terms of the signs of the components of the associated 3 × 3 rotation matrix. A system has been implemented that can solve the following problems: 1. Given the signs of direction and rotation matrix P, find the possible signs of the image of under P. Moreover, for each possible sign vector of · P, generate numerical instantiations of and P that yields that result. 2. Given the signs of rotation matrices P and Q, find the possible signs of the composition P · Q. Moreover, for each possible sign matrix for the composition, generate numerical instantiations of P and Q that yield that result. We have also proved some related complexity and expressivity results. The satisfiability problem for a qualitative rotation constraint network is NP-complete in two dimensions and NP-hard in three dimensions. In three dimensions, any two directions are distinguishable by a qualitative rotation constraint network.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 18-57 |
| Number of pages | 40 |
| Journal | Spatial Cognition and Computation |
| Volume | 14 |
| Issue number | 1 |
| DOIs | |
| State | Published - 2014 |
Keywords
- qualitative calculus
- qualitative spatial reasoning
- three-dimensional rotation
ASJC Scopus subject areas
- Modeling and Simulation
- Experimental and Cognitive Psychology
- Computer Vision and Pattern Recognition
- Earth-Surface Processes
- Computer Graphics and Computer-Aided Design