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);
}
}