Cyrus-Beck Clipping

How Cyrus-Beck Clipping works

Cyrus-Beck clips a line against any convex polygon by working in parameter space instead of pixel space. Write the segment as P(t) = P₀ + t·D where D = P₁ − P₀ and t runs from 0 to 1. For each edge of the clipping polygon take an inward or outward normal N and any point F on that edge, then evaluate N · D and N · (P₀ − F). The sign of N · D says what the line is doing at that edge: with outward normals, a negative dot product means the line is entering the half-plane, a positive one means it is leaving, and zero means it is parallel. Solving for the intersection gives t = −(N · (P₀ − F)) / (N · D). Collect every entering t into a running maximum tE and every leaving t into a running minimum tL. After all edges are processed, the visible portion is the interval [tE, tL]; if tE > tL the line misses the polygon entirely. Parallel edges never produce a t — instead they either reject the line immediately or are ignored, depending on which side of the edge P₀ sits.

Pseudocode

cyrusBeck(P0, P1, polygon):        // convex polygon, outward normals
    D = P1 - P0
    if D == 0: return (P0 inside polygon) ? ACCEPT : REJECT

    tE = 0        // largest entering parameter
    tL = 1        // smallest leaving parameter

    for each edge i of polygon:
        N = outwardNormal(i)
        F = anyPointOn(i)
        W = P0 - F                    // vector from edge to line start

        denom = dot(N, D)
        num   = dot(N, W)

        if denom == 0:                // line parallel to this edge
            if num > 0: return REJECT // and entirely outside it
            else: continue            // inside: this edge cannot clip

        t = -num / denom
        if denom < 0:                 // entering
            tE = max(tE, t)
        else:                         // leaving
            tL = min(tL, t)

        if tE > tL: return REJECT     // early out: interval already empty

    return ACCEPT segment from P(tE) to P(tL)

Time and space complexity

Time

O(k) for a convex polygon with k edges

Space

O(1)

One dot-product pair and one division per edge, with no iteration or repeated clipping — the cost scales with the complexity of the clipping window, not with the length of the line.

Worked example

Square window x ∈ [0, 10], y ∈ [0, 10] with outward normals left(−1,0), right(1,0), bottom(0,−1), top(0,1). Line P₀(−2, 3) to P₁(12, 9), so D = (14, 6).

1. Left edgeN = (−1,0), F = (0,0). denom = −14 < 0 → entering. num = N·(P₀−F) = 2. t = −2/−14 ≈ 0.143. tE = 0.143.
2. Right edgeN = (1,0), F = (10,0). denom = 14 > 0 → leaving. num = (−2−10) = −12. t = 12/14 ≈ 0.857. tL = 0.857.
3. Bottom edgeN = (0,−1), F = (0,0). denom = −6 < 0 → entering. num = −3. t = −num/denom = −(−3)/(−6) = −0.5. tE = max(0.143, −0.5) = 0.143.
4. Top edgeN = (0,1), F = (0,10). denom = 6 > 0 → leaving. num = 3 − 10 = −7. t = 7/6 ≈ 1.167. tL = min(0.857, 1.167) = 0.857.
5. ComparetE = 0.143 ≤ tL = 0.857, so the segment is visible.

Visible from P(0.143) = (0, 3.86) to P(0.857) = (10, 8.14). The top and bottom edges contributed no constraint because the line crosses the window horizontally.

Common exam mistakes

• Mixing inward and outward normals between edges. The entering/leaving test flips sign, so one inconsistent normal silently inverts a constraint.
• Initialising tE and tL to ±infinity. For a segment they start at 0 and 1 — those bounds are what limit the answer to the actual line rather than its infinite extension.
• Assigning entering t values to tL and vice versa. Entering takes the maximum, leaving takes the minimum; swapping them produces an interval that is almost always empty.
• Dividing when N · D = 0. That is the parallel case and needs the sign of the numerator to decide reject-or-ignore, not a division.
• Using it on a concave polygon. The single-interval result is only valid for convex windows; a concave one can clip a line into several disjoint pieces.

Frequently asked questions

Related simulators