Representation and reasoning about general solid rectangles
Xiaoyu Ge, Jochen Renz · ANU Open Research (Australian National University) · 2013
Entities in two-dimensional space are often ap-proximated 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 Qualita-tive Spatial Reasoning, many different spatial rep-resentations 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 rectan-gles (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 rep-resentation and the corresponding reasoning meth-ods 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. 1