Representation and reasoning about general solid rectangles

Entities in two-dimensional space are often approximated using rectangles that are parallel to the two axes that define the space, so-called minimum-bounding rectangles (MBRs). MBRs are popular in Computer Vision and other areas as they are easy to obtain and easy to represent. In the area of Qualitative Spatial Reasoning, many different spatial representations are based on MBRs. Surprisingly, there has been no such representation proposed for general rectangles, i.e., rectangles that can have any angle, nor for general solid rectangles (GSRs) that cannot penetrate each other. GSRs are often used in computer graphics and computer games, such as Angry Birds, where they form the building blocks of more complicated structures. In order to represent and reason about these structures, we need a spatial representation that allows us to use GSRs as the basic spatial entities. In this paper we develop and analyze a qualitative spatial representation for GSRs. We apply our representation and the corresponding reasoning methods to solve a very interesting practical problem: Assuming we want to detect GSRs in computer games, but computer vision can only detect MBRs. How can we infer the GSRs from the given MBRs? We evaluate our solution and test its usefulness in a real gaming scenario.