# CPSC 231 Assignment 1: Analytic Geometry

\$30.00

## Description

In this assignment, you will use elements of the Python programming language including, variables, expressions,
statements, functions, and conditional expressions. While the assignment does not require you to use more than this,
you may use additional features of Python as you like.
Finding Intersections with Analytic Geometry
Analytical geometry, geometry embedded in a coordinate system, is fundamental to computer graphics and physics
simulation (both key elements of video games). You will write a program that computes and displays the intersection
of a line segment with a circle. This is a simplification of a common operation in video games, i.e., casting a ray
that represents a line of sight (the line segment) to determine if an object (the circle, or sphere in three dimensions)
blocks the line of sight.
Figure 1(a) shows one way to describe a line. Two points with coordinates (x1, y1) and (x2, y2) define the direction
and position of the line. Given these two points, the parameter α defines the position of points along the line:
x = (1 − α)x1 + αx2 (1)
y = (1 − α)y1 + αy2. (2)
Note that α = 0 corresponds to (x1, y1), α = 1 corresponds to (x2, y2), 0 < α < 1, corresponds to the points between (x1, y1) and (x2, y2), and other values of alpha correspond to points on either end of the line segment. Figure 1(b) shows the three possible situations that can arise when finding the intersection of a line with circle: no intersection, one point of intersection when the line is tangent to the circle, and two points when the line cuts through the circle. Let (xc, yc) be the centre of a circle with radius r. We can find if and where the intersections occur by solving the quadratic aα2 + bα + c = 0 where a = (x2 − x1) 2 + (y2 − y1) 2 (3) b = 2[(x1 − xc)(x2 − x1) + (y1 − yc)(y2 − y1)] (4) c = (x1 − xc) 2 + (y1 − yc) 2 − r 2 . (5) Solutions are given by the (what should be familiar) quadratic formula: α = −b ± √ b 2 − 4ac 2a . When b 2 − 4ac < 0, α is complex and the line does not intersect the circle. When b 2 − 4ac = 0, there is exactly one solution corresponding to the point where the line touches the circle tangentially. When b 2 − 4ac > 0, there are two
real solutions corresponding to the intersection points when the line cuts through the circle. Note that if α < 0 or α > 1, the line intersects the circle, but not between (x1, y1) and (x2, y2).
Instructions
Write a program to do the following.
(x1
,y1
)
(x2
,y2
)
α < 0 α = 0 α = 1 0 < α < 1 α > 1
(x
c
,y
c
)
r
(a) (b)
Figure 1: Lines and circles: (a) two points, (x1, y1) and (x2, y2), define a line and the parameter α defines a position
along the line, and (b) the ways in which a line intersects (or does not intersect) a circle.
1. Read in values for xc, yc, r, x1, y1, x2, and y2. Your program should be able to read the values from the
example input files when redirected to stdin.
2. Use the turtle graphics module to display the line segment and the circle.
3. Compute the positions of the intersections between the line segment and circle, and display them if they exist.
To get full marks, you must make effective use of conditional statements, comments, and functions. There are
examples of suitable displays in Figure 2 for the sample input files provided with the assignment.
1. You may, for this assignment, assume that we will test your program with properly formed four-line input files
containing
• xc, yc
• r
• x1, y1
• x2, y2
Thus, the following Python statement can read the first line of the file.
xc,yc = eval(input())
This is a risky way to handle input because your Python program will crash if the input is not properly formed
to match what is on the left-hand side of the assignment. However, you do not have the tools to do a better
job of input yet, so this simple approach will be sufficient for this assignment. You may also assume that all
input we test your program with will fit into a 800-by-600 pixel display.
2. So, when you run your program, the command will look something like this.