CODEWITHSUNDEEP
algorithm
Defisher
Defisher

Reputation: 127

Query points in circle areas

Here is a picture to illustrate the problem:picture and features

In the picture there are some feature points shown as blue crosses. I know the coordinate (x,y) for all of the features. Now I want to query which features are inside the circle area (green circle). In practice, there are around 500 features and 300 queries (300 different circles, different centers and radius). I know the parameters (position, radius) of circles. Is there any good algorithm which can do this task?

Current I have two ideas.

  1. Most stupid one, just iterate through all of the features in each query. This is slower.
  2. A rough idea. Separate the whole picture to some sub-pictures. Put features into a tree structure according to sub-pictures, if features in the same sub-pictures, then put in the same leaf. In each query, find out which sub-picture are covered by the circle and check all of the feature in these sub-pictures.

Does anyone out there have any better ideas?

Upvotes: 2

Views: 1214

Answers (1)

Matt Timmermans
Matt Timmermans

Reputation: 59358

The most common way is to put the points into a K-D tree or similar: https://en.wikipedia.org/wiki/K-d_tree

To find the points within a circle, you get the list of points in order of increasing distance from the center, and stop when the distance exceeds the circle radius.

To get list of points in order of increasing distance, you can use a priority queue that can hold both points and internal nodes of the tree, which lets you remove them in order of distance.

For points (leaves), the distance is just the distance of the point from the center point. For internal nodes, the distance is the smallest distance from the center point to any point that could possibly be in that node.

To search, you just put the root of the tree in the priority queue, and repeat:

  1. Remove the head of the priority queue;
  2. If the head of the queue was a point, then it is the closest point in the tree that you have not yet returned. You know this, because if any internal node could possibly have a closer point, then it would have been returned first from the priority queue;
  3. If the head of the queue was an internal node, then put its children back into the queue

This will produce all the points in the tree in order of increasing distance from the center point.

Upvotes: 3

Related Questions