Line crosses Rectangle - how to find the cross points?

Question

I'm drawing a rectangle onto a canvas and a line from the center of the rectangle to some random point in the coordinate space.

Now, I want to truncate the line by the length that is inside the rectangle so that the line starts at the rectangle edge.

How could I do this?

Example

• The rectangle could be defined by 2 points: Pstart(1, 3), Pend(3, 1)
• The center point can be computed to : P(2, 2)
• Now draw the line from P(2, 2) to Q(10, 2).

As I know the width of the rectangle is 2, I could tell the line to start at P(4, 2) instead of P(2, 2).

This gets more complicated when the point is not parallel to one of the XY axis. Moreover the length inside the rectangle will be different amount for diagonal lines.

How can I calculate the start offset for the line point with respect to the center of the rectangle and the end point of the line?

Probably I'd have to find the point where the line would cross the rectangle, and then just let the line start at the cross point. But how could I get this point?

Nicholson

There are a bunch of solutions on this page: #1586025 Pick the solution on that page that makes the most sense to you and get at it. – Inversely

Answer 1

Honestly, I don't understand the maths, but...

Essentially, you have 5 lines. The original line and the 4 lines of the rectangle. So if you break it down to a simple line intersection of line problem it should become a little easier...

import java.awt.BorderLayout;
import java.awt.Color;
import java.awt.Dimension;
import java.awt.EventQueue;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.Point;
import java.awt.geom.Ellipse2D;
import java.awt.geom.Line2D;
import java.awt.geom.Point2D;
import java.awt.geom.Rectangle2D;
import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.UIManager;
import javax.swing.UnsupportedLookAndFeelException;

public class IntersectPoint {

    public static void main(String[] args) {
        new IntersectPoint();
    }

    public IntersectPoint() {
        EventQueue.invokeLater(new Runnable() {
            @Override
            public void run() {
                try {
                    UIManager.setLookAndFeel(UIManager.getSystemLookAndFeelClassName());
                } catch (ClassNotFoundException | InstantiationException | IllegalAccessException | UnsupportedLookAndFeelException ex) {
                }

                JFrame frame = new JFrame("Testing");
                frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
                frame.setLayout(new BorderLayout());
                frame.add(new TestPane());
                frame.pack();
                frame.setLocationRelativeTo(null);
                frame.setVisible(true);
            }
        });
    }

    public class TestPane extends JPanel {

        @Override
        public Dimension getPreferredSize() {
            return new Dimension(200, 200);
        }

        @Override
        protected void paintComponent(Graphics g) {
            super.paintComponent(g);

            int x = (int) (getWidth() * 0.2f);
            int y = (int) (getHeight() * 0.2f);
            int width = (int) (getWidth() * 0.6f);
            int height = (int) (getHeight() * 0.6f);

            int x1 = x;
            int y1 = 0;
            int x2 = x + width;
            int y2 = getHeight();

            Line2D line = new Line2D.Double(x1, y1, x2, y2);
            Rectangle2D rect = new Rectangle2D.Double(x, y, width, height);

            Graphics2D g2d = (Graphics2D) g.create();
            g2d.draw(rect);
            g2d.draw(line);

            g2d.setColor(Color.RED);
            Point2D[] ps = getIntersectionPoint(line, rect);
            for (Point2D p : ps) {
                if (p != null) {
                    g2d.fill(new Ellipse2D.Double(p.getX() - 4, p.getY() - 4, 8, 8));
                }
            }
            g2d.dispose();

        }

        public Point2D[] getIntersectionPoint(Line2D line, Rectangle2D rectangle) {

            Point2D[] p = new Point2D[4];

            // Top line
            p[0] = getIntersectionPoint(line,
                            new Line2D.Double(
                            rectangle.getX(),
                            rectangle.getY(),
                            rectangle.getX() + rectangle.getWidth(),
                            rectangle.getY()));
            // Bottom line
            p[1] = getIntersectionPoint(line,
                            new Line2D.Double(
                            rectangle.getX(),
                            rectangle.getY() + rectangle.getHeight(),
                            rectangle.getX() + rectangle.getWidth(),
                            rectangle.getY() + rectangle.getHeight()));
            // Left side...
            p[2] = getIntersectionPoint(line,
                            new Line2D.Double(
                            rectangle.getX(),
                            rectangle.getY(),
                            rectangle.getX(),
                            rectangle.getY() + rectangle.getHeight()));
            // Right side
            p[3] = getIntersectionPoint(line,
                            new Line2D.Double(
                            rectangle.getX() + rectangle.getWidth(),
                            rectangle.getY(),
                            rectangle.getX() + rectangle.getWidth(),
                            rectangle.getY() + rectangle.getHeight()));

            return p;

        }

        public Point2D getIntersectionPoint(Line2D lineA, Line2D lineB) {

            double x1 = lineA.getX1();
            double y1 = lineA.getY1();
            double x2 = lineA.getX2();
            double y2 = lineA.getY2();

            double x3 = lineB.getX1();
            double y3 = lineB.getY1();
            double x4 = lineB.getX2();
            double y4 = lineB.getY2();

            Point2D p = null;

            double d = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4);
            if (d != 0) {
                double xi = ((x3 - x4) * (x1 * y2 - y1 * x2) - (x1 - x2) * (x3 * y4 - y3 * x4)) / d;
                double yi = ((y3 - y4) * (x1 * y2 - y1 * x2) - (y1 - y2) * (x3 * y4 - y3 * x4)) / d;

                p = new Point2D.Double(xi, yi);

            }
            return p;
        }
    }
}

Jackelinejackelyn

The getIntersectionPoint() functions can be simplified greatly if you know that one of the lines is vertical or horizontal, which you do. – Jackinthebox

Answer 2

Look at Liang-Barsky algorithm used for line clipping by rectangle.

Cymophane

Answer 3

Vertices of the rectangle: a, b, c, d. Represent the x and y coord of each one like ax, ay, etc.

endpoints of the line: x, y

The line follows y = mx + b, and goes either up or down, right or left. That narrows down your possible rectangle edges for crossing to 2.

Use y = mx + b to determine the vertical coordinate at which it crosses the horizontal line, and the horizontal component at which it crosses the vertical line. Either only one of these will actually be on your rectangle (i.e., contained within one of the rectangle edges), or it will intersect at a corner.

Teodoor

really you could use just y=mx because the line starts in the centre of the rectangle – Landahl

I haven't worked out the math fully, but I don't think that will work. The 'b' offset tells you the 'y' coordinate for an x=0, i.e., the vertical position of the line with slope 'm'. That will definitely affect which rectangle edge is intersected by a line, in the general case. I am not assuming any of these points are at the origin. – Teodoor

Yeah, you can only assume b=0 if the rectangle is centered about the origin. – Jackinthebox