Cyrus Beck Algorithm

Cyrus Beck Line clipping algorithm is infact, a parametric line-clipping algorithm. The term parametric implies that we need to find the value of the parameter ‘t’ in the parametric representation of the line segment for the point at which the segment intersects the clipping edge. For better understanding, consider the Figure where PQ is a line segment, which is intersecting at the two edges of the convex window.

Note: The algorithm is applicable to the “convex polygonal window”.

Now, just recall the parametric equation of line segment PQ.

It is simply P + t (Q – P)   0 ≤ t ≤ 1

Where, t → linear parameter continuously changes value.

∴P + t (Q – P) ⇒ (x₁, y₁) + t (x₂ – x₁, y₂ – y₁) = (x, y) be any point on PQ.    —— (1)

For this equation (1) we have following cases:

1. When t = 0 we obtain the point P.
2. When t = 1 we get the point Q.
3. When t varies such that 0 ≤ t ≤ 1 then line between point P and Q is traced. For t = ½ we get the mid-point of PQ.
4. When t < 0 line on LHS of P is traced.
5. When t > 1 line on RHS of Q is traced.

So, the variation in parameter ‘t’ is actually generating line in point wise manner .The range of the parameter values will identify the portion to be clipped by any convex polygonal region having n-vertices or lattice points to be specified by the user. One such clipping situation is shown in Figure.

Remark:

How to specify the window region: Cyrus-Beck Algorithm

A convex polygonal region having ‘n’ vertices {P₀, P₁, P₂, …, P_{n – 1}, P_n, P₀} or lattice points to be specified by the user encloses the convex window region. To be specific about the window we may say that each edge between two points contributes to the boundary of the window under the situation that (when we traverse each edge in anticlockwise manner), the window region lies on left hand side (LHS) of edge. This orientation is preserved and while giving input, the user takes care of the orientation to specify the window region of any arbitrary convex shape.

Potentially entering and leaving points (P_E and  P_L ):

The point of intersection of the line and window may be classified either as Potentially entering or leaving. Before going into other details, let us describe the actual meaning of Potentially entering and leaving points (P_E and  P_L ). PE and PL are dependent on the edge orientation, i.e. direction. Let us understand how to find P_E and P_L (we know as we move anticlockwise across the window boundary then region of LHS encloses the window).

Say, we are moving from point P to point Q, and we know that while traversing the windows edges in anticlockwise manner the region lying on the left hand side is referred to as the window region. So, from the Figure, you may notice that at point P_E  we are moving from P to Q we are entering the window region , thus this point of intersection should be referred to as the Potentially entering point(P_E). Now, refer to other intersection shown in the Figure, here, also the movement of points on the line are determined by varying value of parameter t is from point P to Q and  w.r.t., the orientation of window boundary, we are exiting the window region. So, this point of intersection is known as potentially leaving point (P_L).

Potentially entering point (P_E) while moving towards the window, the point of intersection between line PQ and the window edges faced are known as P_E.

Potentially leaving point (P_L) These are the point of intersection encountered while we move away from window.

Other way round you may detect the point of intersection as Potentially leaving point (P_L) or Potentially entering point (P_E) by studying the angle between the line to be clipped from the outward normal to the intersecting edge, at the point of intersection. From Figure, it is the angle between PQ and N₁ or N₂. You may notice that, while moving from P to Q the angle between line PQ and N₁ is obtuse whereas the angle between PQ and N₂ is acute; so, you may say, if the angle between line PQ and N₁ is obtuse the point of intersection is potentially entering (P_E) whereas, if the angle between PQ and N₂ is acute, then the point of intersection is potentially leaving (P_L).

OR

Where N_i is the outward normal to the i-th edge.

We know that the parametric equation of line PQ is  P + t (Q – P)  ;   0 ≤ t ≤ 1

Now, to find the point of intersection of line PQ and ith edge we need to find the appropriate value of parameter t, for that we firstly find normal to the ith edge. Say N_i is the normal to ith edge (P_i-1 to P_i), then to find the appropriate parameter t, we should determine the dot product of the vector from P_{i – 1}  to the point of intersection and the normal N_i.

How does the Cyrus Beck line clipping algorithm, clip a line segment if the window is non convex?

 ;