Add farthest point sampling filter

[haritha-j]

Farthest point sampling using euclidean distance, utlizing a naive algorithm. Fixes #3715

Maintainer edit: Current implementation https://en.wikipedia.org/wiki/Farthest-first_traversal#Algorithms

[haritha-j]

Also the test is very basic atm and I'd appreciate any and all input on what else I need to be testing for.

[SergioRAgostinho]

Also the test is very basic atm and I'd appreciate any and all input on what else I need to be testing for.

I'll address that once I review properly the implementation. By then I'll have a more clear insight of what we should test for. My idea will likely be to supply a predictable input in which we can manually infer what will be filtered.

[haritha-j]

I've just pushed the requested changes, sorry about the delay. Hopefully I didn't miss anything. p.s. Is the vs2017 build failure caused by some sort of network issue?

[kunaltyagi]

Could you put in a todo to add support to export/import distance metric in the filter? I don't want to create an issue, but that's something that I see as a useful feature a bit in the future, not in next several months.

[haritha-j]

Are there any more changes required on this from my side? If not @SergioRAgostinho could you give me your thoughts on the implementation and testing when you have the time?

[SergioRAgostinho]

Ok, let's discuss functionality testing. For my idea to work, we need to have control over which point gets picked first.

1. Manually create a point cloud with a low number of points n (5), with increasing distances between points. Create all points in a straight line, and triple the distance with each new addition e.g. (0,0,0), (1, 0, 0), (3, 0, 0), (9, 0, 0), (27, 0, 0), ...
2. Assume indexes from 1 to n. The following sequence will always happen: i -> n -> n-1 -> ... -> i+1 -> 1 -> i-1 -> ... -> 2. Some parts of this sequence will be entirely skipped if i is sampled from the beginning or end of the point cloud.

Now its a matter of controlling which points get sampled first: 1) we allow the user to specify it upon invoking filter 2) we set a seed, sample a single point to know what's the first one to be sampled with that seed. We set the same seed again before invoking filter a second time requesting our points we actually we want.

---

You also need to add checks to public methods you add. Currently it seems like you added all setters and getters, so those need to be checked accordingly.

[Morwenn]

Could you const-qualify the getters?

[haritha-j]

@SergioRAgostinho I implemented the testing methodology you suggested. I went with the second option;

2. we set a seed, sample a single point to know what's the first one to be sampled with that seed. We set the same seed again before invoking filter a second time requesting our points we actually we want.

I'm sampling the cloud with a sample_size of cloud_size-1 because; a. At that point there's only one point left out, therefore if all other points were correctly sampled, the final remaining point must be correct as well b. More importantly, if sample_size == cloud_size, the entire point cloud is returned as the result without any computation, so obviously the points won't be in the correct order.

p.s. I just remembered that I didn't add the checks for the setters and getters. Will get on that :)

[SergioRAgostinho]

I'm not sure if GitHub allows it, but trigger the request review once you finish for us to have a look. Alternatively just ping using the standard means.

[ThreeWaterGG]

hello! Really thank you for your contributions. Is this fasthest point sampling filter available now? I tried copy the .h and .hpp files to 'filters' and 'filters/impl' respectively, but the compiler cannot find the 'applyFilters' in .hpp. So need the .hpp re-compile first? Or waiting for the new release?

[kunaltyagi]

You can do:

1. git checkout haritha-j/farthestPointSampling
2. git rebase 383776a --onto master
3. git checkout -b new_feature

Then new_feature branch will be ready (here master can be whatever branch you need to use (eg: 1.10.1 or master, etc.))

[stale[bot]]

Marking this as stale due to 30 days of inactivity. Commenting or adding a new commit to the pull request will revert this.

[stale[bot]]

Marking this as stale due to 30 days of inactivity. Commenting or adding a new commit to the pull request will revert this.

[stale[bot]]

Marking this as stale due to 30 days of inactivity. Commenting or adding a new commit to the pull request will revert this.

[FabianSchuetze]

Hi!

This is a wonderful PR!

Would there be a possibility to continue working on it so that it could be merged into main? Would there also be an interest maybe in a GPU implementation?

[mvieth]

@haritha-j Would you be interested in continuing this pull request?

[FabianSchuetze]

Would it be fine if somebody else continues this already wonderful PR? Do you have any opinion about this, @haritha-j ?

[mvieth]

@FabianSchuetze I believe I have resolved most remaining issues. Would be great if you could also look over the files and do a review. Regarding a GPU implementation: I think currently it makes not much sense to put time into that. We should first wait and see how many people use this new class, whether any changes to the interface/any new functions are necessary, etc

[FabianSchuetze]

Thanks @mvieth for asking and for completing the PR! I have tried the code and it works well. I had two minor comments, but I do not think they are essential for merging.

Would be nice to do again a bit of work for PCL and I'll try to find another issue other than the GPU implementation then.