computeOverlaps6 method

void computeOverlaps6(int start0, int end0, MonotoneChainI mc, int start1, int end1, MonotoneChainOverlapAction mco,)

Uses an efficient mutual binary search strategy to determine which pairs of chain segments may overlap, and calls the given overlap action on them.

@param start0 the start index of this chain section @param end0 the end index of this chain section @param mc the target monotone chain @param start1 the start index of the target chain section @param end1 the end index of the target chain section @param mco the overlap action to execute on selected segments

Implementation

void computeOverlaps6(int start0, int end0, MonotoneChainI mc, int start1,
    int end1, MonotoneChainOverlapAction mco) {
//Debug.println("computeIntersectsForChain:" + p00 + p01 + p10 + p11);
  // terminating condition for the recursion
  if (end0 - start0 == 1 && end1 - start1 == 1) {
    mco.overlap(this, start0, mc, start1);
    return;
  }
  // nothing to do if the envelopes of these subchains don't overlap
  if (!overlaps(start0, end0, mc, start1, end1)) return;

  // the chains overlap, so split each in half and iterate  (binary search)
  int mid0 = ((start0 + end0) / 2).toInt();
  int mid1 = ((start1 + end1) / 2).toInt();

  // Assert: mid != start or end (since we checked above for end - start <= 1)
  // check terminating conditions before recursing
  if (start0 < mid0) {
    if (start1 < mid1) computeOverlaps6(start0, mid0, mc, start1, mid1, mco);
    if (mid1 < end1) computeOverlaps6(start0, mid0, mc, mid1, end1, mco);
  }
  if (mid0 < end0) {
    if (start1 < mid1) computeOverlaps6(mid0, end0, mc, start1, mid1, mco);
    if (mid1 < end1) computeOverlaps6(mid0, end0, mc, mid1, end1, mco);
  }
}