For this assignment, you are to once again write, run, and debug a C program. This program does a little calculation using high school geometry. You will turn in the source code of your program to Moodle. Please remember to put in a comment on the first line of your program telling me the class (CS 539), the assignment number (HW #1), and your name.
Your job is to write a C program that includes a function called inTriangle. Your inTriangle function’s header must match mine exactly (so that I can use your inTriangle function with my main program if I want). Your function prototype should precede main, and your function definition should follow main. The comments in the following code (which you don’t have to reproduce) explain what the function is supposed to return.
int inTriangle( double x0, double y0, double x1, double y1,
double x2, double y2, double xp, double yp )
{
// Is the point (xp, yp) on the interior of the triangle made up of three
// points (x0, y0), (x1, y1), (x2, y2)? We return 0 or 1 for no or yes.
// (If the point is exactly on the triangle, we return 0)
// For instance, if the args were
// (1.0, 1.0, -1.0, -2.0, 3.0, 2.0, 0.5, -0.4)
// we would return 1, since the triangle made up of points
// (1.0, 1.0), (-1.0, -2.0), and (-2.0, 3.0) encloses the point
// (0.5, -0.4), but if the args were
// (1.0, 1.0, -1.0, -2.0, 3.0, 2.0, 0.5, -0.6)
// we would return 0, since that same triangle does not enclose the point
// (0.5, -0.6).
// The three points of the triangle may appear in any order.
For this assignment, you don’t have to worry about floating point overflow, and you don’t have to worry about the tiny round-off errors that occur when the CPU does floating-point calculations.
Your main program should input (with a prompt) the coordinates of three points defining a triangle. Then, as many times as the user wants, input the coordinates of a point and say whether that point is on the interior of the triangle. You’ll use the same triangle for each point, so the coordinates for the triangle vertices only need to be entered once. Use input failure as the loop termination condition. An example run may go as
6 coords for 3 vertices of triangle: 1 1 -1 -2 3 2
Now input coordinate pairs of points to test, non-# to quit.
x y: 2 1.4
in
x y: 2 1.6
not in
x y: blah
Suppose we have a line determined by two points; and in addition we have two more points. We want to know whether the two additional points are on the same side of the line or not.
Let the two points that determine the line be (X0, Y0) and (X1, Y1). Let the two additional points be (XA, YA) and (XB, YB).
The first thing we need to do is find the equation for the line passing through points (X0, Y0) and (X1, Y1). Let
an arbitrary point on that line be (X, Y). Then we use the fact that on a line, the slope (that is, rise/run ) between any two points on the line is the same:
(Y_1-Y_0)/(X_1-X_0 )=(Y_0-Y)/(X_0-X)
Cross-multiplying gives
(Y1-Y0)(X0-X) = (Y0-Y)(X1-X0)
Multiplying out and rearranging gives
(Y0-Y1)X + (X1-X0)Y + (X0Y1-X1Y0) = 0
Now this is an interesting equation. First, we can check the algebra we’ve done so far by substituting X0 for X and Y0 for Y: of course the resulting equation should be true, since the point (X0, Y0) is on the line connecting points (X0, Y0) and (X1, Y1). If you do this substitution, you’ll see that, sure enough, the equation then simplifies to 0 = 0. Likewise, we can substitute X1 for X and Y1 for Y: the resulting equation also simplifies to 0 = 0, as it should. I like to be able to check my algebra, since algebra mistakes are so easy to make.
Also, note that the equation has no division (even though we used division in deriving the equation). That means that division by 0 is not a possibility, so we don’t have to worry about special handling of cases like vertical lines.
Furthermore, look what happens if the points (X0, Y0) and (X1, Y1) are the same point (that is, if X0 = X1 and Y0 = Y1). You can convince yourself that the equation is then true, regardless of the values of X and Y (because each of the three parenthesized expressions in the “interesting equation” is 0). This turns out to be very convenient for us, since it means that if the user gives us a degenerate case with 2 points the same, it’s impossible for two additional points to be on the same side of the resulting “line”. (Yeah, mathematicians really do use the word “degenerate” to describe cases like this.)
But the best thing about this equation is that if we substitute values for X and Y, we learn more than whether (X, Y) is on the line. Sure, if the left side of the “interesting equation” is 0, then the point is on the line, and if it’s non-zero it’s off the line – but more important to us is the fact that if the left side of the equation is positive, then the point is on one side of the line, and if it’s negative, then it’s on the other side.
So suppose we now want to know whether (XA, YA) and (XB, YB) are on the same side of the line determined by points (X0, Y0) and (X1, Y1). We substitute XA for X and YA for Y in the left side of the interesting equation to get the value
(Y0-Y1)XA + (X1-X0)YA + (X0Y1 – X1Y0)
Then likewise, we substitute XB for X and YB for Y to get the value
(Y0-Y1)XB + (X1-X0)YB + (X0Y1 – X1Y0)
If these two values are both positive or both negative, then the points (XA, YA) and (XB, YB) are on the same side of the line. If one is negative and the other positive, they are on opposite sides of the line. If either value is zero, then the corresponding point is exactly on the line.
Now that we know how to tell whether two given points are on the same side of a given line, it’s pretty easy to use this to determine whether a given point is on the interior of a given triangle. Life is simple again.