vb.net code for advanced data structures

[GFM GToeroe]

Hi!

Actually I have to solve the following problems:

Given is a dynamic set S of (moving, vanishing and arising) points
(2D). It could be the case that |S|>100 or even >1000 but not >20000.
In general almost all of the current members of S are moving all the
time.

For a single point p of S I want to find

A) All other points which are in a given circle around p
B) The nearest neighbor of p

I think a voronoi partition of the plane with respect to S should be
the key to solve the problem. So I look for a vb implementation of this
algorithm. It would be fine to have an algorithm which also can handle
insert and delete of points and which is able to deliver an almost
correct voronoi diagram for moved objects without a complete new
calculation if the shift is sufficient small.

Can anybody help?

GFM GToeroe

 

[Patrice]

Not sure if Delaunay Triangluation could help but this article says it"s
closely related and it have several implementations :
http://astronomy.swin.edu.au/~pbourke/modelling/triangulate/

If not already done I would start by the more straightforward algo and would
switch to a more elvoved one if really needed (for example you could quickly
test the difference in x and y to quickly reject points and you have to
compute the exact distance only for those who could match).

Good luck.

 

[Guest]

Given is a dynamic set S of (moving, vanishing and arising) points

(2D). It could be the case that |S|>100 or even >1000 but not >20000.
In general almost all of the current members of S are moving all the
time.

For a single point p of S I want to find

A) All other points which are in a given circle around p
B) The nearest neighbor of p

I think a voronoi partition of the plane with respect to S should be
the key to solve the problem.

I think not, because cell phone masts dont move, but your points do. I
would use square grids for this problem. Represent your set S as a
collection of collections. Let S be a collection keyed on the grid (eg by
the grid's center x,y). Within each of these collections are all of the
points that are currently contained in the grid. As a point moves from one
grid to another, you have to remove it from one collection and add it to
another. Don't make the grids too small or you will spend too much time
moving points from one grid to another.

To find all points at a given distance or less from point P, you can
calculate which grids need to be checked, and then use brute force code to
check all points in the relevant grids. Don't make the grids too big or you
will gain no search advantage (ie you will check many more points than you
really need to).

 

[Guest]

Not sure if I understand your problem exactly but given a point "p", you
might consider:

Keep a grid and every time a point is entered, set it's grid number then for
the point, Calculate the distances beween p and all the other points in the
grid to find the ones which are within the circle radius distance and keeping
track of the minimum distance.

 

[GFM GToeroe]

Not sure if I understand your problem exactly but given a point "p", you
might consider:

Keep a grid and every time a point is entered, set it's grid number then for
the point, Calculate the distances beween p and all the other points in the
grid to find the ones which are within the circle radius distance and keeping
track of the minimum distance.

Yes, this is the street I'm currently going on. Because I figured out
another problem: The data is often clustered very high as the points
stand for example for swarms or objects which chase all the same prey.

So I will work with a list of lists defined by a dynamic grid which is
binded to a suited function of the max speed the objects can have. Also
I will research if lists which contain the objects sorted tby x,y,r,phi
could improve the algorithm.

Thanks to all

Gabor