Many algorithms in nGI are modeled after algorithms available in the STL (Standard Template Library).

However, the STL algorithms work with iterators and in a one-dimensional fashion, while the nGI algorithms work with locators and views in a three-dimensional fashion. A locator is the 3D equivalent of an iterator, while a view is the 3D equivalent of a range.

Most algorithms are multi-core accelerated, and therefore the order in which the elements are processed is undefined.

The algorithms in this chapter are all also point algorithms, but we describe them here in their own chapter to emphasize their STL heritage. Many of the point algorithms described in the next chapter are implemented in terms of these basic algorithms.

Due to shortcomings of the C++ template mechanism, some of the algorithm variants have to take different names in order to satisfy C++ overload resolution. I.e. there are two variants of accumulate: accumulate and accumulate_region, where we would have preferred to use only one name. However, this is impossible, since because of the use of template parameters, C++ could not distinguish the overloads properly. Other examples are algorithms that take the suffix if, to distinguish between overloads, such as countif, find_if, etc.

This chapter lists the basic algorithms in alphabetic order. However, the original STL uses a different ordering scheme, which is mentioned here in tabular form.

Nonmutating algorithms

These algorithms operate on a view without changing the data that the view addresses. The algorithms return some information about the elements in the view. These algorithms are for inspection only and not for modification.

Algorithm	Description
count	Returns the number of elements in a view whose values match a specified value.
count_if	Returns the number of elements in a view whose values satisfy a specified condition.
equal	Compares two views element by element for equality.
find	This algorithm locates the position of the first occurrence of an element in a view that has a specified value.
find_if	This algorithm locates the position of the first occurrence of an element in a view that satisfies a specified condition.
min_element	Finds the first occurrence of smallest element in a specified view.
max_element	Finds the first occurrence of largest element in a specified view.
min_max_element	Finds the first occurrences of both the smallest and the largest element in a specified view.

Mutating algorithms

These algorithms operate on a view and may change the data that the view addresses. These algorithms are for modification.

Algorithm	Description
copy	Copies the values of a source view to a destination view.
fill	Assigns the same new value to every element in a specified view.
generate	Assigns the values generated by a function object to each element in a view.
for_each	Applies a specified function object to each element in a forward order within a view and returns the function object.
for_each_if	Applies a specified function object to each element of the first view in a forward order if the corresponding element of the second view resolves to true and returns the function object.
replace	Examines each element in a view and replaces it if it matches a specified value.
replace_if	Examines each element in a view and replaces it if it satisfies a specified predicate.
replace_copy	Examines each element in a source view and replaces it if it matches a specified value while copying the result into a new destination view.
replace_copy_if	Examines each element in a source view and replaces it if it satisfies a specified predicate while copying the result into a new destination view.
swap	Exchanges the elements of one view with the elements of another view.
transform	Applies a specified function object to each element in one, two or three source views and copies the return values of the function object into a destination view.

Numeric algorithms

These algorithms are of numeric nature.

Algorithm	Description
accumulate	Computes the sum of all the elements in a specified view including some initial value by computing successive partial sums.
inner_product	Computes the sum of the element-wise product of two views and adds it to a specified initial value.

accumulate

This algorithm accumulates all pixel values successively according to a specified binary operation.

template<typename V, typename T> 
T accumulate(V source, T value);

template<typename V, typename T, typename BINOP> 
T accumulate(V source, T value, BINOP binop);

template<typename V, typename T> 
T accumulate_region(V source, ngi::region const& region, T value);

template<typename V, typename T, typename BINOP> 
T accumulate_region(V source, ngi::region const& region, T value, 
    BINOP binop);

where V is a view type that is addressing the source view, T is the return type of the operation and BINOP is the accumulation function. The region parameter constrains the function to the region inside of the view only. The binop is a user defined function object that is called successively for every pixel. The binop takes two parameters - the partial result so far and the pixel value - and returns a new partial result. In the variants that do not take a binop as a parameter, it defaults to addition.

// adds all pixel values together
auto result = ngi::accumulate_region(source.get_view(), aoi, 0.0);

all_of

This algorithm returns true if all pixels satisfy a specified condition.

template<typename V, typename P> 
bool all_of(V source, P predicate);

template<typename V, typename P> 
bool all_of(V source, ngi::region const& region, P predicate);

