Cyrus Beck Line Clipping Algorithm

Introduction

The Cyrus-Beck line clipping algorithm is a way to cut a line segment using a convex polygon. It's a basic concept in computer graphics that helps decide which parts of a line are inside or outside a given area. This method is useful for rendering only the visible portions of a line, making the process more efficient.

In this article, we'll discuss the background of the algorithm, its working principle, different cases, pseudocode, & implementation of this algorithm in different languages

Background

The Cyrus-Beck line clipping algorithm, developed by Mike Cyrus & Jay Beck in 1978, is an extension of the Cohen-Sutherland line clipping algorithm. It works on the principle of parametric equations of a line & determines the intersection points between the line & the clipping polygon. The algorithm calculates the entry & exit points of the line with respect to the polygon edges, allowing it to identify the visible portion of the line segment. This approach is more efficient than Cohen-Sutherland when dealing with complex polygons or multiple lines.

Algorithm

The Cyrus-Beck line clipping algorithm works in steps mentioned below:

1. Define the convex polygon by its edges & vertices.

2. Determine the parametric equation of the line: P(t) = P0 + t(P1 - P0), where P0 & P1 are the endpoints of the line segment, & t is a parameter between 0 & 1.

3. For each edge of the polygon, calculate the outward-pointing normal vector (Ni).

4. Compute the dot product of each normal vector with the line direction vector (P1 - P0). If the dot product is 0, the line is parallel to the edge; if it's greater than 0, the line points inside the edge; & if it's less than 0, the line points outside the edge.

5. Calculate tE (entry) & tL (exit) for each edge using the parametric equation & normal vectors. Update tE with the maximum value & tL with the minimum value.

6. If tE > tL, the line segment is completely outside the polygon & can be discarded.

7. If tE ≤ tL, clip the line segment using the tE & tL values to obtain the visible portion of the line.

Cases

There are three primary cases to consider when applying the Cyrus-Beck line clipping algorithm:

1. Completely inside: If both endpoints of the line segment are inside the convex polygon, the entire line segment is visible & no clipping is required. In this case, tE ≤ 0 & tL ≥ 1.

2. Completely outside: If the line segment is entirely outside the convex polygon, it can be discarded as it won't be visible. This happens when tE > tL.

3. Partially inside: If the line segment is partially inside the convex polygon, it needs to be clipped. The visible portion of the line segment is determined by calculating the intersection points using the tE & tL values. The new endpoints of the clipped line segment are P(tE) & P(tL).

For example :

Consider a square convex polygon with vertices (0, 0), (0, 4), (4, 4), & (4, 0). Let's apply the Cyrus-Beck algorithm to three different line segments:

- Line 1: (1, 1) to (3, 3) - Completely inside

- Line 2: (-1, -1) to (-2, -2) - Completely outside

- Line 3: (-1, 2) to (5, 2) - Partially inside, clipped to (0, 2) & (4, 2)

Pseudocode

Let’s discuss the pseudocode for the Cyrus-Beck line clipping algorithm:

function CyrusBeckClip(P0, P1, polygon)
    tE = 0
    tL = 1
    d = P1 - P0

    for each edge in polygon
        N = normal vector of edge
        W = P0 - edge.start
        
        numerator = dot(N, W)
        denominator = dot(N, d)

        if denominator = 0
            if numerator < 0
                return empty line
        else
            t = -numerator / denominator
            if denominator < 0
                tE = max(tE, t)
            else
                tL = min(tL, t)

    if tE > tL
        return empty line
    else
        P0_clipped = P0 + tE * d
        P1_clipped = P0 + tL * d
        return line segment (P0_clipped, P1_clipped)

In this code :

1. Initialize tE to 0 & tL to 1.

2. Calculate the direction vector d by subtracting P0 from P1.

3. For each edge of the polygon:

- Calculate the outward-pointing normal vector N.

- Compute the vector W from the start of the edge to P0.

- Calculate the numerator by taking the dot product of N & W.

- Calculate the denominator by taking the dot product of N & d.

- If the denominator is 0, the line is parallel to the edge. If the numerator is less than 0, the line is outside the polygon & can be discarded.

- If the denominator is not 0, calculate t by dividing the negative numerator by the denominator.

