## 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.

You can also check out our other blogs on __Code36____0.__