A presentation and explanation of an algorithm you have written, which uses appropriate discrete data structures to solve a computational problem.

Given a list of rectangles and a circle which finds any rectangle which intersects the circle.

I have designed an algorithm that can tell the user if any number of rectangles intersects a circle. This particular problem asks if multiple rectangles intersects a single circle, which is a good way of representing geometric data. Rectangles can be represented as data by using 2 points of the rectangle for example the top left and bottom right corners, this will tell the user everything about this particular rectangle’s position and shape. Another way to represent a rectangle’s data is by keeping the top left corner’s data especially the width and height of the rectangle. Circles can be represented as data by only 2 things which are the centre point and the radius, this specifies everything about any circle that is produced. In my algorithm there are only two required inputs and one required output. The first input is a list of rectangles which are both represented by two points of the rectangle. This input is required to find out if any rectangle from the given list does or does not intersect a circle. An example of this could be “box1 = Rectangle(100, 200, Center_Point(50, 50))”. The second input is a list of circles which is going to be represented by it’s centre point and radius. An example of this could be “center = center_point(150, 100)” “circle = Circle(center, 75)”. The first output is required to find out if any rectangle in the given list intersects a circle in the given list or does not intersect the circle. An example of this could be “Rectangle does overlap with the circle”.

There are 5 subproblems that need to be solved that I have identified. The first subproblem is look at each value in rectangle list one by one. This is a good way of making sure each value in the list is checked properly. The second subproblem is very similar to the first subproblem which is look at each value in circle list one by one. This will only have one circle in the list which means it is a very small list. The third subproblem is to see if a rectangle intersects the circle. This subproblem is very important because it solves most of the algorithms solution. The fourth subproblem is see what the distance is between two different points. This subproblem can tell the user how far away one point of the rectangle is from the circle’s radius. The last subproblem is to see if the entire rectangle is in the circle. This subproblem can also tell the user if they have the full rectangle in the circle’s radius and center point.

My algorithm works by using three different classes and three different functions to be able to solve the problem mentioned in the subtitle. There are two main data structures that I have used which are Array List and Linear Search. The Array List data structure has been used in my algorithm because of it’s fixed length as a rectangle only has 4 points that need to be represented. The only issue with using an Array List data structure is you cannot change the size of the list without creating a new list. I have chosen to use the Linear Search data structure because you can look at the whole list and very easily see where the target value is, without trying values one at a time. 

The main ideas for designing my algorithm was having a center point for the rectangles and the circle which will be able to add a point and increment. The second idea was to create an individual class for the rectangles and circle so they can do different functions. The third idea was to create different functions to work out problems such as when a rectangle overlaps a circle or the distance between two points. The last idea was to run some tests to show this algorithm does it’s purpose. There are three special cases that need to be handled which are find the range between two different points which can tell the user how far away it is from each point. The second and third cases are very similar as they are both trying to see if a rectangle has overlapped.

Last of all, I think that my algorithm is good but could be improved by adding some recursive structures to it.