where V is a view type that is addressing the source view and P is a predicate. The region parameter constrains the function to the region inside of the view only. The predicate is a user defined function object that defines the condition to be satisfied. A predicate takes a single argument of the view’s pixel type and returns true or false.

The algorithm supports parallel execution on multiple cores.

// result is true, if all pixels inside the source view are
// bigger than 127
auto result = ngi::all_of(source.get_view(), aoi,
    [] (unsigned char const& v) {
        return v > 127; });

any_of

This algorithm returns true if any pixel satisfies a specified condition.

template<typename V, typename P> 
bool any_of(V source, P predicate);

template<typename V, typename P> 
bool any_of(V source, ngi::region const& region, P predicate);

where V is a view type that is addressing the source view and P is a predicate. The region parameter constrains the function to the region inside of the view only. The predicate is a user defined function object that defines the condition to be satisfied. A predicate takes a single argument of the view’s pixel type and returns true or false.

The algorithm supports parallel execution on multiple cores.

// result is true, if any pixel inside the source view is
// bigger than 127
auto result = ngi::any_of(source.get_view(), aoi,
    [] (unsigned char const& v) {
        return v > 127; });

copy

This algorithm copies pixels in a source view to a destination view.

template<typename VS, typename VD> 
void copy(VS source, VD destination);

template<typename VS, typename VD> 
void copy(VS source, VD destination, ngi::region const& region);

where VS is a view type that is addressing the source view and VD is a view type that is addressing the destination view. If the source and destination views have different sizes, the intersection is used. The region parameter constrains the function to the region inside of the view only. If the source and destination view pixel types are different, the values are converted.

The algorithm supports parallel execution on multiple cores. Since the order of execution is undefined, when the algorithm executes on multiple cores, you cannot safely use copy with views that address the same data in an overlapping manner.

// copy from source view to destination view
ngi::copy(source.get_view(), dest.get_view(), aoi);

count

This algorithm counts and returns the number of pixels in a view whose values match a specified value or satisfy a specified condition.

template<typename V> 
ptrdiff_t count(V source, typename V::value_type const& value);

template<typename V> 
ptrdiff_t count(V source, ngi::region const& region, 
    typename V::value_type const& value);

template<typename V, typename P> 
ptrdiff_t count_if(V source, P predicate);

template<typename V, typename P> 
ptrdiff_t count_if(V source, ngi::region const& region, 
    P predicate);

where V is a view type that is addressing the source view and P is a predicate. The region parameter constrains the function to the region inside of the view only. The predicate is a user defined function object that defines the condition to be satisfied. A predicate takes a single argument of the view’s pixel type and returns true or false.

The algorithm supports parallel execution on multiple cores.

// count the number of pixels in the source view with the value 255
auto n = ngi::count(source.get_view(), aoi, 255);

equal

This algorithm compares pairwise pixels in two views.

template<typename V> 
bool equal(V first, V second);

template<typename V> 
bool equal(V first, V second, ngi::region const& region);

template<typename V1, typename V2, typename P> 
bool equal(V1 first, V2 second, P predicate);

template<typename V1, typename V2, typename P> 
bool equal(V1 first, V2 second, ngi::region const& region, 
    P predicate);

where V, V1 and V2 are view types that are addressing the two views and P is a predicate. If the two views have different sizes, the intersection is used. The region parameter constrains the function to the region inside of the view only. If the source and destination view pixel types are different, a binary predicate needs to be used to establish an equivalence relation.

The algorithm supports parallel execution on multiple cores.

// compare two views
auto result = ngi::equal(source.get_view(), second.get_view());

fill

This algorithm sets the pixels in a view to a specified value.

template<typename V> 
void fill(V destination, typename V::value_type const& value);

template<typename V> 
void fill(V destination, ngi::region const& region, 
    typename V::value_type const& value);

where V is a view type that is addressing the destination view. The region parameter constrains the function to the region inside of the view only.

The algorithm supports parallel execution on multiple cores.

// set all pixels in the destination view to 127
ngi::fill(dest.get_view(), aoi, 127);

find

This algorithm finds the locator pointing to the first pixel in a view whose value matches a specified value or satisfies a specified condition.

template<typename V> 
typename V::locator_type find(V source, 
    typename V::value_type const& value);

