LiangBarsky.java

packagecom.thealgorithms.lineclipping;

importcom.thealgorithms.lineclipping.utils.Line;
importcom.thealgorithms.lineclipping.utils.Point;

/**
 * @author shikarisohan
 * @since 10/5/24
 *
 * * The Liang-Barsky line clipping algorithm is an efficient algorithm for
 * * line clipping against a rectangular window. It is based on the parametric
 * * equation of a line and checks the intersections of the line with the
 * * window boundaries. This algorithm calculates the intersection points,
 * * if any, and returns the clipped line that lies inside the window.
 * *
 * * Reference:
 * * https://en.wikipedia.org/wiki/Liang%E2%80%93Barsky_algorithm
 *
 * Clipping window boundaries are defined as (xMin, yMin) and (xMax, yMax).
 * The algorithm computes the clipped line segment if it's partially or
 * fully inside the clipping window.
 */
publicclassLiangBarsky {

// Define the clipping window
doublexMin;
doublexMax;
doubleyMin;
doubleyMax;

publicLiangBarsky(doublexMin, doubleyMin, doublexMax, doubleyMax) {
this.xMin = xMin;
this.yMin = yMin;
this.xMax = xMax;
this.yMax = yMax;
 }

// Liang-Barsky algorithm to return the clipped line
publicLineliangBarskyClip(Lineline) {
doubledx = line.end.x - line.start.x;
doubledy = line.end.y - line.start.y;

double[] p = {-dx, dx, -dy, dy};
double[] q = {line.start.x - xMin, xMax - line.start.x, line.start.y - yMin, yMax - line.start.y};

double[] resultT = clipLine(p, q);

if (resultT == null) {
returnnull; // Line is outside the clipping window
 }

returncalculateClippedLine(line, resultT[0], resultT[1], dx, dy);
 }

// clip the line by adjusting t0 and t1 for each edge
privatedouble[] clipLine(double[] p, double[] q) {
doublet0 = 0.0;
doublet1 = 1.0;

for (inti = 0; i < 4; i++) {
doublet = q[i] / p[i];
if (p[i] == 0 && q[i] < 0) {
returnnull; // Line is outside the boundary
 } elseif (p[i] < 0) {
if (t > t1) {
returnnull;
 } // Line is outside
if (t > t0) {
t0 = t;
 } // Update t0
 } elseif (p[i] > 0) {
if (t < t0) {
returnnull;
 } // Line is outside
if (t < t1) {
t1 = t;
 } // Update t1
 }
 }

returnnewdouble[] {t0, t1}; // Return valid t0 and t1
 }

// calculate the clipped line based on t0 and t1
privateLinecalculateClippedLine(Lineline, doublet0, doublet1, doubledx, doubledy) {
doubleclippedX1 = line.start.x + t0 * dx;
doubleclippedY1 = line.start.y + t0 * dy;
doubleclippedX2 = line.start.x + t1 * dx;
doubleclippedY2 = line.start.y + t1 * dy;

returnnewLine(newPoint(clippedX1, clippedY1), newPoint(clippedX2, clippedY2));
 }
}