Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Let's say, we have... 50k points randomly allocated in 3D space, according to some volumetric function, so that in some parts of the space, points are closer together, but in other parts, they are further away. Every point has a random color (represented by an integer, for example)

I would like to find all points that:

  • Are within a certain (general) distance of each other, and
  • are of different color.

What is the fastest way to compute this?

Further, non-mandatory details:

My end goal, is to remove all points with the same color, until there are no more collisions. I would like to remove as few colors as possible, however, this is not mandatory I could simply remove all colors that are involved in any collisions AT ALL, though, it could result in a lower quality result.

The distance does not need to be exact. For instance, if an exact "collision radius" represents a perfect sphere, then I would be fine with the collision radius being the shape of, say, a cube. I am also fine with a trigger-happy solution. That is, I am fine if points get "detected" even if they are not too close. I just don't want this to happen very often, and I cannot accept points that are to close not being detected.

Also, I'm sure there is a family of algorithms devoted to this, but I can't for the life of me come up with any names... Knowing the name of an algorithm of this type would be immensely helpful.

share|improve this question
    
So what you have done so far ? –  omeid Jan 13 '12 at 6:54
    
Right now, nothing, though I am thinking of a recursive sweep approach if nothing better comes up here –  Georges Oates Larsen Jan 13 '12 at 8:33
    
the tricky part is the decision as to which point to remove. assume am simpler problem: if they are on a number line, spaced at 1,2,3,4,5,6. if the requirement is remove them if they are too close. and I start from the left I might remove 2,4,6. But If I start from the right I will remove 5,3,1. In the 3D case it will be even harder. Therefore the final result will not be deterministic. –  mhoran_psprep Jan 13 '12 at 11:23
    
someone asked a similar question in the past few weeks on this site. I can't find it, but you might want to look more carefully. There were some answers mentioning algorithms I had not previously heard of. –  psr Jan 13 '12 at 17:13
    
@psr: you might be talking about programmers.stackexchange.com/questions/120012/…? –  Alex ten Brink Jan 13 '12 at 19:47

6 Answers 6

up vote 2 down vote accepted

Here is what I would do:

  1. Divide the space into a regular lattice of cubes. The the length of th side of each cube should be half the minimum distance between points.
  2. For the first point, see which cube it is in. Add a flag to the cube that contains the point to indicate that that cube contains a point of that color.
  3. For the next point, see which cube is in. If none of the adjacent cubes are flagged with a point of that color, flag the cube with the color of the point like in (2). Otherwise throw the point away.
  4. If you still have unprocessed points, go to 3.

Advantages

The advantages of this approach are:

  1. It is fast
  2. It is easy to understand and to implement

Limitations

This algorithm has several limitations:

Use of Cubes

The algorithm will throw away too many points because it uses cubes instead of spheres. The question suggests that this is OK.

It it is a problem, however, this limitation can be overcome.

One way is to add the coordinates of the point to the flags. Then, when you test points in step (3) and you find that there is already a point in an adjacent cube, check the distance to that point before you decide whether to throw the point away.

Of course, this will slow things down / add complexity / increase the memory requirements of the algorithm.

Order of Testing Points

The number of points you end up with will depend on the order in which you test the points. To prove this, imagine the situation where you have just 3 red points, and that the cubes they fall into happen to be in a row:

+-----+-----+-----+
|     |   . |     |
|.    |     |     |
|     |     |   . |
+-----+-----+-----+

In this case, you could either throw away the point in the centre cube or the two points in the adjacent cubes.

To improve on the original algorithm, then, you could use the cubes as a basis to count the points of a given color that are tooo close to each other, then throw away the points that have the most points too close. I have not explored this in much depth: I'd need to work through a set of scenarios on paper to figure out the best way to do this.

Memory Use

Another potential problem is that the algorithm could use up quite a lot of memory.

A sensible first step would be to limit the number of cubes created to the minimum by calculate the bounding cuboid for all the points and then only using enough cubes to contain the bounding cuboid.

Another improvement would be to divide the problem into larger cubic regions that contain sub-sets of the full set of points, and processing each of these regions separately. Naturally, special care will need to be taken at the boundaries of thes regions.

share|improve this answer
    
I really like your approach! I am, alas, too tired to really think at this moment... But this sounds promising! When I do tests tomorrow, I will definitely be using this one. –  Georges Oates Larsen Jan 13 '12 at 8:35
1  
I have spent many hours now implementing a modified version of your algorithm. It works amazingly, thank you! –  Georges Oates Larsen Jan 14 '12 at 3:24

I don't know much about 3D algorithms but a little while ago I came across an Octree. Based on some reading I did, it is widely used in 3D applications because it essentially gives you a way to binary sort all your data points (or surfaces) in 3 different dimensions.

If you know the center in 3D space and your 50k points are all sorted using this data structure, seems it should be very easy to find all containing cubes that have only the points which would be within some radius.

