vb.net code for advanced data structures

13 Jun 2006 3:47 PM

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

13 Jun 2006 4:29 PM

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.

--
Patrice

"GFM GToeroe" <g**@gtoeroe.de> a écrit dans le message de news:

1150213656.980598.63***@g10g2000cwb.googlegroups.com...
Show quoteHide quote

> 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
>

13 Jun 2006 4:41 PM

AMercer

> 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).

14 Jun 2006 12:01 AM

Dennis

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.

--
Dennis in Houston

Show quoteHide quote

"GFM GToeroe" wrote:

> 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
>
>

14 Jun 2006 9:04 AM

GFM GToeroe

Dennis schrieb:

Show quoteHide quote

> 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.
>
> --
> Dennis in Houston
>
>
> "GFM GToeroe" wrote:
>
> > 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
> >
> >

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