Introduction
Being able to determine to which side of a line a point lies is crucial in computer graphics. Mathematically, we can answer this question by filling in the coordinates of the point into the equation of the line.
(x-x1)(y2-y1) = (y-y1)(x2-x1)
Replacing x and y in this equation by a and b, if both sides are equal then we know (a,b) lies precisely on the line. If the left hand side is bigger than the right hand side, (a,b) lies to the left, and vice versa.
You can use the following skeleton file for this exercise session.
Exercises
Exercise 1: Clipping lines - determining whether two lines intersect
By using the above test, we can quickly determine whether or not two line segments intersect. Implement an algorithm that determines whether two line segments (defined by two points each) intersect or not. The algorithm must work for all cases. Make sure that border cases (no intersection or too many intersections) also work.
Exercise 2: Clipping lines - determining the intersection point
Determining the intersection point of two lines can be calculated using a mathematical formula. To calculate the point, it suffices to solve the following system of equations for x and y:
Implement the algorithm that determines the intersection point of two line segments. Demonstrate its correctness by drawing 100 lines at random on the screen, and by highlighting each intersection point in red. You can draw the lines by means of Processing's built-in line function. You chan change the color of pixels by calling stroke.
Exercise 3: clipping in the plane - the Cohen-Sutherland algorithm
The process of cropping figures to fit a certain window is called clipping. We assume our clipping window is given by a rectangle defined by the opposite corners (a,b) and (c,d) where a < c and b < d. A point (x,y) lies inside of the window when:
a <= x <= c and b <= y <= d
For a line segment, the situation is more complex, because there are multiple outcomes (the segment may lie entirely within the window, entirely outside of the window or partially within the window). An efficient algorithm to determine whether a line segment lies within a clipping window is that of Cohen-Sutherland.
In the figure below, consider the rectangle with opposite corners (a,b) and (c,d). By extending the sides of this rectangle, we divide the plane into 9 regions. The Cohen-Sutherland algorithm assigns a binary code to each region consisting of 4 bits. Each bit indicates whether a point in that region lies to the left, right, below or above the clipping window:
| 4 | 3 | 2 | 1 |
| below | above | right | left |
For example, a point corresponding to the code 0100 lies below the clipping window. A point corresponding to the code 0101 lies below and to the left of the clipping window. Points with code 0000 lie inside of the clipping window. The algorithm assigns such a code to each of the two endpoints of the line segment we are about to clip. We can then make the following case analysis:
- The segment lies entirely within the clipping window if the codes of both endpoints is 0000.
- The segment lies entirely outside of the clipping window if the codes of both endpoints have a 1-bit at a corresponding index in their code.
- In the remaining case, the segment lies either outside of or partially within the clipping window. To clip the segment, we systematically compare the line defined by the segment with each of the lines that bound the clipping window.
Consider for example the segment EF. The code for E is 1001 and the code for F is 0100. The codes are not 0000 and the logical AND is 0000, so we need to investigate further. E's code indicates that E lies to the left of the window. We therefore determine the intersection point between the line defined by EF and the left boundary line of the window. Determining this point is easy: it suffices to insert the x-coordinate of the boundary line into the equation of the line determined by EF. The intersection point E1 has code 0000. We then replace E by E1 and recursively try to clip the segment E1-F.
Again, the segment E1-F, neither lies completely inside nor outside of the clipping window. Since E1's code is 0000, we do not have to clip the segment at this endpoint anymore. Inspecting F's code reveals that it lies below the window. We therefore determine the intersection point between the line defined by EF and the bottom line bounding the clipping window. The intersection point F1 has code 0000. Recursively clipping E1-F1 reveals that both endpoints have code 0000, so E1-F1 lies within the clipping window and is the clipped version of EF. Try to replay this algorithm for the line segment GH.
Implement the above Cohen-Sutherland clipping algorithm. The input to the algorithm are the endpoints of a line segment and the corner points defining the clipping window. The output of the algorithm is either a clipped line segment or null if the segment lies entirely outside of the clipping window. Represent the 4-bit code of each endpoint as a single integer (not as 4 boolean flags). Test your algorithm by drawing a clipping window, a line segment and by highlighting the segment's clipped version.
Exercise 4: Point inside polygon (optional)
Try to develop an algorithm that checks whether a point lies inside (or on) a polygon. Does it work for border cases?
