Cyrus–Beck algorithm

The Cyrus–Beck algorithm is a generalized line clipping algorithm. It was designed to be more efficient than the Cohen–Sutherland algorithm, which uses repetitive clipping.[1] Cyrus–Beck is a general algorithm and can be used with a convex polygon clipping window, unlike Sutherland–Cohen, which can be used only on a rectangular clipping area.

Cyrus–Beck algorithm

Here the parametric equation of a line in the view plane is

where .

Now to find the intersection point with the clipping window, we calculate the value of the dot product. Let pE be a point on the clipping plane E.

Calculate :

if < 0, vector pointed towards interior;
if = 0, vector pointed parallel to plane containing p;
if > 0, vector pointed away from interior.

Here n stands for normal of the current clipping plane (pointed away from interior).

By this we select the point of intersection of line and clipping window where (dot product is 0) and hence clip the line.

Notes
  1. "Clipping" (presentation).
gollark: I actually stole this particular quicksort from a r/haskell post talking about it.
gollark: ```lisp (let (partition_rec xs pred acc) (cond ((= xs '()) acc) (true (partition_rec (tail xs) pred (cond ((pred (head xs)) (list (cons (head xs) (head acc)) (snd acc))) (true (list (head acc) (cons (head xs) (snd acc)))) ))) )) (let (qsort xs cont) (cond ((= xs '()) (cont '())) (true (do (let h (head xs)) (let t (tail xs)) (let part_result (partition_rec t (lambda (x) (< x h)) '(() ()))) (qsort (head part_result) (lambda (ls) (qsort (snd part_result) (lambda (rs) (cont (+ ls (list h) rs)))))) )) ))```These all have to be done tail recursively or it could overflow.
gollark: Continuation passing style quicksort in a hilariously slow interpreter.
gollark: It manages *1* second, which is great.
gollark: When writing osmarkslisp™, I cared about performance to the extent that it would sort a list of 200 integers in under 5 seconds.

See also

Algorithms used for the same purpose:

References in other media:

References


This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.