The line clipping is a process in which we can cut the part of the line, which lies outside the view pane. Only those lines are visible, which lie inside the view pane.

The
line clipping process is implemented by following line clipping algorithms**–**

**Cohen Sutherland Line Clipping Algorithm****Liang-Barsky Line Clipping Algorithm****Midpoint Subdivision Line Clipping Algorithm**

### Cohen Sutherland Line Clipping Algorithm

This
algorithm was named by **“Danny Cohen”** and **“Ivan Sutherland.”**

The algorithm will work in the following steps:

- In this algorithm, we will divide the view pane into nineequal segments (as shown in the below figure) that only serve the viewport.
- Now, we will represent the top, bottom, left, and right corner of the window with 4 bits. This 4bit can be described with the following point that:
- If an object lies within any particular corner position, that corner value will be 1, else it will be 0.
- The
allocation of bits depends on
**“TBRL”**(Top, Bottom, Right, Left) rule. - Suppose, if the point of a line appears in the top-left corner, then according to TBRL, the value is 1001. We will allot the bits as-
- For the top corner, because the object is present at the top corner.
- For the bottom corner, because the object does not lie at the bottom.
- For the right corner, because the object does not lie at the right side.
- For the left corner, because the object lies at the top-left corner.
- In this way, we check TBRL for each segment and allot the bits accordingly.

In Cohen- Sutherland Algorithm we will divide the lines into following Sections-

**Visible Line:**When both points (starting and ending) of the line are entirely situated inside the window.**Invisible Line:**When both points (Starting and ending) of the line are completely situated outside the window.

If we have (x_{min}, x_{max})
and (y_{min}, y_{max}) coordinates of the view pane (window).

Then, it should be described as-

x_{0}, x_{1 }> x_{max}

y_{0}, y_{1 }> y_{max}

x_{0}, x_{1 }< x_{min}

y_{0}, y_{1 }< y_{min}

**Clipped Line:**Everyline has two endpoints. Let (x_{0, }y_{0}) and (x_{1, }y_{1}) are points of the line. If one point of the line situated inside the window and the other one is outside the window, then the line is known as Clipped Line.

### Algorithm of Cohen-Sutherland Line Clipping:

**Step
1: **Assign the bit code for both endpoints of the
line.

**Step
2: **Now,implement OR operation on both
endpoints of the line.

**Step
3: **If the OR = 0000,

Then

{The line is acceptable (Visible)}

Else

{Implement AND operation on endpoints}

Then

** **If AND ≠ 0000

Then

** **{The line is not
acceptable (Invisible)}

Else

AND = 0000

{The line needs to be clip}

**Step
4: **If a line needs to be clipped, first find an
intersection point of all boundaries with the following formula-

m = (y_{1}-y_{0}) (x_{1}-x_{0})

**Step
4.1: **When the line intersects the left side boundary
of the window port.

y_{0 }= y_{1}+ m(x-x_{1})

Here x = xw_{min }(Minimum
value of x coordinate)

**Step
4.2: **When the line intersects the right-side
boundary of the window port.

y_{0 }= y_{1}+m(x-x_{1})

Here x = xw_{max }(Maximum
value of x coordinate)

**Step
4.3:** When the line intersects Top side boundary of
the window port.

** **x_{0
}= x_{1}+(y-y_{1})/m** **

** **Here
y = yw_{max }(Maximum value of y coordinate)

**Step
4.4: **When the line intersects the bottom side
boundary of the window port.** **

**
**x_{0 }= x_{1}+(y-y_{1})/m

** **Here
y = yw_{min }(Minimum value of y coordinate)

**Example:
**In the below-mentioned example, we have
different lines. The different category of the line-

Line AB is a clipped case.

The line CD is completely visible.

Line EF is completely invisible.

Line GH is a clipped case.

Line KL is completely invisible.

Line IJ is a clipped case.

The endpoints of lines are lies as follows-

A → 0000

B → 1010

C → 0000

D → 0000

E → 0100

F → 0100

G → 0001

H → 0000

I → 0000

J → 0010

K → 1000

L → 1000

**Advantages:**

- It is easy to use and implement.
- We can perform clipping and testing in a particular manner.
- It is a fast algorithm.

**Disadvantages:**

### Liang-Barsky Line Clipping Algorithm:

