computeSelect method
Implementation
void computeSelect(
Envelope searchEnv, int start0, int end0, MonotoneChainSelectAction mcs) {
Coordinate p0 = pts[start0];
Coordinate p1 = pts[end0];
//Debug.println("trying:" + p0 + p1 + " [ " + start0 + ", " + end0 + " ]");
// terminating condition for the recursion
if (end0 - start0 == 1) {
//Debug.println("computeSelect:" + p0 + p1);
mcs.select(this, start0);
return;
}
// nothing to do if the envelopes don't overlap
if (!searchEnv.intersectsEnvelopeCoordinates(p0, p1)) return;
// the chains overlap, so split each in half and iterate (binary search)
int mid = ((start0 + end0) / 2).toInt();
// Assert: mid != start or end (since we checked above for end - start <= 1)
// check terminating conditions before recursing
if (start0 < mid) {
computeSelect(searchEnv, start0, mid, mcs);
}
if (mid < end0) {
computeSelect(searchEnv, mid, end0, mcs);
}
}