- If the denominator is less than 0, update tE with the maximum of tE & t.

- If the denominator is greater than 0, update tL with the minimum of tL & t.

4. If tE is greater than tL, the line segment is completely outside the polygon & can be discarded.

5. Otherwise, calculate the clipped endpoints P0_clipped & P1_clipped using tE & tL, & return the clipped line segment.

Implementation

Java
C++
Python
JavaScript
PHP

Java

class Point {
    double x, y;
    
    Point(double x, double y) {
        this.x = x;
        this.y = y;
    }
}

class Edge {
    Point start, end;
    
    Edge(Point start, Point end) {
        this.start = start;
        this.end = end;
    }
}

public class CyrusBeck {
    static final double EPSILON = 1e-9;  // Small value for floating-point comparison
    
    static Point[] clipLine(Point p0, Point p1, Edge[] polygon) {
        double tE = 0, tL = 1;
        double dx = p1.x - p0.x;
        double dy = p1.y - p0.y;
        
        for (Edge edge : polygon) {
            double nx = edge.end.y - edge.start.y;
            double ny = edge.start.x - edge.end.x;
            double wx = p0.x - edge.start.x;
            double wy = p0.y - edge.start.y;
            
            double denominator = nx * dx + ny * dy;
            double numerator = nx * wx + ny * wy;
            
            if (Math.abs(denominator) < EPSILON) {  // Floating-point comparison
                if (numerator < 0) {
                    return null;  // Line is outside and parallel to the edge
                }
            } else {
                double t = -numerator / denominator;
                if (denominator < 0) {  // Potentially entering the polygon
                    tE = Math.max(tE, t);
                } else {  // Potentially leaving the polygon
                    tL = Math.min(tL, t);
                }
            }
        }
        
        if (tE > tL) {
            return null;  // Line is outside the polygon
        } else {
            // Compute the clipped points
            Point p0Clipped = new Point(p0.x + tE * dx, p0.y + tE * dy);
            Point p1Clipped = new Point(p0.x + tL * dx, p0.y + tL * dy);
            return new Point[]{p0Clipped, p1Clipped};
        }
    }

    public static void main(String[] args) {
        // Example usage:
        Point p0 = new Point(1, 1);
        Point p1 = new Point(5, 5);
        Edge[] polygon = new Edge[] {
            new Edge(new Point(0, 0), new Point(4, 0)),
            new Edge(new Point(4, 0), new Point(4, 4)),
            new Edge(new Point(4, 4), new Point(0, 4)),
            new Edge(new Point(0, 4), new Point(0, 0))
        };

        Point[] clippedPoints = CyrusBeck.clipLine(p0, p1, polygon);
        if (clippedPoints != null) {
            System.out.println("Clipped Line: (" + clippedPoints[0].x + ", " + clippedPoints[0].y + ") to (" + clippedPoints[1].x + ", " + clippedPoints[1].y + ")");
        } else {
            System.out.println("The line is outside the polygon.");
        }
    }
}

You can also try this code with Online Java Compiler

Run Code

C++

#include <iostream>
#include <vector>
#include <algorithm>

struct Point {
    double x, y;
    Point(double x, double y) : x(x), y(y) {}
};

struct Edge {
    Point start, end;
    Edge(Point start, Point end) : start(start), end(end) {}
};

std::pair<Point, Point> cyrusBeckClip(Point p0, Point p1, const std::vector<Edge>& polygon) {
    double tE = 0, tL = 1;
    double dx = p1.x - p0.x;
    double dy = p1.y - p0.y;

    for (const auto& edge : polygon) {
        double nx = edge.end.y - edge.start.y;
        double ny = edge.start.x - edge.end.x;
        double wx = p0.x - edge.start.x;
        double wy = p0.y - edge.start.y;

        double denominator = nx * dx + ny * dy;
        double numerator = nx * wx + ny * wy;

        if (denominator == 0) {
            if (numerator < 0) {
                return {Point(0, 0), Point(0, 0)};
            }
        } else {
            double t = -numerator / denominator;
            if (denominator < 0) {
                tE = std::max(tE, t);
            } else {
                tL = std::min(tL, t);
            }
        }
    }

    if (tE > tL) {
        return {Point(0, 0), Point(0, 0)};
    } else {
        Point p0Clipped(p0.x + tE * dx, p0.y + tE * dy);
        Point p1Clipped(p0.x + tL * dx, p0.y + tL * dy);
        return {p0Clipped, p1Clipped};
    }
}

