Definition

line segment https://www.splashmath.com/math-vocabulary/geometry/line-segment
y-intercept https://www.mathsisfun.com/y_intercept.html

For two infinite lines to intersect,

slope1 != slope2 OR slope1 == slope2 AND intersect1 == intersect2

For two straight line segments to intersect,

extended infinite segments intersect AND intersection is within line segment 1 (x and y coordinates) AND intersection is within line segment 2 (x and y coordinates)

What is the two segments represent the same infinite line,

Order the line segments by x locations (start is before end, point1 is before point2) start1.x < start2.x && start1.x < end1.x && start2.x < end2.x start2 is between start1 and end1

Solution

public class Line {
  public double slope, yintercept;
  public Line(Point start, Point end) {
    final double deltaY = end.y - start.y;
    final double deltaX = end.x - start.x;
    slope = deltaY / deltaX;
    yintercept = end.y - slope * end.x;
  }
}

public class Point {
  public double x, y;
  public Point(double x, double y) {
    this.x = x;
    this.y = y;
  }

  public void setLocation(double x, double y) {
    this.x = x;
    this.y = y;
  }
}

Point intersection(Point start1, Point end1, Point start2, Point end2) {
  /* Rearranging these so that, in order of x values: start is before end and
   * point1 is before point2. This will make some of the later logic simpler. */
  if (start1.x > end1.x) swap(start1, end1);
  if (start2.x > end2.x) swap(start2, end2);
  if (start1.x > start2.x) {
    swap(start1, start2);
    swap(end1, end2);
  }

  /* Compute lines (including slope and y-intercept). */
  Line line1 =  new Line(start1, end1);
  Line line2 =  new Line(start2, end2);

  /* If the lines are parallel, they intercept only if they have the same y-intercept
   * and start2 is on line1. */
  if (line1.slope == line2.slope) {
    if (line1.yintercept == line2.yintercept && isBetween(start1, start2, end1)) {
      return start2;
    }
    return null;
  }

  /* Get intersection coordinate. */
  double x = (line2.yintercept - line1.yintercept) / line1.slope - line2.slope);
  double y = x * line1.slope + line1.yintercept;
  Point intersection = new Point(x, y);

  /* Check if within line segment range. */
  if (isBetween(start1, intersection, end1) && isBetween(start2, intersection, end2) {
    return intersection;
  }
  return null;
}

/* Checks if middle is between start and end. */
boolean isBetween(double start, double middle, double end) {
  if (start > end) {
    return end <= middle && middle <= start;
  } else {
    return start <= middle && middle <= end;
  }
}

/* Checks if middle is between start and end. */
boolean isBetween(Point start, Point middle, Point end) {
  return isBetween(start.x, middle.x, end.x) && isBetween(start.y, middle.y, end.y) ;
}

/* Swap coordinates of point one and two. */
void swap(Point one, Point two) {
  double x = one.x;
  double y = one.y;
  one.setLocation(two.x, two.y);
  two.setLocation(x, y);
}

interview-preparation / what-we-do

[Moderate] interview questions #3 #130

Definition

Solution