template<typename V> 
typename V::locator_type find(V source, 
    ngi::region const& region, typename V::value_type const& value);

template<typename V, typename P> 
typename V::locator_type find_if(V source, P predicate);

template<typename V, typename P> 
typename V::locator_type find_if(V source, 
    ngi::region const& region, P predicate);

where V is a view type that is addressing the source view and P is a predicate. The region parameter constrains the function to the region inside of the view only. The predicate is a user defined function object that defines the condition to be satisfied. A predicate takes a single argument of the view’s pixel type and returns true or false.

The algorithm iterates through the planes from front to back, inside each plane from top to bottom and on each line from left to right. Thus, the first pixel found is the one most at the front, top, left position.

// find the locator that points to the first pixel in the source view 
// with the value 255
auto loc = ngi::find(source.get_view(), aoi, 255);

find_position

This algorithm finds the position of the first pixel in a view whose value matches a specified value or satisfies a specified condition.

template<typename V> 
ngi::point_3d<int> find_position(V source, 
    typename V::value_type const& value);

template<typename V> 
ngi::point_3d<int> find_position(V source, 
    ngi::region const& region, 
    typename V::value_type const& value);

template<typename V, typename P> 
ngi::point_3d<int> find_position_if(V source, P predicate);

template<typename V, typename P> 
ngi::point_3d<int> find_position_if(V source, 
    ngi::region const& region, P predicate);

where V is a view type that is addressing the source view and P is a predicate. The region parameter constrains the function to the region inside of the view only. The predicate is a user defined function object that defines the condition to be satisfied. A predicate takes a single argument of the view’s pixel type and returns true or false.

The algorithm iterates through the planes from front to back, inside each plane from top to bottom and on each line from left to right. Thus, the first pixel found is the one most at the front, top, left position.

// find the first pixel in the source view with the value 255
auto position = ngi::find_position(source.get_view(), aoi, 255);

for_each

Applies a specified function object to each pixel in a view and returns the function object.

template<typename V, typename F> 
F for_each(V source, F function);

template<typename V, typename F> 
F for_each(V source, ngi::region const& region, F function);

where V is a view type that is addressing the source view and F is a function object. The region parameter constrains the function to the region inside of the view only. The function object is user defined and takes one parameter of the view’s pixel reference type. The algorithm returns the function object, after it has been applied to all pixels. The function object is free to carry state that needs to be available when the algorithm returns.

The algorithm iterates through the planes from front to back, inside each plane from top to bottom and on each line from left to right.

// add 50 to every pixel
ngi::for_each(dest.get_view(), aoi,
    [] (unsigned char & v) {
        v += 50; });

generate

Assigns the values generated by a specified function object to each pixel in a view.

template<typename V, typename F> 
void generate(V source, F function)

template<typename V, typename F> 
void generate(V source, ngi::region const& region, F function);

where V is a view type that is addressing the source view and F is a function object. The region parameter constrains the function to the region inside of the view only. The function object is user defined, takes no parameter and returns a pixel value. The function object does not need to return the same value each time it is called. It may, for example, read from a file or refer to and modify state.

The algorithm iterates through the planes from front to back, inside each plane from top to bottom and on each line from left to right.

// assign 100 to every pixel
ngi::generate(dest.get_view(), aoi,
    [] () -> unsigned char {
        return 100; });

inner_product

This algorithm computes the inner product between two views.

template<typename V1, typename V2, typename T> 
T inner_product(V1 source1, V2 source2, T value);

template<typename V, typename T, typename BINOP1, typename BINOP2> 
T inner_product(V1 source1, V2 source2, T value, BINOP1 binop1, 
    BINOP2 binop2);

template<typename V1, typename V2, typename T> 
T inner_product(V1 source1, V2 source2, ngi::region const& region, 
    T value);

template<typename V1, typename V2, typename T, typename BINOP1, 
    typename BINOP2> 
T inner_product(V1 source1, V2 source2, ngi::region const& region, 
    T value, BINOP1 binop1, BINOP2 binop2);

where V1 and V2 are view types that are addressing the source views, T is the return type of the operation and BINOP1 and BINOP2 are the sum and product functions. The region parameter constrains the function to the region inside of the view only. Binop1 and binop2 are user defined function objects that are called successively for every pixel, one to calculate the pixel-wise product between the two views and the other to a successively accumulate the results. In the variants that do not take binops as parameters, they default to addition and multiplication.

