Rendering Triangles --------- --------- In order to produce a picture, computer algorithms often divide surfaces up into triangles each with its own color. The triangles are then inserted into the image, starting with triangles representing surface parts that are farthest from the viewer, so that if two triangles overlap, the nearer covers the overlapping part of the farther triangle. This problem asks you to do this for a simplified case. The image consists of MxN pixels that are assigned integer coordinates from (0,0) through (M-1,N-1). The triangle vertices have integer coordinates, with vertex (x,y) corresponding to pixel (x,y). The triangle colors are simply upper case letters. The pixels correspond to characters in a set of N lines each of M characters, so the image can be easily printed. Each pixel prints as its color. The period `.' is used to denote white, so the position of a white pixel can be easily ascertained. A pixel is painted with the color of a triangle if the pixel is inside OR ON THE BOUNDARY of the triangle. To simplify the problem, no two triangles will have the same color, and colors earlier in the alphabet are for triangles farther from the observer. That is, if a pixel receives several colors, it remembers only the one that is latest in the alphabet. Remark: This is the classical rendering problem solved by graphics hardware. However, the hardware has to deal with many more pixels and triangles than we do here. So the hardware needs more efficient algorithms than you need here. Input ----- For each of several test cases, first a line with three integers, M, N, and T in that order, and then T lines each describing a triangle. Here 0 < M,N <= 50; 1 <= T <= 26. Each of the triangle description lines has the format C X1 Y1 X2 Y2 X3 Y3 where C is an upper case letter giving the color of the triangle, and (X1,Y1), (X2,Y2), (X3,Y3) are the vertices of the triangle. All vertex coordinates are integers, but they may be outside the ranges 0..M-1 or 0..N-1, i.e., the vertices may be outside the image. Input numbers and color characters are separated by whitespace. No two triangles have the same color. Input ends with an end of file. Output ------ For each test case, an empty line, followed by N lines each of M characters. Pixel (x,y) corresponds to the x+1'st character of the y+1'st line, where 0 <= x < M and 0 <= y < N. If the pixel has a color, the character is the color letter. If the pixel has no color, the character is the period `.'. The first output line is empty. There are no whitespace characters in any output line. Note that (0,0) is the UPPER left pixel and (M-1,N-1) is the LOWER right pixel. Sample Input ------ ----- 40 6 8 A 0 0 5 5 10 0 B 5 0 10 5 15 0 C 10 0 15 5 20 0 D 15 0 20 5 25 0 E 20 0 25 5 30 0 F 25 0 30 5 35 0 G 30 0 35 5 40 0 H 35 0 40 5 45 0 6 6 4 B -8 -10 12 10 12 -10 C -15 20 22 -20 22 -18 A -12 -10 8 10 -12 10 D 4 6 7 3 7 6 Sample Output ------ ------ [The first output line is empty.] AAAAABBBBBCCCCCDDDDDEEEEEFFFFFGGGGGHHHHH .AAAAABBBBBCCCCCDDDDDEEEEEFFFFFGGGGGHHHH ..AAAAABBBBBCCCCCDDDDDEEEEEFFFFFGGGGGHHH ...AAAAABBBBBCCCCCDDDDDEEEEEFFFFFGGGGGHH ....AAA..BBB..CCC..DDD..EEE..FFF..GGG..H .....A....B....C....D....E....F....G.... ..BBCB ...CBB A.C.BB AC...B CAA... AAAA.D File: render.txt Author: Bob Walton Date: Tue Oct 10 08:54:58 EDT 2006 The authors have placed this file in the public domain; they make no warranty and accept no liability for this file. RCS Info (may not be true date or author): $Author: walton $ $Date: 2006/10/10 12:56:35 $ $RCSfile: render.txt,v $ $Revision: 1.6 $