C++ Algorithms – Finding All Nearby Points in a Point Cloud

The classic answer would be a trie which stores all rotations of words (in scrabble there is a very similar need and a very similar datastructure called a gaddag). It turns out you can do much better (B-tree of words where the lowest level is delta encoded), but the simplest thing you can do is store a sorted list of all rotations of all words in your dictionary and binary search for things. Example:

Our dictionary contains the word w = 'zoofoo', so we store:

sorted(w[i:] + '^' + w[:i] for i in range(len(w)))
['foo^zoo', 'o^zoofo', 'ofoo^zo', 'oo^zoof', 'oofoo^z', 'zoofoo^']

Hey look, one of those entries starts with 'foo'! We can find it via binary search, and reconstruct the original word from 'foo^zoo' by flipping around the ^.

If you can sort your input as well you can do a linear intersection of the input list and the rotation dictionary.

I hope it's ok to answer my own question. I believe I have found the optimal (without overcomplicating the problem) data structure for my problem. There was at least minor idiocy on my part for not recognising this earlier. The data doesn't need to be accessed by (x,y,z) but instead by (x, y, range of z (say 0 - 3)). This give a C++ struct as follows:

struct node {
  struct node *next;
  int zGroup;
  int z;
  50 bytes of misc data };

I can then address this through a 3D dynamic array (vectors):

vector< vector < vector < node* > > > Data;

Any given Data[x][y][zGroup] points to the first element of a linked list, the entirety of which is needed every time one element of it is needed. No value of this array is NULL, every one contains a linked-list of at least one element.

The third dimension of the array - the zGroup has jagged dimensions, but with dynamic arrays this isn't an issue. Given the data and computations being performed on it, I know that the max x and y values are set when the file is read and do not change, neither does the number of z groups on any given (x,y) line, the actual z-values of nodes may change, but they will remain inside the same z-groups, giving a constant-sized, fully populated array.

With the way that the file is structured it is also easy enough to page it in and out of memory if I am brought to do this with much larger data sets.