Discussion
In the sample we reduced the total runtime from 8 days to 21 seconds (see Table 2 for details). The sample data of course is different from real-world data (i.e., from a GIS). But the runtime improvements shown here are comparable to those we encountered with data from GIS. Batch processing usually not only searches in data, but it also performs some action on it, which of course costs runtime that is not reduced by improving search. In the task I had to perform, the overall task was reduced from a number of days to a few hours. Also impressive is the difference between optimized and debug compiled code, which came to about factor 10.
In this solution it becomes crucial to set the right width of the single quadrants: Setting them too small (i.e., 10 meter in the sample) increases the memory and the time to setup the data of CQuadMap. Setting it too large (i.e., 100 meter) more and more reduces the acceleration introduced by the algorithm. On real-world data I found that 25 meters is more appropriate. Below 10 meters, the amount of memory used soon reaches 1 GB and more. Keep in mind, that enlarging the size of the quadrants does not affect the search result though: It only leads to more lines checked as candidate, but it will still return the nearest element. Also still only those elements are returned that are not more far away than the maximum search width, even if the quadrant size is larger then this. It is illegal though to use a smaller quadrant size than the maximum search width.
Of course your units used can also be micrometers or miles.
The time to execute linear search grows linear with the number of lines used. When connecting all lines to each other it grows exponentially by n^2. The search time of CQuadMap turns out to be more or less linear and independent of the number of lines inserted. Connecting 1,000,000 lines to each other of course is a heavy task, but also when doing this with only 10,000 lines the runtime is reduced impressively from more than one minute to 188ms -- making such a task possible in real time (see table 2).
Conclusion
In this article I introduced a algorithm that reduces the search time for the next line of a given point to a fraction compared to linear search. The performance gain lays between 420 and 36,000 depending on the number of lines existing. The algorithm is implemented in C++ and publicly available.