int main() {
    Point p0(1, 1), p1(5, 5);
    std::vector<Edge> polygon = {
        Edge(Point(0, 0), Point(0, 4)),
        Edge(Point(0, 4), Point(4, 4)),
        Edge(Point(4, 4), Point(4, 0)),
        Edge(Point(4, 0), Point(0, 0))
    };

    auto clippedLine = cyrusBeckClip(p0, p1, polygon);

    if (clippedLine.first.x != 0 || clippedLine.first.y != 0 || clippedLine.second.x != 0 || clippedLine.second.y != 0) {
        std::cout << "Clipped line: (" << clippedLine.first.x << ", " << clippedLine.first.y << ") to ("
                  << clippedLine.second.x << ", " << clippedLine.second.y << ")" << std::endl;
    } else {
        std::cout << "Line is completely outside the polygon" << std::endl;
    }

    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Python

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

class Edge:
    def __init__(self, start, end):
        self.start = start
        self.end = end

def cyrus_beck_clip(p0, p1, polygon):
    tE = 0
    tL = 1
    dx = p1.x - p0.x
    dy = p1.y - p0.y

    for edge in polygon:
        nx = edge.end.y - edge.start.y
        ny = edge.start.x - edge.end.x
        wx = p0.x - edge.start.x
        wy = p0.y - edge.start.y

        denominator = nx * dx + ny * dy
        numerator = nx * wx + ny * wy

        if denominator == 0:
            if numerator < 0:
                return None
        else:
            t = -numerator / denominator
            if denominator < 0:
                tE = max(tE, t)
            else:
                tL = min(tL, t)

    if tE > tL:
        return None
    else:
        p0_clipped = Point(p0.x + tE * dx, p0.y + tE * dy)
        p1_clipped = Point(p0.x + tL * dx, p0.y + tL * dy)
        return p0_clipped, p1_clipped

# Example usage
p0 = Point(1, 1)
p1 = Point(5, 5)
polygon = [
    Edge(Point(0, 0), Point(0, 4)),
    Edge(Point(0, 4), Point(4, 4)),
    Edge(Point(4, 4), Point(4, 0)),
    Edge(Point(4, 0), Point(0, 0))
]

clipped_line = cyrus_beck_clip(p0, p1, polygon)

if clipped_line:
    print(f"Clipped line: ({clipped_line[0].x}, {clipped_line[0].y}) to ({clipped_line[1].x}, {clipped_line[1].y})")
else:
    print("Line is completely outside the polygon")

You can also try this code with Online Python Compiler

Run Code

JavaScript

class Point {
  constructor(x, y) {
    this.x = x;
    this.y = y;
  }
}

class Edge {
  constructor(start, end) {
    this.start = start;
    this.end = end;
  }
}

function cyrusBeckClip(p0, p1, polygon) {
  let tE = 0;
  let tL = 1;
  const dx = p1.x - p0.x;
  const dy = p1.y - p0.y;

  for (const edge of polygon) {
    const nx = edge.end.y - edge.start.y;
    const ny = edge.start.x - edge.end.x;
    const wx = p0.x - edge.start.x;
    const wy = p0.y - edge.start.y;

    const denominator = nx * dx + ny * dy;
    const numerator = nx * wx + ny * wy;

    if (denominator === 0) {
      if (numerator < 0) {
        return null;
      }
    } else {
      const t = -numerator / denominator;
      if (denominator < 0) {
        tE = Math.max(tE, t);
      } else {
        tL = Math.min(tL, t);
      }
    }
  }

  if (tE > tL) {
    return null;
  } else {
    const p0Clipped = new Point(p0.x + tE * dx, p0.y + tE * dy);
    const p1Clipped = new Point(p0.x + tL * dx, p0.y + tL * dy);
    return [p0Clipped, p1Clipped];
  }
}

// Example usage
const p0 = new Point(1, 1);
const p1 = new Point(5, 5);
const polygon = [
  new Edge(new Point(0, 0), new Point(0, 4)),
  new Edge(new Point(0, 4), new Point(4, 4)),
  new Edge(new Point(4, 4), new Point(4, 0)),
  new Edge(new Point(4, 0), new Point(0, 0)),
];

const clippedLine = cyrusBeckClip(p0, p1, polygon);

if (clippedLine) {
  console.log(
    `Clipped line: (${clippedLine[0].x}, ${clippedLine[0].y}) to (${clippedLine[1].x}, ${clippedLine[1].y})`
  );
} else {
  console.log("Line is completely outside the polygon");
}

You can also try this code with Online Javascript Compiler

Run Code

PHP


<?php
class Point {
    public $x;
    public $y;

    public function __construct($x, $y) {
        $this->x = $x;
        $this->y = $y;
    }
}

class Edge {
    public $start;
    public $end;

    public function __construct($start, $end) {
        $this->start = $start;
        $this->end = $end;
    }
}

function cyrusBeckClip($p0, $p1, $polygon) {
    $tE = 0;
    $tL = 1;
    $dx = $p1->x - $p0->x;
    $dy = $p1->y - $p0->y;

    foreach ($polygon as $edge) {
        $nx = $edge->end->y - $edge->start->y;
        $ny = $edge->start->x - $edge->end->x;
        $wx = $p0->x - $edge->start->x;
        $wy = $p0->y - $edge->start->y;

        $denominator = $nx * $dx + $ny * $dy;
        $numerator = $nx * $wx + $ny * $wy;

        if ($denominator == 0) {
            if ($numerator < 0) {
                return null;
            }
        } else {
            $t = -$numerator / $denominator;
            if ($denominator < 0) {
                $tE = max($tE, $t);
            } else {
                $tL = min($tL, $t);
            }
        }
    }

    if ($tE > $tL) {
        return null;
    } else {
        $p0Clipped = new Point($p0->x + $tE * $dx, $p0->y + $tE * $dy);
        $p1Clipped = new Point($p0->x + $tL * $dx, $p0->y + $tL * $dy);
        return [$p0Clipped, $p1Clipped];
    }
}

// Example usage
$p0 = new Point(1, 1);
$p1 = new Point(5, 5);
$polygon = [
    new Edge(new Point(0, 0), new Point(0, 4)),
    new Edge(new Point(0, 4), new Point(4, 4)),
    new Edge(new Point(4, 4), new Point(4, 0)),
    new Edge(new Point(4, 0), new Point(0, 0))
];

$clippedLine = cyrusBeckClip($p0, $p1, $polygon);

if ($clippedLine) {
    echo "Clipped line: ({$clippedLine[0]->x}, {$clippedLine[0]->y}) to ({$clippedLine[1]->x}, {$clippedLine[1]->y})\n";
} else {
    echo "Line is completely outside the polygon\n";
}
?>

You can also try this code with Online PHP Compiler

Run Code

Output

Clipped Line: (1.0, 1.0) to (4.0, 4.0)

Frequently Asked Questions

What is the time complexity of the Cyrus-Beck line clipping algorithm?

The time complexity of the Cyrus-Beck algorithm is O(n), where n is the number of edges in the convex polygon.

Can the Cyrus-Beck algorithm handle concave polygons?

No, the Cyrus-Beck algorithm is designed to work with convex polygons only. For concave polygons, other algorithms like Weiler-Atherton should be used.

How does the Cyrus-Beck algorithm differ from the Cohen-Sutherland algorithm?

The Cyrus-Beck algorithm uses parametric equations & dot products to determine the intersection points, while Cohen-Sutherland uses a region-based approach. Cyrus-Beck is more efficient for complex polygons.

Conclusion

In this article, we discussed the Cyrus-Beck line clipping algorithm, a powerful method for clipping line segments against a convex polygon. We started with the background, then we talked about the working principle, different cases, pseudocode, & implementation of the algorithm in Java, Python, C++, JavaScript, & PHP. The Cyrus-Beck algorithm provides an efficient way to determine the visible portion of a line segment within a convex polygon, which makes it a valuable tool in computer graphics & rendering applications.