Computing Topological Predicates between complex objects using OpenMP and OpenACC

ABSTRACT

Topological relations between spatial objects are important in a wide range of fields that involve spatial data and reasoning, such as artificial intelligence, computer vision, robotics, GIS, and spatial cognition. AI/NLP requires topological relations to help machines reason about spatial relationships, while computer vision and robotics rely on it for tasks like object recognition. GIS uses topological relations to model spatial relationships between geographic features, and spatial reasoning tasks require an understanding of it. The main ideas utilized in this paper are the Turn Test and Ray Shooting Algorithm, which are quick,reliable, and only involve basic arithmetic operations, and produce a single metric that can be utilized to create a set of guidelines to complete the matrix. Additionally, the paper performs a more efficient comparative analysis of OpenMP and OpenACC implementations by examining randomly generated line segments of two polygons in terms of their running times.

INTRODUCTION

Topological relation provide us the information about the spatial relationships between different parts of the objects, regardless of their exact geometric shape or size. This information can be used in a wide range of applications, including image recognition, computer vision, geographic information systems,and robotics. Topological relations can also help to simplify complex shapes, making them easier to analyze and process.

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

Additionally, the 9-intersection matrix can be used in computer vision and image processing applications, such as object recognition and scene understanding.