find_cross.m, version 2.1

Find and/or estimate level crossings using a combination of search and interpolation.

OVERVIEW

find_cross() uses a combination of search and interpolation to estimate the X values at which the dependent variable Y crosses a specified target level y_target. If there are multiple level crossings, find_cross finds all of the level crossings. This function has been designed to work with both continuous- and discrete-valued Y's. Thus, if the input sequence "kisses" the specified level but does not actually cross it, this is not counted as a crossing. If there are two or more consecutive Y values that match the specified target, each of them is counted as a crossing.

Calling syntax:

X_cross= find_cross(X, Y, Y_target)

where:

X is a column vector containing a sequence of monotone increasing values of the independent variable.

Y is a column vector containing values of the dependent variable.

Y_target is the desired level crossing.

X_cross (the returned value) is the estimated value of X at which the dependent variable crosses the level Y_target.

ACKNOWLEDGMENT

This code uses a vectorized algorithm that was suggested to me by Paul Kienzle of the National Institute of Standards and Technology, Gaithersburg, MD.

COMMENTS ON THE ALGORITHM

The algorithm consists of two phases. In the first phase, the target level is subtracted out to reduce the problem to one of finding zero crossings, and indices in the vicinity of crossings are then identified in a computationally-efficient manner using vector operations. In the second phase, each crossing is considered in turn. "Exact crossings", i.e., where a zero is surrounded by values having opposite signs, are simply copied to the output array. Non-exact crossings, i.e., where a pair of Y coordinates bracket zero, are handled via interpolation.

After the initial phase, the number of indices to consider should be very small, so there is no longer much impetus for using vector operations. If I were going to try to vectorize this phase of the process, then I would find all of the exact zeroes first and remove them so that the linear interpolation could be done via vector operations with no risk of a divide-by-zero condition. The two sets of zero-crossings (the exact zeros and the estimated zeroes found by interpolation) would have to be merged together and sorted. I'm not convinced that this would be either cleaner or generally faster.

REVISION HISTORY

Version 2.1, 9 May 2009, Phillip M. Feldman:

As per a suggestion from Antoni J. Canós, I added a line of code at the end of the function to eliminate repeated values in the output.

Version 2.0, 9 Nov. 2005, Phillip M. Feldman:

Vectorized the code for faster execution. The underlying assumption is that, even for a large dataset, the number of level crossings tends to be small, so that the initial step of finding array indices in the vicinity of level crossings is the critical one from the standpoint of performance. The subsequent step of estimating level crossing locations via interpolation can be done within a loop.

Version 1.1, Phillip M. Feldman:

Fixed code to handle situation where Y_target exactly matches Y(i), with Y(i-1) and Y(i+1) bracketing Y_target. Previously, this was not being recognized as a crossing.