Mid Point Subdivision Line Clipping Algorithm

It is used for clipping line. The line is divided in two parts. Mid points of line is obtained by dividing it in two short segments. Again division is done, by finding midpoint. This process is continued until line of visible and invisible category is obtained. Let (x_i,y_i) are midpoint.

x₅lie on pointof intersection of boundary of window.

Advantage of midpoint subdivision Line Clipping:

It is suitable for machines in which multiplication and division operation is not possible. Because it can be performed by introducing clipping divides in hardware.

Algorithm of midpoint subdivision Line Clipping:

Step1: Calculate the position of both endpoints of the line

Step2: Perform OR operation on both of these endpoints

Step3: If the OR operation gives 0000

then

Line is guaranteed to be visible

else

Perform AND operation on both endpoints.

If AND ≠ 0000

then the line is invisible

else

AND=6000

then the line is clipped case.

Step4: For the line to be clipped. Find midpoint

X_m=(x₁+x₂)/2

Y_m=(y₁+y₂)/2

X_m is midpoint of X coordinate. Y_m is midpoint of Y coordinate.

Step5: Check each midpoint, whether it nearest to the boundary of a window or not.

Step6: If the line is totally visible or totally rejected not found then repeat step 1 to 5.

Step7: Stop algorithm.

Example: Window size is (-3, 1) to (2, 6). A line AB is given having co-ordinates of A (-4, 2)and B (-1, 7). Does this line visible. Find the visible portion of the line using midpoint subdivision?

Solution

Step1: Fix point A (-4, 2)

Step2: Find b"=mid of b' and b

So (-1, 5) is betterthan (2, 4)

Find b"&bb"(-1, 5) b (-1, 7)

So B""to B length of line will be clipped from upper side Now considered left-hand side portion

A and B""are now endpoints

Find mid of A and B""

A(-4, 2) B""(-1, 6)