[vtkusers] Why is vtkDelaunay2D so slow in VC++ 2005

[Godofredo]

Hi santana, I've run some timing test on VC ++ 2005. You can compare them
with the ones you posted (by the way, nice job!!). As you can see, I'm
working in the "linear" region because of the slowness of the algorithm and
also because that will be the size range my input data will have. I cannot
post a graph like yours but I post here the values so you can get an idea:

Number of points             vtkDelaunay2d time (seconds)

402290                                        103
364985                                          95
339443                                          84
300141                                          74                       
273696                                          68
255287                                          62
232500                                          55
210868                                          49
194717                                          46
180700                                          41
163726                                          37
148096                                          33
125223                                          25
76458                                            15

If I understand your plot, it takes your program about 13 seconds to
triangulate 512^2 = 262144 points. As you can see, it takes mine about 65
seconds to complete the same task. This has been done in debug mode but, as
I've said in a previous post, I don't appreciate much difference between
release and debug modes. 


santana wrote:
> 
> 
> 
> 
> 
> Hi, Godofredo, I ran some timing tests on vtkdelaunay2D this morning
> after your post and found that vtkDelaunay2D performance is actually
> O(n^2) when compiled for debug. See
> http://quaoar.sr.unh.edu/vtkDelaunay2D/  for the details. I am running a
> linux box with the latest stable VTK. These results should give a
> reference point to compare your VC++ build against. 
> burlen 
> 
> Godofredo wrote:
> 
>   Hi, I haven't tried it yet under another platform. Sure it's slow by
> itself
> but I don't think that it should be that slow. Take a look at this
> unanswered post (quite old) regarding to VC7 vs VC6 and vtkDelaunay2D:
> 
> http://public.kitware.com/pipermail/vtkusers/2002-December/064429.html 
> 
> As soon I've time, I'll try under another platform to evaluate the
> algorithm
> performance. Meanwhile any comment is wellcomed. Thanks to all.
> 
> 
> santana wrote:
>   
>   
>     Hi, Delaunay is slow algorithm in general, it has to work point by
> point 
> and make a search through the point set with each insertion. I am not 
> sure about VTK but I have seen the time complexity of other 
> implementations is O(n*log(n)). It sounds like you by hand approach is 
> O(n) so would be much faster. You mentioned that you think it is related 
> to VC++ 2005 but I think it is the delaunay algorithm itself rather than 
> the platform which is the problem. have you tried under another platform?
> Burlen
> 
> 
> Godofredo wrote:
>     
>     
>       Hi to all, I've been doing some triangulations with big datasets and
> found
> out that vtkDelaunay2D is extremely slow in VC++ 2005. I've done the
> triangulation by hand (as my data came from a range scanner I just join
> the 
> verts in order) and It takes only seconds to triangulate what with
> vtkDelaunay2D takes almost 2 minutes. I've found in the forums a post
> that
> talked about the same problem but had no replys. Anyone could put some
> light
> into this? Many thanks.
>   
>       
>     
>     _______________________________________________
> This is the private VTK discussion list. 
> Please keep messages on-topic. Check the FAQ at:
> http://www.vtk.org/Wiki/VTK_FAQ 
> Follow this link to subscribe/unsubscribe:
> http://www.vtk.org/mailman/listinfo/vtkusers 
> 
> 
> -----
> http://quaoar.sr.unh.edu  
> 
>     
>   
>   
>   
> 
> 
> 
> 
> 
> _______________________________________________
> This is the private VTK discussion list. 
> Please keep messages on-topic. Check the FAQ at:
> http://www.vtk.org/Wiki/VTK_FAQ
> Follow this link to subscribe/unsubscribe:
> http://www.vtk.org/mailman/listinfo/vtkusers
> 
> 
> -----
> http://quaoar.sr.unh.edu 
> 

-- 
View this message in context: http://www.nabble.com/Why-is-vtkDelaunay2D-so-slow-in-VC%2B%2B-2005-tp14576119p14594685.html
Sent from the VTK - Users mailing list archive at Nabble.com.