// compute inner product
double result = ngi::inner_product(
    source1.get_view(), source2.get_view(), aoi, 0.0);

max_element

This algorithm finds the locator pointing to the first pixel in a view with the maximum value.

template<typename V> 
typename V::locator_type max_element(V source);

template<typename V> 
typename V::locator_type max_element(V source, 
    ngi::region const& region);

template<typename V, typename P> 
typename V::locator_type max_element_if(V source, P predicate);

template<typename V, typename P> 
typename V::locator_type max_element_if(V source, 
    ngi::region const& region, P predicate);

where V is a view type that is addressing the source view and P is a predicate. The region parameter constrains the function to the region inside of the view only. The predicate is a user defined function object that takes two arguments and should return when the first is less than the second and false otherwise.

The algorithm supports parallel execution on multiple cores.

// find the locator that points to the first pixel in the source 
// view with the maximum value
auto loc = ngi::max_element(source.get_view(), aoi);

max_position

This algorithm finds the position of the first pixel in a view with the maximum value.

template<typename V> 
ngi::point_3d<int> max_position(V source);

template<typename V> 
ngi::point_3d<int> max_position(V source, 
    ngi::region const& region);

template<typename V, typename P> 
ngi::point_3d<int> max_position_if(V source, P predicate);

template<typename V, typename P> 
ngi::point_3d<int> max_position_if(V source, 
    ngi::region const& region, P predicate);

where V is a view type that is addressing the source view and P is a predicate. The region parameter constrains the function to the region inside of the view only. The predicate is a user defined function object that takes two arguments and should return when the first is less than the second and false otherwise.

The algorithm supports parallel execution on multiple cores.

// find the position of the first pixel in the source view
// with the maximum value
auto position = ngi::max_position(source.get_view(), aoi);

min_element

This algorithm finds the locator pointing to the first pixel in a view with the minimum value.

template<typename V> 
typename V::locator_type min_element(V source);

template<typename V> 
typename V::locator_type min_element(V source, 
    ngi::region const& region);

template<typename V, typename P> 
typename V::locator_type min_element_if(V source, P predicate);

template<typename V, typename P> 
typename V::locator_type min_element_if(V source, 
    ngi::region const& region, P predicate);

where V is a view type that is addressing the source view and P is a predicate. The region parameter constrains the function to the region inside of the view only. The predicate is a user defined function object that takes two arguments and should return when the first is less than the second and false otherwise.

The algorithm supports parallel execution on multiple cores.

// find the locator that points to the first pixel in the source 
// view with the minimum value
auto loc = ngi::min_element(source.get_view(), aoi);

min_position

This algorithm finds the position of the first pixel in a view with the minimum value.

template<typename V> 
ngi::point_3d<int> min_position(V source);

template<typename V> 
ngi::point_3d<int> min_position(V source, 
    ngi::region const& region);

template<typename V, typename P> 
ngi::point_3d<int> min_position_if(V source, P predicate);

template<typename V, typename P> 
ngi::point_3d<int> min_position_if(V source, 
    ngi::region const& region, P predicate);

where V is a view type that is addressing the source view and P is a predicate. The region parameter constrains the function to the region inside of the view only. The predicate is a user defined function object that takes two arguments and should return when the first is less than the second and false otherwise.

The algorithm supports parallel execution on multiple cores.

// find the position of the first pixel in the source view
// with the minimum value
auto position = ngi::min_position(source.get_view(), aoi);

none_of

This algorithm returns true if no pixel in a view or a region satisfies a specified condition.

template<typename V, typename P> 
bool none_of(V source, P predicate);

template<typename V, typename P> 
bool none_of(V source, ngi::region const& region, P predicate);

where V is a view type that is addressing the source view and P is a predicate. The region parameter constrains the function to the region inside of the view only. The predicate is a user defined function object that defines the condition to be satisfied. A predicate takes a single argument of the view’s pixel type and returns true or false.

The algorithm supports parallel execution on multiple cores.

// result is true, if no pixel inside the source view is
// bigger than 127
auto result = ngi::none_of(source.get_view(), aoi,
    [] (unsigned char const& v) {
        return v > 127; });

replace

This algorithm replaces pixel values in a view or a region if they satisfy a specified condition.

