1. Find the implicit, explicit and parametric equations of the line that passes through the two points (4,2) and (6,8).
The equation of the line is (y - 2) / (8 - 2) = (x - 4)/(6 - 4) ie, (y-2)/6 = (x-4)/2 Implicit: Cross multiplying we get: 2y - 4 = 6x - 24 Rearranging: 6x - 2y = 20 or 3x - y = 10. Explicit: Rearranging again: y = 3x - 10. Parametric: x(t) = 4 + (6-4)t = 4 + 2t y(t) = 2 + (8-2)t = 2 + 6t
2. Find only the implicit equation of the line that passes through (5,1) and (10,6).
The equation is (y - 1)/(6-1) = (x-5)/(10-5) or (y-1)/5 = (x-5)/5, and multiply through by 5 to give: y-1 = x-5. Rearranging: x - y = 4.(a) By making use of the parametric equation of the line in question 1, find its intersection point with the line in this question.
Where the two lines intersect, we must simultaneously satisfy all requirements: x(t) = 4 + 2t and y(t) = 2 + 6t for the first line, and x-y=4 for the second. Hence if (x(t), y(t)) is a point on the first line, for it to also be on the second: x(t) - y(t) = 4, and therefore (4 + 2t) - (2 + 6t) = 4. Rearranging gives: -4t = 2, so that t = -1/2. The lines meet where t= -1/2 on the first line, and the corresponding point is therefore: x(-1/2) = 3, and y(-1/2) = -1, ie, at the point (3,-1). As a check, we see that this does satisfy the equation x - y = 4.(b) Two distinct lines will always intersect (unless they are parallel). However, two line segments might not intersect. Does the line segment of 1. intersect the line of this question?
No it does not, since the line segment corresponds to the range of t values between 0 and 1. Here t < 0.
3. Suppose (x1,y1) and (x2,y2) defines a line segment. Consider the left boundary of the clipping region x = Wxmin.
(a) Specify the visible side of the boundary.
The visible side is specified as x >= Wxmin.(b) Construct a test to find whether both end-points are on the invisible, or both on the visible side of the boundary, or whether one point is one side and the other is the opposite side.
if(x1 < Wxmin) {
if(x2 < Wxmin) /*both on invisible side*/
else {/*p1 on invisible side and p2 on visible side*/
}
else{ /*x1 >= Wxmin*/
if(x2 >= Wxmin) /*both on visible side*/
else {/*p1 on visible side and p2 on invisible side*/}
}
(c) Find the intersection of the the line segment with the boundary, if any.
The line segment has parametric equation x(t) = x1 + t.dx, y(t) = y1 + t.dy where dx = x2-x1 and dy = y2 - y1. The equation of the boundary is x = Wxmin. Therefore where the line meets the boundary: x1 + t.dx = Wxmin, and t = (Wxmin - x1)/dx. Therefore the intersection of the line with the boundary is at: ( Wxmin, y1 + (dy/dx)(Wxmin - x1) ) The line segment only intersects the boundary provided that 0 <= t <= 1.
4. Suppose the window is defined by 1.0 ² x ² 2.0, 0.1 ² y ² 1.1, and the viewport is 0 ² x ² 200, 100 ² y ² 300. Find the point in the viewport corresponding to the point (1.1,0.8) in the window. In general write down the function wc2dc for this particular arrangement.
Let the point in DC be (x',y'). Then, x' = 0 + (200/1)(x - 1) = 200(x-1) y' =100 + (200/1)(y-0.1) = 100 + 200(y-0.1) = 80 + 200y Therefor the point (1.1,0.8) corresponds to x' = 200*(1.1-1) = 20 y' = 80 + 200*0.8 = 240 So the DC point is (20,240).
5. A trapezium is a four-sided shape, with top and bottom sides horizontal. For example, it would have coordinates (going round anti-clockwise from the bottom left corner): (x1,y1), (x2,y1), (x3,y2), (x4,y2). In this case x1 < x2, and y2 > y1.
(a) Construct a line clipping algorithm for the trapezium as clipping region.
A trivial reject test is possible for each of the horizontal boundaries. For the side boundaries a trivial reject test is possible by checking to see if both line end-points are to the left of the the left-most x-coordinate or the right of the right-most x-coordinate of the two boundaries. A trivial accept test is possible in a similar manner (except that the end points would have to be above the lower horizontal boundary, below the horizontal boundary, and between the two inner x-coordinates of the other two boundaries). These are not fool-proof trivial reject/accept tests - ie, it is possible that both end-points are to the left of the left most boundary, but not rejected by the test described here. To compute intersections is easy for the horizontal boundaries. For the other two boundaries we can follow the method of question 2. above. Suppose a boundary of the clip region has equation l(x,y) = ax + by - c = 0. The intersection bewteen the line and the clip edge can be computed by representing the line parametrically x(t) = x1 + tdx, y(t) = y1 + tdy and substituting into ax + by - c = 0, and solve for t.(b) Construct a polygon clipping algorithm on the lines of Sutherland-Hodgman for such a clipping region.
The S-H algorithm can be carried out almost exactly as usual (for a rectangular clipping region) except that for the non-horizontal boundaries we have to determine the relationship between a polygon edge and the boundary. We can use the fact that l(x,y) > 0, when (x,y) is in "front" front of the edge, < 0 behind it, = 0, on it. This can be used to determine the relationship between the polygon edge and the clip edge, as is required in the S-H algorithm. For example, given the edge (x1,y1) to (x2,y2), suppose l(x1,y1) < 0 and l(x2,y2) < 0 then both end-points are on the invisible side. l(x1,y1) > 0 and l(x2,y2) > 0 then both end-points are on the visible side. l(x1,y1) < 0 and l(x2,y2) > 0 then the edge is entering the visible side, and so on.*6. A simple polygon is one where no edges intersect (except at vertices). Show (with diagrams) that any simple polygon can be decomposed into a set of triangles and trapezia. Use this and your previous results to construct an efficient line clipping algorithm for a simple polygon.
**7. Consider a polygon with a hole. This can be easily specified as an outer polygon with vertices going say clockwise, and an inner polygon with vertices anti-clockwise, and where the inner polygon is completely contained within the boundaries of the outer one. Assume that the two polygons are convex.
(a) Using the non-zero winding number rule as the inside test show that this really does specify a polygon with a hole.
(b) Can the Sutherland-Hodgman algorithm be extended to cover such a polygon used as a clipping region?