## RE: [Algorithms] Re: Fast nearest neighbour queries

 RE: [Algorithms] Re: Fast nearest neighbour queries From: Jon Watte - 2005-04-22 01:18:20 ```> The "incremental" algorithm is also quite easy to code up and extends to > higher dimensions (drop a point in, blow away all of the cells whose > circumsphere contains the point, reconnect to the new point...) Yes, but which points actually connect, and which are culled away by the sides of the polytope of the new point's cell? If there's a way to calculate this that's better than actually calculating the polytope, I'm interested! Cheers, / h+ ```

 RE: [Algorithms] Re: Fast nearest neighbour queries From: Tony Cox - 2005-04-21 23:57:30 ```Don't you just want the Delaunay triangulation of the nodes, i.e. the dual of the Voronoi diagram? See "Computational Geometry in C" (O'Rourke) for good stuff on this, but essentially you can compute the Delaunay triangulation directly using a convex-hull algorithm, based on the observation that: The Delaunay triangulation of a set of points in two dimensions is precisely the projection onto the xy-plane of the lower convex hull of the transformed points in three dimensions, transformed by mapping upwards to the paraboloid z =3D x*x + y*y. This relationship holds for higher dimensions. So, basically you can compute the Delaunay triangulation as fast as you can compute convex hulls. - Tony -----Original Message----- From: gdalgorithms-list-admin@... [mailto:gdalgorithms-list-admin@...] On Behalf Of Jon Watte Sent: Thursday, April 21, 2005 4:32 PM To: gdalgorithms-list@... Subject: RE: [Algorithms] Re: Fast nearest neighbour queries > If you can spare the RAM, you could precompute > a connectivity graph and each node can store all of the closest nodes to it, > and then on the first frame you do a global search using whatever method, > then you start out only searching its neighbors. As long as you don't move That's actually exactly what a Voronoi diagram is, and the search algorithm I suggested using. The main difficulty is calculating which nodes are actually "nearest" each other. This typically involves building cell side polygons through plane clipping, and keeping track of what you clip out (as preprocess). Cheers, / h+ ------------------------------------------------------- SF email is sponsored by - The IT Product Guide Read honest & candid reviews on hundreds of IT Products from real users. Discover which products truly live up to the hype. Start reading now. http://ads.osdn.com/?ad_id=3D6595&alloc_id=3D14396&op=3Dclick _______________________________________________ GDAlgorithms-list mailing list GDAlgorithms-list@... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 ```
 RE: [Algorithms] Re: Fast nearest neighbour queries From: Peter-Pike Sloan - 2005-04-22 01:05:04 ```It's important to note that the edge flip algorithm (and the general formulation of constrained triangulations) don't extend to higher dimensions... The "incremental" algorithm is also quite easy to code up and extends to higher dimensions (drop a point in, blow away all of the cells whose circumsphere contains the point, reconnect to the new point...) -Peter-Pike Sloan=20 -----Original Message----- From: gdalgorithms-list-admin@... [mailto:gdalgorithms-list-admin@...] On Behalf Of Alex Mohr Sent: Thursday, April 21, 2005 5:15 PM To: gdalgorithms-list@... Subject: Re: [Algorithms] Re: Fast nearest neighbour queries This is off the thread topic, but I think the easiest algorithm to code is the edge flip algorithm (google: edge flip delaunay). I've done it before and it's quite straightforward and the performance is quite good. I believe it's worst case N^2, but I think it rarely requires this many edge flips. Another cool thing is that you can also very easily extend this to do "constrained" Delaunay triangulations. Alex >Don't you just want the Delaunay triangulation of the nodes, i.e. the=20 >dual of the Voronoi diagram? > >See "Computational Geometry in C" (O'Rourke) for good stuff on this,=20 >but essentially you can compute the Delaunay triangulation directly=20 >using a convex-hull algorithm, based on the observation that: > >The Delaunay triangulation of a set of points in two dimensions is=20 >precisely the projection onto the xy-plane of the lower convex hull of=20 >the transformed points in three dimensions, transformed by mapping=20 >upwards to the paraboloid z =3D x*x + y*y. > >This relationship holds for higher dimensions. So, basically you can=20 >compute the Delaunay triangulation as fast as you can compute convex=20 >hulls. > >- Tony > >-----Original Message----- >From: gdalgorithms-list-admin@... >[mailto:gdalgorithms-list-admin@...] On Behalf Of Jon >Watte >Sent: Thursday, April 21, 2005 4:32 PM >To: gdalgorithms-list@... >Subject: RE: [Algorithms] Re: Fast nearest neighbour queries > > >> If you can spare the RAM, you could precompute a connectivity graph=20 >> and each node can store all of the closest nodes >to >it, >> and then on the first frame you do a global search using whatever >method, >> then you start out only searching its neighbors. As long as you=20 >> don't >move > >That's actually exactly what a Voronoi diagram is, and the search=20 >algorithm I suggested using. The main difficulty is calculating which=20 >nodes are actually "nearest" each other. This typically involves=20 >building cell side polygons through plane clipping, and keeping track=20 >of what you clip out (as preprocess). > >Cheers, > > / h+ > > > >------------------------------------------------------- >SF email is sponsored by - The IT Product Guide Read honest & candid=20 >reviews on hundreds of IT Products from real users. >Discover which products truly live up to the hype. Start reading now. >http://ads.osdn.com/?ad_id=3D6595&alloc_id=3D14396&op=3Dclick >_______________________________________________ >GDAlgorithms-list mailing list >GDAlgorithms-list@... >https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list >Archives: >http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 > > >------------------------------------------------------- >SF email is sponsored by - The IT Product Guide Read honest & candid=20 >reviews on hundreds of IT Products from real users. >Discover which products truly live up to the hype. Start reading now. >http://ads.osdn.com/?ad_ide95&alloc_id=14396&op=3Dclick >_______________________________________________ >GDAlgorithms-list mailing list >GDAlgorithms-list@... >https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list >Archives: >http://sourceforge.net/mailarchive/forum.php?forum_ida88 ------------------------------------------------------- SF email is sponsored by - The IT Product Guide Read honest & candid reviews on hundreds of IT Products from real users. Discover which products truly live up to the hype. Start reading now. http://ads.osdn.com/?ad_ide95&alloc_id=14396&op=3Dick _______________________________________________ GDAlgorithms-list mailing list GDAlgorithms-list@... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_ida88 ```
 RE: [Algorithms] Re: Fast nearest neighbour queries From: Jon Watte - 2005-04-22 01:18:20 ```> The "incremental" algorithm is also quite easy to code up and extends to > higher dimensions (drop a point in, blow away all of the cells whose > circumsphere contains the point, reconnect to the new point...) Yes, but which points actually connect, and which are culled away by the sides of the polytope of the new point's cell? If there's a way to calculate this that's better than actually calculating the polytope, I'm interested! Cheers, / h+ ```
 RE: [Algorithms] Re: Fast nearest neighbour queries From: Peter-Pike Sloan - 2005-04-22 18:30:30 ```I believe it's fairly easy if you keep the connectivity of your cells. You have the set of cells that are to be removed, any cell which is adjacent (and not on the list) should be connected to the new point - so you can kind of walk this boundary region (always a d-1 manifold) building cells as you do. I hope that makes sense... -Peter-Pike Sloan=20 -----Original Message----- From: gdalgorithms-list-admin@... [mailto:gdalgorithms-list-admin@...] On Behalf Of Jon Watte Sent: Thursday, April 21, 2005 6:19 PM To: gdalgorithms-list@... Subject: RE: [Algorithms] Re: Fast nearest neighbour queries > The "incremental" algorithm is also quite easy to code up and extends=20 > to higher dimensions (drop a point in, blow away all of the cells=20 > whose circumsphere contains the point, reconnect to the new point...) Yes, but which points actually connect, and which are culled away by the sides of the polytope of the new point's cell? If there's a way to calculate this that's better than actually calculating the polytope, I'm interested! Cheers, / h+ ------------------------------------------------------- SF email is sponsored by - The IT Product Guide Read honest & candid reviews on hundreds of IT Products from real users. Discover which products truly live up to the hype. Start reading now. http://ads.osdn.com/?ad_id=3D6595&alloc_id=3D14396&op=3Dclick _______________________________________________ GDAlgorithms-list mailing list GDAlgorithms-list@... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 ```
 RE: [Algorithms] Re: Fast nearest neighbour queries From: Jon Watte - 2005-04-22 20:38:05 ```Yes, it seems building the DT this way, and then flipping to the dual Voronoi representation for actual map querying might be the easiest route. Thanks! Cheers, / h+ -----Original Message----- From: gdalgorithms-list-admin@... [mailto:gdalgorithms-list-admin@...]On Behalf Of Peter-Pike Sloan Sent: Friday, April 22, 2005 11:30 AM To: gdalgorithms-list@... Subject: RE: [Algorithms] Re: Fast nearest neighbour queries I believe it's fairly easy if you keep the connectivity of your cells. You have the set of cells that are to be removed, any cell which is adjacent (and not on the list) should be connected to the new point - so you can kind of walk this boundary region (always a d-1 manifold) building cells as you do. I hope that makes sense... -Peter-Pike Sloan ```
 RE: [Algorithms] Re: Fast nearest neighbour queries From: Garett Bass - 2005-04-23 07:39:08 ```I suspect you might also want to convolute against the Horowitz conjunct to reduce the Norbitstein quotient. Regards, Garett p.s. apologies in advance for any artificially induced confusion. -----Original Message----- From: Jon Watte [mailto:hplus@...] Sent: Friday, April 22, 2005 3:39 PM To: gdalgorithms-list@... Subject: RE: [Algorithms] Re: Fast nearest neighbour queries Yes, it seems building the DT this way, and then flipping to the dual Voronoi representation for actual map querying might be the easiest route. Thanks! Cheers, / h+ -----Original Message----- From: gdalgorithms-list-admin@... [mailto:gdalgorithms-list-admin@...]On Behalf Of Peter-Pike Sloan Sent: Friday, April 22, 2005 11:30 AM To: gdalgorithms-list@... Subject: RE: [Algorithms] Re: Fast nearest neighbour queries I believe it's fairly easy if you keep the connectivity of your cells. You have the set of cells that are to be removed, any cell which is adjacent (and not on the list) should be connected to the new point - so you can kind of walk this boundary region (always a d-1 manifold) building cells as you do. I hope that makes sense... -Peter-Pike Sloan ------------------------------------------------------- SF email is sponsored by - The IT Product Guide Read honest & candid reviews on hundreds of IT Products from real users. Discover which products truly live up to the hype. Start reading now. http://ads.osdn.com/?ad_id=6595&alloc_id=14396&op=click _______________________________________________ GDAlgorithms-list mailing list GDAlgorithms-list@... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=6188 ```
 [Algorithms] test From: Daniel Renkel - 2005-05-24 18:36:05 ```i haven't received a mail since 4 days ... is this list that silent while e3 is going on? :-) ```
 Re: [Algorithms] Re: Fast nearest neighbour queries From: Alex Mohr - 2005-04-22 00:14:59 ```This is off the thread topic, but I think the easiest algorithm to code is the edge flip algorithm (google: edge flip delaunay). I've done it before and it's quite straightforward and the performance is quite good. I believe it's worst case N^2, but I think it rarely requires this many edge flips. Another cool thing is that you can also very easily extend this to do "constrained" Delaunay triangulations. Alex >Don't you just want the Delaunay triangulation of the nodes, i.e. the >dual of the Voronoi diagram? > >See "Computational Geometry in C" (O'Rourke) for good stuff on this, but >essentially you can compute the Delaunay triangulation directly using a >convex-hull algorithm, based on the observation that: > >The Delaunay triangulation of a set of points in two dimensions is >precisely the projection onto the xy-plane of the lower convex hull of >the transformed points in three dimensions, transformed by mapping >upwards to the paraboloid z =3D x*x + y*y. > >This relationship holds for higher dimensions. So, basically you can >compute the Delaunay triangulation as fast as you can compute convex >hulls. > >- Tony > >-----Original Message----- >From: gdalgorithms-list-admin@... >[mailto:gdalgorithms-list-admin@...] On Behalf Of Jon >Watte >Sent: Thursday, April 21, 2005 4:32 PM >To: gdalgorithms-list@... >Subject: RE: [Algorithms] Re: Fast nearest neighbour queries > > >> If you can spare the RAM, you could precompute >> a connectivity graph and each node can store all of the closest nodes >to >it, >> and then on the first frame you do a global search using whatever >method, >> then you start out only searching its neighbors. As long as you don't >move > >That's actually exactly what a Voronoi diagram is, and the search >algorithm I suggested using. The main difficulty is calculating >which nodes are actually "nearest" each other. This typically >involves building cell side polygons through plane clipping, and >keeping track of what you clip out (as preprocess). > >Cheers, > > / h+ > > > >------------------------------------------------------- >SF email is sponsored by - The IT Product Guide >Read honest & candid reviews on hundreds of IT Products from real users. >Discover which products truly live up to the hype. Start reading now. >http://ads.osdn.com/?ad_id=3D6595&alloc_id=3D14396&op=3Dclick >_______________________________________________ >GDAlgorithms-list mailing list >GDAlgorithms-list@... >https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list >Archives: >http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 > > >------------------------------------------------------- >SF email is sponsored by - The IT Product Guide >Read honest & candid reviews on hundreds of IT Products from real users. >Discover which products truly live up to the hype. Start reading now. >http://ads.osdn.com/?ad_ide95&alloc_id=14396&op=3Dclick >_______________________________________________ >GDAlgorithms-list mailing list >GDAlgorithms-list@... >https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list >Archives: >http://sourceforge.net/mailarchive/forum.php?forum_ida88 ```