share|improve this answer
    
An octree should be a reasonable optimization. If you limit the minimum sector size to the desired distance, the check is reduced from "all 50k points" to "the points in the current sector and up to 7 adjacent sectors". –  tdammers Jan 13 '12 at 6:55

The easiest approach would be a nested loop, checking the distance for each point-pair. This is off course the least efficient method, which you are not looking for probably.

A not uncommon approach in particle dynamics, is to divide your domain into boxes. You loop once over all particles to get some particle-id to box connectivity. Doing so, you can reduce the inner loop considerably, if you chose your box-size small.

I however wonder what you are trying to do here. Since you're first generating random points, and after this you delete them again, including some color, that is a bit weird. If you generate the points smarter, so with a different color by definition, and do some search during the point location generation. This will save you a lot of check afterwards.

share|improve this answer
    
This is for a videogame level generation, which generates a number of paths, and generates tunnels along those paths. Each tunnel-path is made up of a number of points. Each point's "color" represents waht tunnel it belongs to. The point is to eliminate tunnels that cross paths with each other (preventing strange glitches which would trap the player). I can do this by visualizing the paths, just as I explained above. This allows me to remove offending tunnels. I do it all afterwards, because the alternative is doing it over and over again with each segment of each tunnel –  Georges Oates Larsen Jan 13 '12 at 7:12
    
On another note... I like your idea of dividing into boxes, octrees I believe it is called, I may end up using those. However, I am hoping for a real solid full algorithm, something which perhaps relies on the octrees, and can use them efficiently –  Georges Oates Larsen Jan 13 '12 at 7:14

I can think of one optimization straight off.

If you traverse the space, starting at the bottom left hand corner, left to right then bottom to top you need only examine those points to the right and above.

There is a possibility (whatever algorithm you use!) that you will get different results if you start from a different point.

share|improve this answer

We'll start approaching your problem from the 'points are close' requirement, and check the colors after.

KD-trees are probably the best choice for you. You can build one in O(n log n) time (O(n log^2 n) using a simpler approach) on your points, after which you can answer questions 'give me the points at least this distance from this point' (a 'nearest neighbours' query) in O(k + log n) time, where k is the number of points returned. You can then run through these points and check their colors in O(k^2) time (you can get this down to O(k log k) if needed). This gives a total running time of O(n k log k + n log n) time.

If your data points are also moving around (they change their locations), then octrees are probably the best. KD-trees are quite bad at handling a mix of data changes and nearest neighbour queries. Do make sure you don't happen to hit the worst-case of octrees though: make sure you understand how they work and when they break, as you might just have points that are distributed in a bad way for octrees.

If you're feeling particularly algorithmic, you could even try to employ locality-sensitive hashing, but the above are probably easier and better.


You could also approach this problem starting from the colors. If it is rare that two points share the same color, you could also use an algorithm to find the points with the same colors, and then check the distances between these points to see if they need removing.

Analysis: sort-based duplicate finding gives you a O(n log n) first step (possibly improvable to O(n)), and then an O(n k^2) step to compare the distances between all colored nodes.

If k is very small, that's very efficient. For moderately large k (k > 100 probably) you could improve the performance of the last step by building a KD-tree for those equal-valued colors exactly as I described at the start, reducing the run time of the second bit to O(n + k (l + log k)) (where l is the number of nodes returned per nearest neighbour query).

You can even adapt this approach to moving points: build a binary tree (or a hashmap if you like them) containing octrees of points of the same color: inserting a new point then takes O(log n + log k) expected time.

share|improve this answer

It appears that the family of algorithms you are looking for are those used for cluster analysis.

Most algorithms of this family are not exact ones, as cluster analysis is traditionally performed on huge datasets, for which getting exact results is infeasible.

The main problem you will get with a clustering approach though, is that these algorithms will usually not care about a small number of outliners.

For your problem, I think a solution could look something like this:

  1. Cluster your point cloud to get clusters of points which are close together. Fine-tune this step to your specific requirements to get useful clusters.
  2. Use a different algorithm to examine the points inside each cluster and filter them based on your requirements. This algorithm can be one that a) delivers exact results and b) is possibly not very efficient, as it has to deal with a much smaller number of points.
share|improve this answer
    
Frank, thankyou very much for your answer :) It is going to take a large amount of time for me to delve into this, but your approach looks like it might work! It all depends on efficiency, I am going to have to look deeper into cluster analysis to know for sure –  Georges Oates Larsen Jan 13 '12 at 6:50
    
After doing further research, it turns out that the type of clustering I need (connectivity based clustering) has an efficiency of O(n^3). I have come up with an algorithm that uses plane sweeps which has a worst case of O(n^3), and I was hoping to find an algorithm with better efficiency –  Georges Oates Larsen Jan 13 '12 at 7:09

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.