Sunday, March 30, 2014

Determine whether two lines would intersect on a Cartesian plane

Problem
Given two lines on a Cartesian plane, determine whether the two lines would intersect.
Solution
 On a Cartesian plane, if two lines do not intersect, they must be parallel with each other. Hence, their slopes must be the same. If their slopes are different, they would intersect. A line is represented as ax+by+c=0 on a Cartesian plane and the slope is given by -\frac{a}{b}. Therefore if -\frac{a_{0}}{b_{0}} \neq -\frac{a_{1}}{b_{1}} for two lines, they will intersect.


public class Line {
    static final double epsilon = 0.000001;
    public double slope;
    public double yintercept;
 
    public Line(double s, double y) {
        slope = s;
        yintercept = y;
    }
 
    public boolean intersect(Line line2) {
        return Math.abs(slope - line2.slope) > epsilon
                || Math.abs(yintercept - line2.yintercept) < epsilon;
    }
}

Two lines can be the same. In that case, we assume they intersects (overlap). We need to consider the floating system in a computer. Never use == to compare two floating numbers in java.

0 comments:

Post a Comment