How to find where two line segments intersect programmatically

Question

Suppose you have the following positive coordinate region below:

In this region we have a rectangle that represents a computer window. As you can see there are also line segments covering the region. I am attempting to try and solve a problem in which I will clip the line segments when they are outside of the window.

For instance, the top left coordinate of the window below would be (20,80), its bottom left coordinate would be (20, 20), its top right coordinate would be (120, 80) and its bottom right coordinate would be (120, 20). Line segment B has a starting coordinate of (55, 65) and an ending coordinate of (90, 90).

If I were to clip segment B, though, it would then have a starting coordinate of (55,65) and an ending coordinate of (76, 80).

Programmatically, how would I go about calculating where the line segment intersects the line segment of the window? Likewise, how would I go about finding that they don't intersect at all like segment E.

Answer 1

Try this.

public static boolean clipLine(Line2D line, Rectangle2D rect) {

    double x1 = line.getX1(), y1 = line.getY1(), x2 = line.getX2(), y2 = line.getY2();
    double minX = rect.getMinX(), maxX = rect.getMaxX(), minY = rect.getMinY(), maxY = rect.getMaxY();
    int f1 = rect.outcode(x1, y1);
    int f2 = rect.outcode(x2, y2);

    while ((f1 | f2) != 0) {
        if ((f1 & f2) != 0) {
            return false;
        }
        double dx = (x2 - x1);
        double dy = (y2 - y1);
        // update (x1, y1), (x2, y2) and f1 and f2 using intersections
        // then recheck
        if (f1 != 0) {
            // first point is outside, so we update it against one of the
            // four sides then continue
            if ((f1 & Rectangle2D.OUT_LEFT) == Rectangle2D.OUT_LEFT
                    && dx != 0.0) {
                y1 = y1 + (minX - x1) * dy / dx;
                x1 = minX;
            }
            else if ((f1 & Rectangle2D.OUT_RIGHT) == Rectangle2D.OUT_RIGHT
                    && dx != 0.0) {
                y1 = y1 + (maxX - x1) * dy / dx;
                x1 = maxX;
            }
            else if ((f1 & Rectangle2D.OUT_BOTTOM) == Rectangle2D.OUT_BOTTOM
                    && dy != 0.0) {
                x1 = x1 + (maxY - y1) * dx / dy;
                y1 = maxY;
            }
            else if ((f1 & Rectangle2D.OUT_TOP) == Rectangle2D.OUT_TOP
                    && dy != 0.0) {
                x1 = x1 + (minY - y1) * dx / dy;
                y1 = minY;
            }
            f1 = rect.outcode(x1, y1);
        }
        else if (f2 != 0) {
            // second point is outside, so we update it against one of the
            // four sides then continue
            if ((f2 & Rectangle2D.OUT_LEFT) == Rectangle2D.OUT_LEFT
                    && dx != 0.0) {
                y2 = y2 + (minX - x2) * dy / dx;
                x2 = minX;
            }
            else if ((f2 & Rectangle2D.OUT_RIGHT) == Rectangle2D.OUT_RIGHT
                    && dx != 0.0) {
                y2 = y2 + (maxX - x2) * dy / dx;
                x2 = maxX;
            }
            else if ((f2 & Rectangle2D.OUT_BOTTOM) == Rectangle2D.OUT_BOTTOM
                    && dy != 0.0) {
                x2 = x2 + (maxY - y2) * dx / dy;
                y2 = maxY;
            }
            else if ((f2 & Rectangle2D.OUT_TOP) == Rectangle2D.OUT_TOP
                    && dy != 0.0) {
                x2 = x2 + (minY - y2) * dx / dy;
                y2 = minY;
            }
            f2 = rect.outcode(x2, y2);
        }
    }

    line.setLine(x1, y1, x2, y2);
    return true;  // the line is visible - if it wasn't, we'd have
                  // returned false from within the while loop above

}

and

public static void main(String[] args) {
    Rectangle2D.Double rectangle = new Rectangle2D.Double(20, 20, 100, 60); // x, y, width, height
    Line2D.Double line = new Line2D.Double(55, 65, 90, 90); // x1, y1, x2, y2
    boolean result = clipLine(line, rectangle);
    System.out.println("result=" + result
        + " x1=" + line.x1 + " y1=" + line.y1
        + " x2=" + line.x2 + " y2=" + line.y2);
}

output:

result=true x1=55.0 y1=65.0 x2=76.0 y2=80.0