LearningOutcomes
On completion of this lesson you will know how to fill a shape with colour instead of drawing its outline.
Go to topFills
Download Program CodeIntroduction
Up to now we have defined shapes by drawing their outlines. Here we shall look at filling the shape with colour instead. To keep the code as simple as possible we shall concentrate on quadrilaterals only. Also we shall confine the quadrilaterals to those where the sum of their angles is equal to 360 degrees.
Our technique for filling the space occupied by a quadrilateral is to determine whether or not any pixel or point is or is not inside that space. If it is then we colour that pixel black.
But how do we determine if a pixel is or is not inside the quadrilateral? The answer is coordinate geometry.
In Fig 1 we have a quadrilateral with a point p outside. If we connect p with the four vertices of the quadrilateral we get the triangles PAB, PCD and PAD. Clearly the sum of the four triangles is greater in area than the quadrilateral itself.
In Fig 2 we have the exact same quadrilateral, but this time the point P is inside it. In this insistance it is clear that the sum of the triangles PAB, PCD and PAD is equal in area to that of the quadrilateral.
From the above observation we can determine that a point is outside a quadrilateral if the sum of the areas of triangles created by joining the point to the four vertices of the quadrilateral is greater than the area of the quadrilateral.
The inverse is also true, i.e. from a point inside a quadrilateral the sum of the areas of triangles created by joining the point to the four vertices of the quadrilateral is equal to the area of the quadrilateral.
All that we have said above about quadrilaterals, also apply to triangles.
Go to topAreas of Triangles and Quadrilaterals
There are numerous methods for calculating the area of a triangle. In our case, since we are dealing with the concepts of coordinate geometry, we shall use a method that uses only the coordinates of the vertices.
If a triangle has vertices of x1, y1, x2, y2, x3, y3 then the area of the triangle can be calculated as
area = (x1(y2 - y3) + x2(y3 - y1) + x3(y1 - y2))/2
This is very easily transferable to Python code as can be seen below.
def areaOfTriangle(x1, y1, x2, y2, x3, y3):
area = abs((x1 *(y2 - y3)+ x2*(y3-y1)+x3*(y1-y2))/2)
return area
Any quadrilateral can be broken up into two triangles simply by drawing one of the diagonals. Thus we can calculate a quadrilateral's area simply by calculating the sum of the areas of its constituent triangles. This is what we have done below.
def areaOfQuadrilateral(x1, y1, x2, y2, x3, y3, x4, y4):
area = abs((x1 *(y2 - y3)+ x2*(y3-y1)+x3*(y1-y2))/2) +abs((x1 * (y4 - y3) + x4 * (y3 - y1) + x3 * (y1 - y4))/2)
return area
In the two listings above if we compare lines 84 and 88 we see that the function areaOfQuadrilateral() have two arguments more than the function areaOfTriangle(). The extra pair are the coordinates of the fourth point of the quadrilateral.
Again comparing lines 85 and 89 we see that the sum of two areas are calculated at line 89 compared to one area at line 85. This is due to the fact that at line 89 we are calculating the areas of the two triangles that constitute the quadrilateral.
Go to topFilling in the shape
def fillShape(arr, shape, maxRows, maxCols):
x1 = shape[0][0]
y1 = shape[0][1]
x2 = shape[1][0]
y2 = shape[1][1]
x3 = shape[2][0]
y3 = shape[2][1]
x4 = shape[3][0]
y4 = shape[3][1]
AreaOfQuadrilateral = areaOfQuadrilateral(x1, y1, x2, y2, x3, y3, x4, y4)
for arrRows in range(maxRows):
AreaOfTriangles = 0
for arrCols in range(maxCols):
AreaOfTriangles += areaOfTriangle(arrRows, arrCols, x1, y1, x2,y2)
AreaOfTriangles += areaOfTriangle(arrRows, arrCols, x2, y2, x3,y3)
AreaOfTriangles += areaOfTriangle(arrRows, arrCols, x3, y3, x4,y4)
AreaOfTriangles += areaOfTriangle(arrRows, arrCols, x1, y1, x4,y4)
if AreaOfQuadrilateral == AreaOfTriangles:
arr[arrCols][arrRows]=1
AreaOfTriangles = 0
return arr
This is the new function that determines if a line is within the area of a quadrilateral or not, and enters a 1 into the appropriate element of the two dimensional list if it is.
Lines 62 to 69 extract the coordinates of the four points of the quadrilateral from the list argument shape and stores them as individual variables. Strictly speaking this is not necessary, but it allows for neater coding throughout the rest of the function.
At line 70 the area of the quadrilateral is calculated by a call to the function areaOfQuadrilateral() and the returned value is stored in the variable AreaOfQuadrilateral. That is the easy part.
The rest of the function simply scans all of the points on our 800 X 800 Cartesian plane.
For each point it determines whether that poin is inside our quadrilateral or not. For this it uses a nested for loop, the outer loop beginning at line 72 and the inner loop at line 74. Those values are temporarily held in the loop counters arrRows and arrCols
Lines 75 to 78 calculate the total area of the triangels formed from the point at arrRows and arrCols and each line of the quadrilateral
At line 79 the area of the quadrilateral is compared to the sum of the triangles. If they are the same value then 1 is put into the postion arr[arrCols][arrRows], otherwise no processing takes place.
At line 81 the value of AreaOfTriangles is set to zero, a new point in the plane is selected and the testing continues.
Once the entire plane has been searched the loops terminate and the processed array is returned to the calling function.
Go to topThe program controller
def main():
arrPage = []
strFileName="Filling"
intMaxCols=800
intMaxRows=800
arrPage = createBackground(intMaxCols,intMaxRows)
arrPage = fillShape(arrPage, [[250,350],[250,450],[550,450],[550,350],[250,350]], intMaxRows, intMaxCols)
saveFile(arrPage,intMaxRows, intMaxCols,strFileName)
if __name__ == "__main__":
main()
print("Programme finished")
This is the shortest version of the function main() so far. At line 112 it calls the function fillShape() and the processed data is returned and then saved by the call to saveFile() at line 113.
Summary
Filling in space to create a shape is an alternative to drawing its outline. The technique for implementing the filling is very different to that of drawing the outline.
To implement the filling we first determine the area of the shape to be filled in. Next we scan the surrounding Cartesion plane. For each point we draw a triangle using that point and a line from the shape. Once we have drawn triangles for all the sides of the shape, we add up their areas. If the sum of the areas is equal to the previously calculated area of the shape then the point is inside the shape area, otherwise it is outside of it.
Go to topExercises
Try out a few of the following variations on our program:
- Add two more horizontal bars to the image. Both will be the same size and will be half of the width and height of current bar. One should be placed exactly half ways between the current one and the top. The other should be placed half ways between the current one and the bottom. Both should be centered horizontally.
- Modify the original file so that the black bar in the centre is vertical instead of hourizontal. It shill should be centered both vertically and horizontally
- Draw two more vertical bars along with the one above. Like the first example they should be half the height and width of the original and should be placed on both sides of it, and half way between it and the vertical margins.