Question

Exercise 3 Collision detection is very important in many applications such as computer graphics, video games, robotics, etc. Checking in dt f two objects collide, however, is very costly as it involves calculating possible intersections between any part of one object with any part of another an O(N) process (where N is typically large). No Collision Collision LI Block Profagonist Protagonist Xp Xa Xp X A better approach consist of enclosing each object with a bounding box or rectangle, as depicted on the right. If two bounding boxes do not intersect, as is the case most of the time, there is no need for further calculation! (It is only when they intersect that we need to determine in detail where and how much..) In this exercise, we consider a one-dimensional version of the problem, where characters have a name, a position x on the horizontal axis, and a width (of the bounding box). Write a user function that will take a list of (unsorted) characters as argument and return the list of characters that intersect with another (i.e, such that their bounding boxes overlap). To improve performance, your function should store characters in an array-based Binary Search Tree (based on their position) and use it. Note that, while creating the BST is an O(N logN) process, later processing can be done in O(N) time. For testing purposes, you should create a list of 50 characters with names such as C1...C100, randomly generated, unique integer positions in the range 0...1000, and randomly generated widths in the range 10...40

Program with C++.
Please provide an output.
Will give a thumbs up for the right effort :)

Answer 1