Theory of Computation & Computer Graphics — Two-Dimensional Transformation, NEC licence examination syllabus (Nepal Engineering Council).
Liang-Barsky Line Clipping: the algebra-based alternative
Same goal as Cohen-Sutherland, but works with parametric equations instead of region codes.
Liang-Barsky represents the line parametrically as P(t) = P₀ + t(P₁−P₀) for t between 0 and 1, then calculates the exact range of t where the line stays inside each of the four window boundaries.
Liang-Barsky core idea:
For each of the 4 boundaries (left, right, bottom, top), compute
a parameter value t where the line crosses that boundary.
Separate these into t-values that ENTER the window and t-values
that EXIT the window.
Final visible segment: t ranges from
max(0, all entering t-values) to min(1, all exiting t-values)
If this range is invalid (max > min), the line is entirely outside.
💡 One-liner: "Why is Liang-Barsky often considered more efficient than Cohen-Sutherland?" → It computes clip boundaries algebraically in a fixed number of steps, avoiding Cohen-Sutherland's potential for repeated intersection recalculations on lines that cross multiple boundaries.
The same line, the Liang-Barsky way
Clip the line from P₀(−2, 3) to P₁(14, 9) against the window (0,0)–(10,10), so the result can be compared with the Cohen-Sutherland walkthrough.
Set up: dx = 16, dy = 6
Four boundary conditions, each written as p·t ≤ q:
boundary p q
left p₁=−dx=−16 q₁ = x₀ − x_min = −2 − 0 = −2
right p₂= dx= 16 q₂ = x_max − x₀ = 10 −(−2) = 12
bottom p₃=−dy= −6 q₃ = y₀ − y_min = 3 − 0 = 3
top p₄= dy= 6 q₄ = y_max − y₀ = 10 − 3 = 7
Compute r = q/p for each, and sort by the sign of p:
p₁ = −16 < 0 → ENTERING: r = −2/−16 = 0.125
p₂ = 16 > 0 → LEAVING: r = 12/16 = 0.75
p₃ = −6 < 0 → ENTERING: r = 3/−6 = −0.5
p₄ = 6 > 0 → LEAVING: r = 7/6 ≈ 1.167
t₀ = max(0, all entering) = max(0, 0.125, −0.5) = 0.125
t₁ = min(1, all leaving) = min(1, 0.75, 1.167) = 0.75
t₀ < t₁, so a visible segment exists:
entry = (−2 + 0.125×16, 3 + 0.125×6) = (0, 3.75)
exit = (−2 + 0.75×16, 3 + 0.75×6) = (10, 7.5)
The same segment as Cohen-Sutherland produced — (0, 3.75) to (10, 7.5) — reached without any iteration. Every boundary is handled once, in a fixed number of steps, which is the efficiency claim made above.
The two rules that decide everything
📐 Reading the sign of p
p < 0The line is entering across that boundary — its r is a candidate for t₀, and we take the largest.
p > 0The line is leaving — its r is a candidate for t₁, and we take the smallest.
p = 0, q < 0The line is parallel to that boundary and lies outside it — reject immediately.
p = 0, q ≥ 0Parallel but inside — ignore this boundary and carry on.
💡 The p = 0 case is the one that breaks naive implementations: it means dx or dy is zero, so a perfectly horizontal or vertical line divides by zero unless handled separately. Examiners include such a line specifically to see whether the case was considered.
💡 If t₀ > t₁ at the end, no visible segment exists and the line is rejected entirely — the entry point would be beyond the exit point, which is impossible for a real crossing.
Syllabus points
Parametric line clipping; algorithm steps (numerical)
Create a free account to tick topics off, take notes as you read, watch the video lessons and get a day-by-day study plan built around your exam date.