template<typename V> 
void replace(V source, 
    typename V::value_type const& old_value, 
    typename V::value_type const& new_value);

template<typename V> 
void replace(V source, ngi::region const& region, 
    typename V::value_type const& old_value, 
    typename V::value_type const& new_value);

template<typename V, typename P> 
void replace_if(V source, P predicate, 
    typename V::value_type const& new_value);

template<typename V, typename P> 
void replace_if(V source, ngi::region const& region, 
    P predicate, typename V::value_type const& new_value);

where V is a view type that is addressing the source view and P is a predicate. The region parameter constrains the function to the region inside of the view only. The predicate is a user defined function object that defines the condition to be satisfied. A predicate takes a single argument of the view’s pixel type and returns true or false. The overloads with no predicate have a parameter named old_value, which is used instead.

The algorithm supports parallel execution on multiple cores.

// replaces all pixels that are bigger than 127 with 200
ngi::replace_if(dest.get_view(), aoi,
    [] (unsigned char const& v) {
        return v > 127; }, 
    200);

replace_copy

This algorithm copies pixel values from a view or a region to a destination and replaces them with a new value if they satisfy a specified condition.

template<typename S, typename D> 
void replace_copy(S source, D destination,
    typename S::value_type const& old_value, 
    typename D::value_type const& new_value);

template<typename V, typename D> 
void replace_copy(V source, D destination, 
    ngi::region const& region,
    typename V::value_type const& old_value, 
    typename V::value_type const& new_value);

template<typename V, typename D, typename P> 
void replace_copy_if(V source, D destination, P predicate, 
    typename V::value_type const& new_value);

template<typename V, typename D, typename P> 
void replace_copy_if(V source, D destination,
    ngi::region const& region, P predicate, 
    typename V::value_type const& new_value);

where S and D are view types that are addressing the source and destination views and P is a predicate. The region parameter constrains the function to the region inside of the view only. The predicate is a user defined function object that defines the condition to be satisfied. A predicate takes a single argument of the view’s pixel type and returns true or false. The overloads with no predicate have a parameter named old_value, which is used instead.

The algorithm supports parallel execution on multiple cores.

ngi::replace_copy(
    source.get_view(), dest.get_view(), aoi,
    255, 50);

swap

This algorithm swaps pixel values from one view or a region with pixel values from another view.

template<typename V1, typename V2> 
void swap(V1 source, V2 destination,
    typename V1::value_type const& old_value, 
    typename V2::value_type const& new_value);

template<typename V1, typename V2> 
void swap(V1 source, V2 destination, 
    ngi::region const& region,
    typename V1::value_type const& old_value, 
    typename V2::value_type const& new_value);

where V1 and V2 are view types that are addressing the two views. The region parameter constrains the function to the region inside of the view only.

The algorithm supports parallel execution on multiple cores.

// swaps two views
ngi::swap(source.get_view(), second.get_view(), aoi);

transform

This algorithm calls a function for every source pixel from a view or a region to a destination and writes the result pixelwise to a destination view.

template<typename VS, typename D, typename F> 
void transform(VS source, D destination, F function);

template<typename VS, typename D, typename F> 
void transform(VS source, D destination, 
    ngi::region const& region, F function);

template<typename VS1, typename VS2, typename D, typename F> 
void transform2(VS1 source1, VS2 source2, D destination, 
    F function);

template<typename VS1, typename VS2, typename D, typename F> 
void transform2(VS1 source1, VS2 source2, D destination, 
    ngi::region const& region, F function);

template<typename VS1, typename VS2, typename VS3, typename D, 
    typename F> 
void transform3(VS1 source1, VS2 source2, VS3 source3, 
    D destination, F function);

template<typename VS1, typename VS2, typename VS3, typename D, 
    typename F> 
void transform3(VS1 source1, VS2 source2, VS3 source3, 
    D destination, ngi::region const& region, F function);

where VS, VS1, VS2 and D are view types that are addressing the source and destination views. The region parameter constrains the function to the region inside of the view only. The function is a user defined function object that takes a suitable number of parameters matching the view types and returns a pixel value with a suitable return type.

The algorithm supports parallel execution on multiple cores.

// complements every pixel
ngi::transform(source.get_view(), dest.get_view(), aoi,
    [] (unsigned char const& v) -> unsigned char{
        return ~v; });