CPSC120 Assignment 5

Point in Triangle

In computer graphics surfaces are often represented using many triangles. Triangles are easier to render into images and with enough triangles curved surfaces can be approximated. In order to render a collection of triangles into an image that can be displayed, the computer repeatedly performs tests to determine if a point is inside a triangle.


Create a program that draws a triangle and a random point and tests if the point is inside the triangle. The program should draw a triangle that takes up the majority of the window. You can pick the location of each of the corners, or vertices, of the triangle. The program should also generate and draw a random point in the window. The color of the circle should be determined by whether the point is inside or outside the triangle.

A point is inside a triangle if it is on the interior side of all three edges of the triangle. For example, the point P in the illustration below is on the interior side of the edge from B to C and the edge from C to A, but it is not on the interior side of the edge from A to B.

It is possible to determine which side of an edge a point is on using the equation:

s = (V1x − V2x)(V1y − Py) − (V1y − V2y)(V1x − Px)

Where V1 and V2 are vertices that define an edge of the triangle, and P is a point. If the vertex V1 is clockwise from V2, then s will be positive if P is on the interior side of the line segment between V1 and V2. Note, it is possible to create one boolean statement that tests if the point is in the triangle, but it would be enormous and difficult to debug. A more simple way to write the program would be to create functions and variables for intermediary calculations.


Test: Submit your test files as a zip file on the course Inquire site by 9AM on Monday October 8th.

Code: Submit your code as a zip file on the course Inquire site by 5PM on Friday October 12th.


Monte Carlo Integration: It is possible to approximate the area of a triangle using Monte Carlo Integration. To calculate the area of the triangle using this technique, generate many random points in the window. Draw each random point and compute the total number that are inside the triangle and the total number that are outside the triangle. The triangle area is approximately the area of the window times the ratio of points inside the triangle to the total number of points.

Render: Use the point in triangle function to fill in the triangle. For every pixel in the window, test if the point corresponding to the pixel is in the triangle. If it is, draw a dot that is 1 pixel wide.