intersects method

bool intersects(Coordinate p0, Coordinate p1)

Tests whether the query rectangle intersects a given line segment.

@param p0 the first endpoint of the segment @param p1 the second endpoint of the segment @return true if the rectangle intersects the segment

Implementation

bool intersects(Coordinate p0, Coordinate p1) {
  // TODO: confirm that checking envelopes first is faster

  /**
   * If the segment envelope is disjoint from the
   * rectangle envelope, there is no intersection
   */
  Envelope segEnv = new Envelope.fromCoordinates(p0, p1);
  if (!rectEnv.intersectsEnvelope(segEnv)) return false;

  /**
   * If either segment endpoint lies in the rectangle,
   * there is an intersection.
   */
  if (rectEnv.intersectsCoordinate(p0)) return true;
  if (rectEnv.intersectsCoordinate(p1)) return true;

  /**
   * Normalize segment.
   * This makes p0 less than p1,
   * so that the segment runs to the right,
   * or vertically upwards.
   */
  if (p0.compareTo(p1) > 0) {
    Coordinate tmp = p0;
    p0 = p1;
    p1 = tmp;
  }
  /**
   * Compute angle of segment.
   * Since the segment is normalized to run left to right,
   * it is sufficient to simply test the Y ordinate.
   * "Upwards" means relative to the left end of the segment.
   */
  bool isSegUpwards = false;
  if (p1.y > p0.y) isSegUpwards = true;

  /**
   * Since we now know that neither segment endpoint
   * lies in the rectangle, there are two possible
   * situations:
   * 1) the segment is disjoint to the rectangle
   * 2) the segment crosses the rectangle completely.
   *
   * In the case of a crossing, the segment must intersect
   * a diagonal of the rectangle.
   *
   * To distinguish these two cases, it is sufficient
   * to test intersection with
   * a single diagonal of the rectangle,
   * namely the one with slope "opposite" to the slope
   * of the segment.
   * (Note that if the segment is axis-parallel,
   * it must intersect both diagonals, so this is
   * still sufficient.)
   */
  if (isSegUpwards) {
    li.computeIntersection(p0, p1, diagDown0, diagDown1);
  } else {
    li.computeIntersection(p0, p1, diagUp0, diagUp1);
  }
  if (li.hasIntersection()) return true;
  return false;
}