Hi everybody,
I have the following problem:
I have some points in a 2D space, and I need to find fields of close points in it, the maximum distance between the points is given by the user, the algorithm needs to be fast because sometimes there are a lot of points.
Thank you for your help! ;-)
> I have the following problem:
> I have some points in a 2D space, and I need to find
> fields of close points in it, the maximum distance
> between the points is given by the user, the
> algorithm needs to be fast because sometimes there
> are a lot of points.
What exactly are fields of close points?
And what number are you talking about when you say a lot of points?
Ok, I'm going to be more specific.
Here is an image with fields of points:
http://i84.photobucket.com/albums/k22/hasame_2006/fields.jpg
These points are in a 2D space.
When I talk about a lot of points, I talk about 1000 points, sometimes it could be less or it could be more.
Thank you!
Message was edited by:
ricard.lopez
> Ok, I'm going to be more specific.
> Here is an image with fields of points:
> http://i84.photobucket.com/albums/k22/hasame_2006/fields.jpg
> These points are in a 2D space.
But what are the rules? When does a point belong to a field? (only when it's in scope of the distance a user enters?)
Can fields overlap? Take the points (1,1) (2,1) (3,1) and (1,3) for example. And the distance is 1. What fields are there now?
Are there other rules?
> When I talk about a lot of points, I talk about 1000
> points, sometimes it could be less or it could be
> more.
> Thank you!
Operating on graphs with 1000 vertices is no problem for a computer.
Fields cannot overlap, in your example the fields are
- (1,1)(2,1)(3,1)
- (1,3)
Because between (1,1) and (2,1) the distance is 1, and between (2,1) and (3,1) the distance is also 1, so the three points make a field. The point (1,3) is too far from any point from the field, so it makes another field. If there were another point (1,2) then this one and (1,3) would join the field, then there would be only one field with all the points.
I hope now you understand my problem
Thank you!
When you mentioned points and distances I was immediately thinking of a kd-tree (see e.g. [1]) where you can do a cheap range query that gives you all the points within a rectangle. It would have been more suitable, however, if the fields overlapped.
This new situation needs some more thinking. ;-)
Just to be sure:
Two points p and q belong to the same field iff there is a sequence of points p=p_1, ..., p_n, q=q such that the distance between every p_i and p_(i+1) <=d ?
[1] http://en.wikipedia.org/wiki/Kd-tree
With 1000 points a quadratic solution should easily be fine, but if you want it to scale then there are two halves to the problem.
1. Finding points near a point. It may suffice to sort by x-co-ord (O(n lg n)) and then scan the neighbourhood. For larger problems you could use a spatial tree, such as the kd-tree already mentioned.
2. Merging fields. There's an abstract data type which supports fast merging of sets - I think it's called a union set, but Google isn't forthcoming. Basically it works with more trees. Initially each element is in a tree of its own. To merge two sets you create a new root with the sets as children. Given an element you get the set it's in by following parent references until you reach the root.
You can do a 2d bucket sort into a sparse array, with buckets d/sqrt(2) wide, so all points inside a bucket are within d of each other, then join adjacent buckets if any points in either overlap. I'd need to think a bit about the average order, since you can halt when unified with all adjacent buckets, and how many comparisons depends on how sparse your data is, but it seems to go at around 2N at around 100<N><1000. (above 1000 linked nodes Firefox's svg gives up on my laptop)
There's a svg + javascript implementation at http://tincancamera.com/examples/xul/graphs/grouping.svg - apologies for my isp's lack of mime-type awareness.
If you were in Java, you'd use linked lists for the groups rather than arrays, since you only ever append to them or iterate forwards.
Pete
>2. Merging fields. There's an abstract data type which supports fast merging of
>sets - I think it's called a union set, but Google isn't forthcoming. Basically it
>works with more trees. Initially each element is in a tree of its own. To merge
>two sets you create a new root with the sets as children. Given an element you
>get the set it's in by following parent references until you reach the root.
Yes, that's what came up my mind in the meantime, too. A better search term is
"union find data structure". Iirc, a good optimization is that whenever you
traverse a path from a node to the root, you flatten the tree by setting all the
nodes on the path as direct children of the root.