From: Jon Watte <hplus@mi...>  20050422 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+ 
From: Tony Cox <tonycox@mi...>  20050421 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 convexhull algorithm, based on the observation that: The Delaunay triangulation of a set of points in two dimensions is precisely the projection onto the xyplane 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: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...] On Behalf Of Jon Watte Sent: Thursday, April 21, 2005 4:32 PM To: gdalgorithmslist@... 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 _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 
From: PeterPike Sloan <ppsloan@wi...>  20050422 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...) PeterPike Sloan=20 Original Message From: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...] On Behalf Of Alex Mohr Sent: Thursday, April 21, 2005 5:15 PM To: gdalgorithmslist@... 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 convexhull algorithm, based on the observation that: > >The Delaunay triangulation of a set of points in two dimensions is=20 >precisely the projection onto the xyplane 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: gdalgorithmslistadmin@... >[mailto:gdalgorithmslistadmin@...] On Behalf Of Jon >Watte >Sent: Thursday, April 21, 2005 4:32 PM >To: gdalgorithmslist@... >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 >_______________________________________________ >GDAlgorithmslist mailing list >GDAlgorithmslist@... >https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist >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 >_______________________________________________ >GDAlgorithmslist mailing list >GDAlgorithmslist@... >https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist >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 _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_ida88 
From: Jon Watte <hplus@mi...>  20050422 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+ 
From: PeterPike Sloan <ppsloan@wi...>  20050422 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 d1 manifold) building cells as you do. I hope that makes sense... PeterPike Sloan=20 Original Message From: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...] On Behalf Of Jon Watte Sent: Thursday, April 21, 2005 6:19 PM To: gdalgorithmslist@... 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 _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 
From: Jon Watte <hplus@mi...>  20050422 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: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...]On Behalf Of PeterPike Sloan Sent: Friday, April 22, 2005 11:30 AM To: gdalgorithmslist@... 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 d1 manifold) building cells as you do. I hope that makes sense... PeterPike Sloan 
From: Garett Bass <gtbass@st...>  20050423 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: gdalgorithmslist@... 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: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...]On Behalf Of PeterPike Sloan Sent: Friday, April 22, 2005 11:30 AM To: gdalgorithmslist@... 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 d1 manifold) building cells as you do. I hope that makes sense... PeterPike 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 _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=6188 
From: Daniel Renkel <renkel@ce...>  20050524 18:36:05

i haven't received a mail since 4 days ... is this list that silent while e3 is going on? :) 
From: Alex Mohr <amohr@cs...>  20050422 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 >convexhull algorithm, based on the observation that: > >The Delaunay triangulation of a set of points in two dimensions is >precisely the projection onto the xyplane 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: gdalgorithmslistadmin@... >[mailto:gdalgorithmslistadmin@...] On Behalf Of Jon >Watte >Sent: Thursday, April 21, 2005 4:32 PM >To: gdalgorithmslist@... >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 >_______________________________________________ >GDAlgorithmslist mailing list >GDAlgorithmslist@... >https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist >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 >_______________________________________________ >GDAlgorithmslist mailing list >GDAlgorithmslist@... >https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist >Archives: >http://sourceforge.net/mailarchive/forum.php?forum_ida88 