The algorithm was introduced by **“You-Dong
Liang”** and **“Brian A. Barsky.”** It is used for line clipping. It is a
more powerful algorithm than the Cohen-Sutherland algorithm.

### We use the following concepts in this algorithm-

- We can use the parametric equation of line and inequalities.
- These are used to describe the range of windows to find out the intersection points between the line and the clipping window.
- The parametric
line is also known as
**“Cyrus-Beck.”**

In this algorithm, we have to find the intersection point based on a time interval.

**Time interval**
(**t**) can be defined as travelling time between initial position (0) to
final position (1). Then we have,

**0 < t < 1 **(Here,
t lies between 0 and 1)

We have the formula to find x and y points of the line-

**x=
x _{1 }+ t. **

**▲**

**x**(For point x)

**y=
y _{1 }+ t. **

**▲**

**y**(For point y)

To check that the point lies between the window or outside the equation is-

**Xw _{min
}<= x_{1 }+ t. **

**▲**

**x <= Xw**

_{max}**Yw _{min
}<= y_{1 }+ t. **

**▲**

**y <= Yw**

_{max}These two conditions can be written as-

**x _{1
}+ t. **

**▲**

**x >= Xw**

_{min}**x _{1
}+ t. **

**▲**

**x <= Xw**

_{max}**y _{1
}+ t. **

**▲**

**y >= Yw**

_{min}**y _{1
}+ t. **

**▲**

**y <= Yw**

_{max}We can take a common expression for above four conditions. It will be-

**t.p _{k
}<= q_{k }**(Here the value of k is multiple)

**t
= q _{k }/ p_{k}**

** p _{1 }= **–

**▲**

**x q**(For left boundary)

_{1 }= x_{1 }– xw_{min }** p _{2 }= **

**▲**

**x q**(For right boundary)

_{2 }= xw_{max }– x_{1}** p _{3 }= **–

**▲**

**y q**(For bottom boundary)

_{3 }= y_{1 }– yw_{min }** p _{4 }= **

**▲**

**y q**(For top Boundary)

_{4 }= yw_{max }– y_{1}

_{ }### Algorithm of Liang-Barsky Line Clipping:

**Step
1: **Set the endpoints of the line **(x _{1},
y_{1})** and

**(x**

_{2}, y_{2}).**Step
2: **Calculate the value of **p _{1}, p_{2},p_{3}, p_{4 }**and

**q**

_{1}, q_{2}, q_{3},q_{4}.**Step
3: ** Now we calculate
the value of **t**

** t _{1 }= 0 (For initial
point)**

** t _{2 }= 1 (For final
point)**

**Step
4: **Now, we have to calculate the value of **p _{k
}**and

**q**

_{k}** **If

**p _{k }**=

**0**

** **then

{The line is parallel to the window}

**
**If

** Q _{k }< 0**

** **then

{The line is completely outside the window}

**Step
5: **If we have non zero value of **p _{k }**–

** _{ }**If

**p _{k }< 0**

then

**t _{1 }= max (0,
q_{k }/ p_{k})**

If

**p _{k
}> 0**

** **then

** t _{2 }= min (1, q_{k
}/ p_{k})**

Now,
if **t _{1 }< t_{2 }{**If

**t**value is changed

_{1}** **Then
the first point is outside the window.

** _{ } **If

**t**value is changed

_{2 } Then the second point
is outside the window**}**

else

**t _{1 }> t_{2}**

then

{Line is completely outside the window}

**Step
6:** Stop.

**Example:
**

Let a rectangular window size with (5, 9). The points of the line are (4, 12) and (8, 8). Use the Liang- Barsky algorithm to clip the line and find the intersection point.

**Solution:
**

We have,

The
initial point of the line (p_{1}) = (4, 12)

The
ending point of the line (p_{2}) = (8, 8)

x_{1 }= 4, x_{2 }= 8

y_{1 }= 12, y_{2 }= 8

xw_{min
}= 5, xw_{max }= 9

yw_{min
}= 5, yw_{max }= 9

**Step
1: **We have to calculate the value of **▲****x **and**▲****y-**

** ****▲****x = **x_{2}–
x_{1}= 8-4 = 4

**▲****y
= **y_{2}– y_{1}= 8-12 = -4

**Step
2:** Now, we will calculate-

p_{1 }= -4 q_{1 }= 4-5 = -1

