<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<meta content="text/html;charset=ISO-8859-1" http-equiv="Content-Type">
</head>
<body bgcolor="#ffffff" text="#000000">
Hi Godofredo, <br>
I added your data into the plot, posted to same place
<a class="moz-txt-link-freetext" href="http://quaoar.sr.unh.edu/vtkDelaunay2D/">http://quaoar.sr.unh.edu/vtkDelaunay2D/</a><br>
I am not sure it is a fair comparison, since our hardware setup is
probably quite different, I am running a dual proc, dual core 2G
opteron each core has 1M of cache and each proc has 2G of ram. What is
your setup?<br>
Burlen<br>
<br>
<br>
<br>
Godofredo wrote:
<blockquote cite="mid:14594685.post@talk.nabble.com" type="cite">
<pre wrap="">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:
</pre>
<blockquote type="cite">
<pre wrap="">
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
<a class="moz-txt-link-freetext" href="http://quaoar.sr.unh.edu/vtkDelaunay2D/">http://quaoar.sr.unh.edu/vtkDelaunay2D/</a> 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:
<a class="moz-txt-link-freetext" href="http://public.kitware.com/pipermail/vtkusers/2002-December/064429.html">http://public.kitware.com/pipermail/vtkusers/2002-December/064429.html</a>
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:
<a class="moz-txt-link-freetext" href="http://www.vtk.org/Wiki/VTK_FAQ">http://www.vtk.org/Wiki/VTK_FAQ</a>
Follow this link to subscribe/unsubscribe:
<a class="moz-txt-link-freetext" href="http://www.vtk.org/mailman/listinfo/vtkusers">http://www.vtk.org/mailman/listinfo/vtkusers</a>
-----
<a class="moz-txt-link-freetext" href="http://quaoar.sr.unh.edu">http://quaoar.sr.unh.edu</a>
_______________________________________________
This is the private VTK discussion list.
Please keep messages on-topic. Check the FAQ at:
<a class="moz-txt-link-freetext" href="http://www.vtk.org/Wiki/VTK_FAQ">http://www.vtk.org/Wiki/VTK_FAQ</a>
Follow this link to subscribe/unsubscribe:
<a class="moz-txt-link-freetext" href="http://www.vtk.org/mailman/listinfo/vtkusers">http://www.vtk.org/mailman/listinfo/vtkusers</a>
-----
<a class="moz-txt-link-freetext" href="http://quaoar.sr.unh.edu">http://quaoar.sr.unh.edu</a>
</pre>
</blockquote>
<pre wrap=""><!---->
</pre>
</blockquote>
<br>
</body>
</html>