Collision Detection in Autonomous Vehicles Using Quadtrees
Team members - Anshika (2021CSB1069) Ajaybeer Singh (2021CSB1063) Shaik Darakshinda (2021CSB1130)
Instructor-Dr.Anil Shukla Teaching assistant-Ms.Monisha Singh
Quadtrees-Implementation,Analysis and Application
Project summary: In this universe of ever-growing data, we are always looking for DataStructures that are compact and depending on the nature of the data they save space as well as time while facilitating operations such as Search. Quad-tree is a data structure that allows partitioning of space that is simple and efficient to navigate and search. Our project brings about how Quadtrees can be implemented and how they significantly reduce the space and time requirements in practical situations. This datastructure is represented as a tree structure, which has at most four children and multiple levels. They are based on the principle of recursive decomposition. This has a significant use inthe development of Autonomous Vehicles.
One of the many applications on which our project is focused is Collision Detection. The program detects collision in Autonomous Vehicles. Firstly, the initial position of the center of the car is specified. Then the range where the car is to move is specified.Then the dimensions of the car (including safety margin is taken as input) and the obstacles (theircoordinates) are taken as input. All of this is done by Artificial Intelligence in practical situations. After that, the task of Quadtree comes into play. It is to detect an obstacle and tell if there is going to be a collision or not.
Time complexity of Quadtree operations:
1.Search:
Expected complexity- O(logn)
Worst complexity- 0(n)
2.Insert:
Expected complexity- O(logn)
Worst complexity- 0(n)
3.Delete:
Expected complexity- O(logn)
Worst complexity- 0(n)