An Example
Overlapping Rectangles
The Project Specification
Given the coordinates of two rectangles, create a program that can determine if they overlap.
The Program Specification
You need to answer the following questions before writing any code:
- What will the subroutine be called? Ensure your subroutine name is descriptive. e.g. doRectanglesOverlap()
- What arguments will the subroutine take? In this case it could be the x/y coordinates of all four corners, but the bottom-left and top-right coordinates are sufficient
- How will we pass the arguments into the subroutine?
- Eight scalars - ax1, ay1, ax2, ay2, bx1, by1, bx2, by2
- A list - [0,1,2,3,4,5,6,7] = ax1, ay1, ax2, ay2, bx1, by1, bx2, by2
- Two lists - [0,1,2,3], [4,5,6,7] = x1, y1, x2, y2 of each rectangle
- A dictionary - where the keys are the names of the coordinates (ax1, ay1, ax2, ay2, bx1, by1, bx2, by2).
- Two dictionaries - where the keys are the names of the coordinates (x1, y1, x2, y2) - one dictionary for each rectangle
a = { 'x1': 0, 'y1': 0, 'x2': 10, 'y2': 5 } - What will the subroutine return? We want the subroutine to return either true (if the provided rectangles overlap) or false (if they don't). In Python we will accomplish this by returning True or False.
Choose the test data
There is an infinite number of possible test cases
- You have to decide on the appropriate level of detail to test.
- You must be thorough and attempt to identify all categories of possible data, but you must decide how many examples for each category.
- We will design one test for each category in the image...
You must define the behaviour of edge cases
- Whether two rectangles touching count as an overlap depends on the specification and what the tool is being used for.
- Going through this process will help you determine the correct decision to make with edge cases before you start writing the code.
- We will say that rectangles with just edges touching do not overlap...
Write The Tests
- We create a dummy routine that returns some arbitrary value: 'BUG'
- Before each test we create our test data - in our case, we will create two dictionaries that model rectangles.
- We experiment with using Python at the command line to check the formatting
- We decide on the expected result for each test - in particular a decision must be made about the edge cases
- We add a comment to each test line as a description of the test. This makes reading the test output easier.
Once we have written our tests, we can run the code. At this point they will fail as we have not written the code yet.
#!/usr/bin/env python3
def doRectanglesOverlap(a, b):
""" Tests whether two rectangles overlap
>>> a = {'x1': 0, 'y1': 0, 'x2': 10, 'y2': 5}
>>> b = {'x1': 15, 'y1': 0, 'x2': 25, 'y2': 5}
>>> doRectanglesOverlap(a, b) # not overlapping, not touching
False
>>>
>>> a = {'x1': 0, 'y1': 0, 'x2': 10, 'y2': 5}
>>> b = {'x1': 5, 'y1': 3, 'x2': 15, 'y2': 13}
>>> doRectanglesOverlap(a, b) # one corner in the other rectangle
True
>>>
>>> a = {'x1': 0, 'y1': 0, 'x2': 10, 'y2': 5}
>>> b = {'x1': 5, 'y1': -3, 'x2': 15, 'y2': 8}
>>> doRectanglesOverlap(a, b) # two corners in the other rectangle
True
>>>
>>> a = {'x1': 1, 'y1': 0, 'x2': 11, 'y2': 10}
>>> b = {'x1': 0, 'y1': 1, 'x2': 12, 'y2': 9}
>>> doRectanglesOverlap(a, b) # overlapping, neither rectangle contains the other's corner
True
>>>
>>> a = {'x1': 0, 'y1': 0, 'x2': 10, 'y2': 10}
>>> b = {'x1': 1, 'y1': 1, 'x2': 9, 'y2': 9}
>>> doRectanglesOverlap(a, b) # one rectangle containing the other
True
>>>
>>> a = {'x1': 0, 'y1': 0, 'x2': 10, 'y2': 10}
>>> b = {'x1': 10, 'y1': 0, 'x2': 20, 'y2': 10}
>>> doRectanglesOverlap(a, b) # one edge touching
False
>>>
>>> a = {'x1': 0, 'y1': 0, 'x2': 10, 'y2': 10}
>>> b = {'x1': 10, 'y1': 10, 'x2': 20, 'y2': 20}
>>> doRectanglesOverlap(a, b) # one corner touching
False
>>>
"""
return('BUG')
if __name__ == "__main__":
import doctest
doctest.testmod()
[Download]
An Implementation
- By writing the tests we have designed an API and a complete specification of the subroutine.
- We know what the results should be when run on a wide range of data.
- This makes writing the subroutine much easier.
#!/usr/bin/env python3
def doRectanglesOverlap(a, b):
""" Tests whether two rectangles overlap
>>> a = {'x1': 0, 'y1': 0, 'x2': 10, 'y2': 5}
>>> b = {'x1': 15, 'y1': 0, 'x2': 25, 'y2': 5}
>>> doRectanglesOverlap(a, b) # not overlapping, not touching
False
>>>
>>> a = {'x1': 0, 'y1': 0, 'x2': 10, 'y2': 5}
>>> b = {'x1': 5, 'y1': 3, 'x2': 15, 'y2': 13}
>>> doRectanglesOverlap(a, b) # one corner in the other rectangle
True
>>>
>>> a = {'x1': 0, 'y1': 0, 'x2': 10, 'y2': 5}
>>> b = {'x1': 5, 'y1': -3, 'x2': 15, 'y2': 8}
>>> doRectanglesOverlap(a, b) # two corners in the other rectangle
True
>>>
>>> a = {'x1': 1, 'y1': 0, 'x2': 11, 'y2': 10}
>>> b = {'x1': 0, 'y1': 1, 'x2': 12, 'y2': 9}
>>> doRectanglesOverlap(a, b) # overlapping, neither rectangle contains the other's corner
True
>>>
>>> a = {'x1': 0, 'y1': 0, 'x2': 10, 'y2': 10}
>>> b = {'x1': 1, 'y1': 1, 'x2': 9, 'y2': 9}
>>> doRectanglesOverlap(a, b) # one rectangle containing the other
True
>>>
>>> a = {'x1': 0, 'y1': 0, 'x2': 10, 'y2': 10}
>>> b = {'x1': 10, 'y1': 0, 'x2': 20, 'y2': 10}
>>> doRectanglesOverlap(a, b) # one edge touching
False
>>>
>>> a = {'x1': 0, 'y1': 0, 'x2': 10, 'y2': 10}
>>> b = {'x1': 10, 'y1': 10, 'x2': 20, 'y2': 20}
>>> doRectanglesOverlap(a, b) # one corner touching
False
>>>
"""
if a['x1'] < b['x2'] and a['x2'] > b['x1'] and a['y1'] < b['y2'] and a['y2'] > b['y1']:
return True
return False
if __name__ == "__main__":
import doctest
doctest.testmod()
[Download]
Now that the subroutine is written you can run the tests again. If any tests fail you can alter the code so that the tests pass.