The homework problem statement is available in the brute upload system bounding boxes

The following text is aimed at students with significantly smaller programming expereince. Its presents a sequence of manageable smaller steps which should lead to a working solution of the problem.

The problem is designed to practice the usage of arrays/lists in Python, so it is quite probable that you will use lists througout your code. If, for any reason, you are more comfortable with some other data structure, use that structure in your code and only later, when your program is completed and it works, try to write it once more with lists. The expected length of the code is about 100-150 lines, an experienced Python programmer might produce a shorter code. If the code of your solution occupies more than about 200 lines and still has tendency to grow, the chances are that there are either some unnecessary parts of the code or maybe the data representation is too complex. In such case try to reduce the size of the code and strive to break the code into more smaller functions. Otherwise, the code length should not be of too moch concern.

Basic Solution Rule:

Do complete each step before you move to the next one. Starting in the middle makes no sense. Also, trying to go to the next step without reliably completing the previous one will probably only increase your confusion. After each step run your program more times on more data to make sure that it really does what it has to do.

Step 0. “Know the assignement”

An absolute necessity, in this problem and in any future problem as well, is to know and understand the assignment. In particular, you shuld be able to communicate, when asked, what is the overal goal of the problem, what are the input data and what output data are expected. Preferably, in this step, you should not think about any programming at all, no data strucures no algorithms, no programming language.

Step 1. “Just read in the data”

Read the input data into any data structure you can manage and then print (the copy of) those data on the standard output (screen). The order and/or the format of the printed data does matter too much, the important point is, that you are able to see that the data were read correctly and that they are stored in a structure you can access and (hopefully) exploit in the next steps.

Step 2. “List triples”

With the input points (data) are reliably stored in a data structure, the next phase is to create all triples of points. In this step, it is enough just to print the triples, you do not have to think where and how the triples should be stored. Therefore, your task is now to implement some loops which will process the points in your data structure and which will print on the screen all possible triples of the points in the memory. In Example 1 the output should contain 20 triples, in Example 2 the output should contain 4 triples, figure out theoretically how many triples should be there in Example 3. Then run your code on Example 3 and see if it fits the prediction.

Step 3. “List bounding boxes”

Compute a bounding box for each triple. This is best done by a separate function which input parameter is one triple of points and the output parameter is the bounding box of the triple. Think how would you represent a bounding box. It may be a set or a touple or a list of four corner points or a set or a touple or a list of two oposite corner points or a set or a touple or a list of one corner points and the width and the height of the box or a set or a touple or a list of four coordinates jus givim the minimum and maximum x and y coordinates of the box or maybe something else, again, you have to choose your most sympathetic variant. Verify the function correctness by using the code from step 2 and instead of printing the triple print the output of the function which produces the coordinates of the bounding box. (Do it in small examples mainly). Do not store the bounding boxes anywhere yet.

Step 4. “Store bounding boxes”

Now the code produces the bounding boxes. To store them in a suitable data structure use the same loops (or part of the code) that were created in the previous step. There are more possibilities how to store bounding boxes (or just plain rectangles, for that matter). You may think of array of touples, arrays of arrays maybe about a separate array for each coordinate of a bounding boxes or maybe about some other way of storage. There is no general rule dictating what data have to be stored in what kind of data structure, so the choice is yours. You shoud opt for a variant which you are most comfortable with (even if you are afraid that it might be ineffective). Write an additional function (or a piece of code) which will separately print the contents of the data structure with the bounding boxes (not the same code as in the previous steps!). By doing this you will verify that the bounding boxes are stored corectly in your chosen data structure.

Step 5. “List pairs of bounding boxes”

Similarly to the step 2, print out all pairs of bounding boxes. If you were able to complete the step 2. you should also be able to complete this step because it is structurally even simpler. In Example 1 the number of pairs of bounding boxes should be 190, in Example 2 the number of pairs of bounding boxes should be 6. figure out theoretically how many pairs of bounding boxes should be there in Example 3. Do verify that the number 190 is correct by counting the bounding boxes in the output, either by hand or by implementing a counter. If you are not sure that there are exactly 190 bounding boxes in you output in Example 1, do not continue. Perform a similar check with Example 2 and Example 3.

Step 6. “Start comparing bounding boxes”

In this step, add to the printing of pairs of bounding boxes some calls of functions each of which will actually compare two bounding boxes in a given pair. For the start, it is enough to create just three functions, F1, F2, F4 (In your code, name the functions more appropriately). Each function will return True or False. F1 will decide if two bounding boxes are identical. F2 will decide if any of the two bounding boxes lies in the interior of the other bounding box. F4 will return True if and only if the two bounding boxes share no common point. You have to implement a few elementary geometrical considerations comparing the relative positions of bounding boxes, be careful to use strict and non-strict inequalities properly. Print the output of each function together with the print of the bounding boxes themselves. Draw manually the points in the plane and at least some the bounding boxes in Example 1 to verify that your functions are correct. At this moment, your solution of the problem is close to completion. The code compares pairs of bounding boxes as demanded and prints the results of comparisons.

Step 7. “Finish comparing bounding boxes”

There are no more structural changes to add to the code now. All that remains is to implement Functions F3, F5, F6, F7 and F8 which will perform checks specified in cases 3,5,6,7,8 in the assignement. After completing step 6, this should be more or less just an exercise in geometry and careful formulation of conditions in the code. When all functions are written and verified on small examples comment out all prints creaded in previous steps and produce only the requested 8 lines of output. Compare your results with the public data.

Concluding remarks

The sequence of steps described above is not obligatory. Anybody can modify it for their own purposes or solve the problem in a different way according to their experience and understanding of programming, algorithms, data structures and Python language specifics. Also, it should be obvious that the solution method described here is not the very optimal one (if any optimal method exists, at all). Nevertheless, when implemented correctly it should be reasonably effective, provided that the expected complexity of the solution is O(N^6), where N is the number of input points. There are methods in computational geometry which would allow to drastically reduce the complexity of the task down to maybe even O( N * log(N)), but those methods are somewhat more advanced and their implementation is not expected here.