15

I am making a simple game and stumbled upon this problem. Assume several points in 2D space. What I want is to make points close to each other interact in some way.

Let me throw a picture here for better understanding of the problem: image of the problem

Now, the problem isn't about computing the distance. I know how to do that.

At first I had around 10 points and I could simply check every combination, but as you can already assume, this is extremely inefficient with increasing number of points. What if I had a million of points in total, but all of them would be very distant to each other?

I'm trying to find a suitable data structure or a way to look at this problem, so every point can only mind their surrounding and not whole space. Are there any known algorithms for this? I don't exactly know how to name this problem so I can google exactly what I want.

If you don't know of such known algorighm, all ideas are very welcome.

Saraph
  • 992
  • 1
  • 11
  • 25
  • 1
    I dont know if is the best idea, but it is better than nothing. Store your 2D space in this structure: array(array(bool)), true if there is a point, false if there is not. So when you want to find points in the radius, you don't have to evaluate the entire matrix, just the positions that are inside the radius – pablito.aven Jun 29 '15 at 17:16
  • https://en.wikipedia.org/wiki/K-d_tree – amit Jun 29 '15 at 17:18
  • @pablito.aven That was actually one of my first ideas. Still don't really like the idea of checking every single pixel around you. – Saraph Jun 29 '15 at 18:16
  • 1
    See previous solution on using [quadtrees](http://stackoverflow.com/questions/6698484/using-a-quadtree-to-get-all-points-within-a-bounding-circle) – dpmcmlxxvi Jun 29 '15 at 20:16
  • @Saraph: Is the interaction radius fixed such that you'll always be considering the same radius and every point within that radius will interact with the focal point? – Richard Jun 05 '17 at 03:38

6 Answers6

18

This is a range searching problem. More specifically - the 2-d circular range reporting problem.

Quoting from "Solving Query-Retrieval Problems by Compacting Voronoi Diagrams" [Aggarwal, Hansen, Leighton, 1990]:

  • Input: A set P of n points in the Euclidean plane E²
  • Query: Find all points of P contained in a disk in E² with radius r centered at q.

The best results were obtained in "Optimal Halfspace Range Reporting in Three Dimensions" [Afshani, Chan, 2009]. Their method requires O(n) space data structure that supports queries in O(log n + k) worst-case time. The structure can be preprocessed by a randomized algorithm that runs in O(n log n) expected time. (n is the number of input points, and k in the number of output points).

The CGAL library supports circular range search queries. See here.

Lior Kogan
  • 19,919
  • 6
  • 53
  • 85
7

You're still going to have to iterate through every point, but there are two optimizations you can perform:

1) You can eliminate obvious points by checking if x1 < radius and if y1 < radius (like Brent already mentioned in another answer).

2) Instead of calculating the distance, you can calculate the square of the distance and compare it to the square of the allowed radius. This saves you from performing expensive square root calculations.

This is probably the best performance you're gonna get.

adao7000
  • 3,632
  • 2
  • 28
  • 37
  • I think I can make very good use of optimization number 1 by keeping 2 heaps: one sorted by `x` and one by `y` coordination. When points move, heapsort call should be very cheap given that these coordinations would only change very slightly each iteration. I'll be back (no movie quote intended) after playing around with this a bit. – Saraph Jun 29 '15 at 18:40
3

This looks like a nearest neighbor problem. You should be using the kd tree for storing the points.

https://en.wikipedia.org/wiki/K-d_tree

Harman
  • 1,571
  • 1
  • 19
  • 31
3

Space partitioning is what you want.. https://en.wikipedia.org/wiki/Quadtree

CaldasGSM
  • 3,032
  • 16
  • 26
  • Yes, space partitioning; no quadtree. The problem is that in sparse areas quadtree cells will be far bigger than the radius; in crowded areas you can have quadtree cells far far smaller than radius. – Swiss Frank May 18 '19 at 08:59
2

If you could get those points to be sorted by x and y values, then you could quickly pick out those points (binary search?) which are within a box of the central point: x +- r, y +- r. Once you have that subset of points, then you can use the distance formula to see if they are within the radius.

Brent Washburne
  • 12,904
  • 4
  • 60
  • 82
  • 1
    Practically speaking this approach might work... but what if there were a million points in that box? You're minimizing the number of points you have to check with the distance formula but there are no guaranteed bounds or improvements in runtime – adao7000 Jun 29 '15 at 17:20
  • I don't think there's any way to sort a collection of two dimensional points that guarantees that each point will be close to its neighbors. For example, If you sort by x and then use y for tie breakers, you might end up with an array like `[(0,0), (1, 999), (2,0)]`. (I guess you could sort by euclidean distance from a reference point, but then you're back where you started with O(n) run time). So you could narrow down your search to points with a nearby x coordinate, or a y coordinate, but not both. – Kevin Jun 29 '15 at 17:21
  • @Kevin you could have two indexes, one for `x` and one for `y`, and then find the intersection of both (like a JOIN clause in SQL). Even if there were a million points, that's just a few megabytes of storage. – Brent Washburne Jun 29 '15 at 18:46
0

I assume you have a minimum and maximum X and Y coordinate? If so how about this.

Call our radius R, Xmax-Xmin X, and Ymax-Ymin Y.

Have a 2D matrix of [X/R, Y/R] of double-linked lists. Put each dot structure on the correct linked list.

To find dots you need to interact with, you only need check your cell plus your 8 neighbors.

Example: if X and Y are 100 each, and R is 1, then put a dot at 43.2, 77.1 in cell [43,77]. You'll check cells [42,76] [43,76] [44,76] [42,77] [43,77] [44,77] [42,78] [43,78] [44,78] for matches. Note that not all cells in your own box will match (for instance 43.9,77.9 is in the same list but more than 1 unit distant), and you'll always need to check all 8 neighbors.

As dots move (it sounds like they'd move?) you'd simply unlink them (fast and easy with a double-link list) and relink in their new location. Moving any dot is O(1). Moving them all is O(n).

If that array size gives too many cells, you can make bigger cells with the same algo and probably same code; just be prepared for fewer candidate dots to actually be close enough. For instance if R=1 and the map is a million times R by a million times R, you wouldn't be able to make a 2D array that big. Better perhaps to have each cell be 1000 units wide? As long as density was low, the same code as before would probably work: check each dot only against other dots in this cell plus the neighboring 8 cells. Just be prepared for more candidates failing to be within R.

If some cells will have a lot of dots, each cell having a linked list, perhaps the cell should have an red-black tree indexed by X coordinate? Even in the same cell the vast majority of other cell members will be too far away so just traverse the tree from X-R to X+R. Rather than loop over all dots, and go diving into each one's tree, perhaps you could instead iterate through the tree looking for X coords within R and if/when you find them calculate the distance. As you traverse one cell's tree from low to high X, you need only check the neighboring cell to the left's tree while in the first R entries.

You could also go to cells smaller than R. You'd have fewer candidates that fail to be close enough. For instance with R/2, you'd check 25 link lists instead of 9, but have on average (if randomly distributed) 25/36ths as many dots to check. That might be a minor gain.

Swiss Frank
  • 1,985
  • 15
  • 33