[Subsampling module] Get indices that produce the subsample

[jlazovskis]

In the theme of argsort being related to sort in Python, I would like to get the indices that produce subsamples constructed by the functions in the subsampling module ( link ).

Use case: I have a point cloud of (x,y)-values (observations in latitude and longitude), and each (x,y)-value has two other variables associated to it (climatic variables). I sparsify the (x,y)-values using sparsify_point_set¹, but to get back the associated variables, I have to find which original point matches every sparsified point, which feels very circuitous (given that I already have done the sparsification) and potentially imprecise (if I have (almost exactly) the same (x,y)-value twice, each with different associated variables).

Suggested solution: Include a new argument in each of the functions of the subsampling module (there are four there currently), something like bool argsample or bool get_indices, with a default value false, to ensure backwards compatibility.

• When false, the functions do the same thing they do now.
• When true, the values placed in the output iterator output_it are the indices of the elements selected from the input input_pts, instead of the elements themselves

As my suggestion is to modify existing functions, I am interested to hear if there are unforseen issues my solution would introduce, or if there is a more appropriate way to do this, or something else. Once (if) a solution is accepted, I am happy to implement it in a pull request.

Footnotes

1. I am aware this function uses Euclidean distance on the inputs, which is not the same as spherical distance for latitude and longitude inputs. I would like to have a distance option for these subsampling functions as well, but that is another discussion. ↩

[mglisse]

Having the index instead of the point sounds like a good idea, and if we were to start from scratch, I would probably make those functions return the indices. Since we have to deal with backwards compatibility, things are a bit more complicated.

1. I think the new parameter you suggest would have to be a template parameter, otherwise the same iterator would be forced to accept both points and indices even if only one is used at runtime. Function template parameters that need to be specified explicitly are not very nice.
2. We could add an optional IndexOutputIterator output_idx_it that by default would be Null_output_iterator, as we already have an optional DistanceOutputIterator dist_it in choose_n_farthest_points.
3. We could have separate functions, say sparsify_point_set_idx, that would return indices and contain most of the code, with the original functions like sparsify_point_set becoming small wrappers around the new functions.

[jlazovskis]

Thanks for explaining. As a user, working with similar-sounding, wrapper and non-wrapper functions increases the time necessary to understand what is going on, so I would not prefer option 3. And as a (novice) programmer, implementing a template parameter sounds like a sounds like a difficult task, one which I have not done before, so I would not prefer option 1. Which leaves option 2., and it does sound fairly reasonable.

Do I understand correctly that, with option 2., a subsampling function

• would need be modified so that the indices of the computed subsample are always placed in the new output index iterator, and
• by default the output index iterator is the null iterator, in which case the user has no way to immediately access the indices after the function has completed, and
• with a non-null iterator given for the output index iterator, the user can access the indices by starting at and iterating through this input iterator, after the function has completed.