Faced a task - there are quite a few (well, say, tens of thousands) points on the plane (maybe later they will be in three-dimensional space, but so far the question of the plane). It is required many times to solve a subtask - to choose for iterations points of a set that are at a distance of no more than L from some point (generally speaking, not included in this set of points).

Tell me what data structure to use, so as not to go through all the points in a row. I can not even figure out how to properly GET what exactly to look for - how to formulate a request.

The working language is C ++.

  • one
    Maybe R tree ? - Alexander Petrov
  • @AlexanderPetrov Thank you, look. - Harry
  • one
    If the points are relatively compact and the point being checked is also relatively close, then maybe a regular matrix? If there is a point in the cell, then the value is "1", if not - "0". The search will then be reduced to the enumeration of the cells of the matrix in the radius L Filling the matrix with new points will also be easy. - alexis031182
  • @ alexis031182 Hmm ... also an option :) Thank you! - Harry

2 answers 2

You can divide the plane into squares of size L. For each square, we save a list of points that have fallen into it. For a new point we find its square and iterate through the contents of this, as well as the adjacent squares. How to do this effectively from memory is described, for example, here: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.35.2471&rep=rep1&type=pdf

    If the task is massive, i.e. if the initial set of points is stable and a relatively large number of queries are made to this stable set of points, then a good option: the Euclidean Voronoi diagram for the initial set plus some algorithm for a fast point-location.

    When a query point arrives, we perform point-location to determine which region of the Voronoi diagram the query point has hit. After that, we consider this region of Voronoi and go around searching for the width of the neighboring regions of Voronoi until we obviously go beyond the radius L

    It is clear that building a Voronoi diagram and preparing for a point-location is a relatively "heavy" preprocessing, for which reason, as I said above, this approach makes sense with a stable input set and a relatively large number of requests to it, i.e. when preprocessing results remain relevant for a long time.

    Another option is kd-tree.

    • Generally speaking, the set of points is then planned to be changed ... - Harry