Computing Topological Predicates between complex objects using OpenMP and OpenACC

ABSTRACT

Topological relations between spatial objects are important in awide range of fields that involve spatial data and reasoning, suchas artificial intelligence, computer vision, robotics, GIS, andspatial cognition. AI/NLP requires topological relations to helpmachines reason about spatial relationships, while computervision and robotics rely on it for tasks like object recognition.GIS uses topological relations to model spatial relationshipsbetween geographic features, and spatial reasoning tasks requirean understanding of it. The main ideas utilized in this paper arethe Turn Test and Ray Shooting Algorithm, which are quick,reliable, and only involve basic arithmetic operations, andproduce a single metric that can be utilized to create a set ofguidelines to complete the matrix. Additionally, the paperperforms a more efficient comparative analysis of OpenMP andOpenACC implementations by examining randomly generatedline segments of two polygons in terms of their running times.

INTRODUCTION

Topological relation provide us the information about the spatialrelationships between different parts of the objects, regardless oftheir exact geometric shape or size. This information can beused in a wide range of applications, including imagerecognition, computer vision, geographic information systems,and robotics. Topological relations can also help to simplifycomplex shapes, making them easier to analyze and process.

The 9-intersection matrix can be used as a tool used to representthe topological relations between two-dimensional spatialobjects. It provides a standardized way to describe the possiblerelationships between two objects, such as whether they touch,overlap, or contain each other.
The 9-intersection matrix allows for efficient and accuratespatial reasoning, such as determining if two objects intersect orif one object is completely contained within another. It is also afundamental component of many geographic informationsystems and spatial databases, which rely on topologicalrelationships for spatial analysis and decision-making.

Additionally, the 9-intersection matrix can be used in computervision and image processing applications, such as objectrecognition and scene understanding.