p_{2 }= 4 q_{2 }= 9-4 = 5

p_{3 }= 4 q_{3 }= 12-5 = 7

p_{4 }= -4 q_{4 }= 9-12 = -3

**Step
3: **Now we will calculate t_{1 }value**– **

If
p_{1}, p_{4 }< 0

Then
t_{1 }=max (0, q_{k }/p_{k})

_{ }=max (0, q_{1 }/p_{1}, q_{4 }/p_{4})

=max (0, 1/4, 3/4)

t_{1} = 3/4

If
p_{2}, p_{3 }> 0

Then
t_{2 }= min (1, q_{k }/p_{k})

= min (1, q_{2 }/p_{2},
q_{3 }/p_{3})

= min (1, 5/4, 7/4)

t_{2} = 1

**Step
4: **Now, we have to calculate the intersection
point.

x = x_{1 }+ t_{1. }▲x= 4+ 3/4 * 4 = 7

_{ }y
= y_{1 }+ t_{1. }▲y= 12+ 3/4 *(-4) = 9

**The
coordinates intersection point = (7, 9)**

### Midpoint Subdivision Line Clipping Algorithm:

The midpoint subdivision algorithm is used to clip the line. The algorithm is based on finding the midpoint of the line. We can divide the line into two equal parts. There should be following categories of the line-

**Visible
line **

_{ }**Invisible line**

**Partially
visible**

We can calculate the midpoint of the line by the following formula-

**p _{m
}= (p_{1 }+ p_{2})/2**

### Algorithm Midpoint Subdivision Line Clipping:

**Step
1: **Assign the bit code for both endpoints of the
line.

**Step
2: **Now,implement OR operation on both
endpoints of the line.

**Step
3: **If the OR = 0000,

Then

{The line is Visible}

Else

{Implement AND operation on endpoints}

Then

** **If
AND ≠ 0000

Then

** **{The
line is Invisible}

Else

AND = 0000

{The line is the partially visible}

**Step
4:** For
partially visible line, we need to find the midpoint.

**X _{m }= (x_{1 }+
x_{2})/2 (For x coordinate)
**

** Y _{m }= (y_{1 }+ y_{2})/2
(For y coordinate)**

**Step
5: **Weneed to check that the line is near
to the boundary of the window or not.

**Step
6: **If the line is visible or invisible, then
repeat steps 1 to 5.

**Step
7: **Stop.

**Example:
**A window contains the size (0, 50, 0, 50). A
line PQ has the coordinates (-10, 40) and (30, -20). Find the visible point of
the line using midpoint subdivision.

**Solution:
**We have,

The coordinates for x and y = P (-10, 40)

The coordinates for x and y = Q (30, -20)

Now,

**Step
1: **We have to compute the midpoint of the line
segment PQ.

Q = [(-10 + 30) /2, (40 – 20)/2]

= (10, 10)

**Now
the new coordinates of Q = (10, 10)**

**Step
2: **Now, we will find

Q’’ = midpoint of the Q’ and Q

Q’’ = [(10 + 30) /2, (10 + (-20))/2]

** = **(20, -5)

**Now
the new coordinates of Q’’ = (20, -5)**

Here (20, -5) is much better than (10, 10)

Now we have to find Q’’’ then,

Q’’’ = [(20 + 30) /2, (-5 + (-20))/2]

= (25, -12.5)

**Now
the new coordinates of Q’’’ = (25, -12.5)**

We can clip the line from Q’’ to Q from the top side.

**Step
3: **Now, we will take left hand side part. The
endpoints are P and Q’’’

We will find the midpoint of P and Q’’’

P (-10,40) and Q’’’ (25, -12.5)

P’ = [(-10 + 25) /2, (40 + (-12.5))/2]

= (7.5, 27.5)

Now we will find the midpoint of P and P’’

P (-10, 40) and P’ (7.5, 27.5)

P’’ = [(-10 + 7.5) /2, (40 + (27.5))/2]

= (-1.25, 33.75)

Now we will find midpoint of P’’ and P

P’’’ = P (-10, 40) and P’’ (-1.25, 33.75)

= [(-10 + (-1.25)) /2, (40 + 33.75)/2]

= (5.62, 36.87)

Now we will clip the line from P to P’’’

Finally, we have P’’’ = (5.62, 36.87)

Q’’’ = (25, -12.5)