daviddoria/PatchBasedInpainting — comment on commit 4636c9a4102b98f81d29dfde2ed8dbcd37e01b15
File:  line 0
By mikael-s-persson:

Did you expect it not to work properly?
I refer you to my unit-test program:
https://github.com/mikael-s-persson/ReaK/blob/master/src/ReaK/ctrl/path_planning/test_vp_tree.cpp
that compares the performance of the linear search versus the DVP tree with 2-arity and 4-arity, as well as for a batch insertion of the vertices versus an incremental insertion of the vertices. The results can be found here:
https://github.com/mikael-s-persson/ReaK/blob/master/src/ReaK/ctrl/path_planning/test_vp_tree_results.dat
In which I think are in micro-seconds (time for one query) (and "-f" stands for the "fresh" DVP trees, that is, batch insertion).

The performance of my DVP-tree code is definitely not perfect (I still have some memory locality issues which explains the not-quite log-time performance) but the performance is reasonable compared to linear search. Also, there are other options to consider, like approximate search methods (like random-restarting a best-first search). And, when applying to your source-patch query, you might want to consider techniques which employ the fact that once you have found a patch to in-paint one pixel, it is likely that pixels close to it will also find the same patch (or one near to it) for their own in-painting.