Hi David,<div><br></div><div>You're right, vtkDelaunay3D is not the correct approach in this case. Now I'm trying to obtain a 2D convex hull (vtkDelaunay2D) by projecting the 3-D points onto a plane. Here's the code:</div>
<div><div><br></div><div>// create a plane, seting its origin in (0,0,0) and its normal N (N is the normal to the current vertex, the center of the neighborhood)</div><div>vtkSmartPointer<vtkPlane> plane = vtkSmartPointer<vtkPlane>::New();</div>
<div>plane->SetOrigin(0.0, 0.0, 0.0);</div><div>plane->SetNormal(N[0], N[1], N[2]);</div><div><br></div><div> // project each point in the neighborhood onto the plane</div><div>vtkSmartPointer<vtkPoints> ptsProj = vtkSmartPointer<vtkPoints>::New();</div>
<div>double origin[3] = {0.0, 0.0, 0.0};</div><div>double normal[3] = {N[0], N[1], N[2]};</div><div>double projected[3];</div><div>for ( int i = 0; i < pts->GetNumberOfPoints(); i++ ) {</div><div> <span class="Apple-tab-span" style="white-space:pre"> </span>pts->GetPoint(i,p);</div>
<div> <span class="Apple-tab-span" style="white-space:pre"> </span>plane->ProjectPoint( p, origin, normal, projected );</div><div> <span class="Apple-tab-span" style="white-space:pre"> </span>ptsProj->InsertNextPoint(projected);}</div>
<div><br></div><div>// store projected points in a polydata</div><div>vtkSmartPointer<vtkPolyData> ptsForTriang = vtkSmartPointer<vtkPolyData>::New();</div><div>ptsForTriang->SetPoints(ptsProj);</div><div><br>
</div><div>// apply delaunay2D</div><div>vtkSmartPointer<vtkDelaunay2D> delaunay2D = vtkSmartPointer<vtkDelaunay2D>::New();</div><div>delaunay2D->SetInput(ptsForTriang);</div><div>delaunay2D->Update();</div>
<div><br></div><div>When using this approach to my initial problem I get this:</div><div><a href="http://tinypic.com/r/2mre8ma/7">http://tinypic.com/r/2mre8ma/7</a></div><div><br></div><div>again, some vertices were not included in the convex hull . When I check the 2D convex hull info it says that has 6 points (which is correct) but only 2 cells (the ones that can be seen in the image)...</div>
<div><br></div><div>Is this the correct approach for computing the 2D convex hull (using projections)? Am I missing something?</div><div>Thanks again,</div><div>Miguel</div><br><div class="gmail_quote">2011/7/26 David Gobbi <span dir="ltr"><<a href="mailto:david.gobbi@gmail.com">david.gobbi@gmail.com</a>></span><br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">Hi Miguel,<br>
<br>
By applying vtkDelaunay3D to a flat (or nearly-flat) mesh, you are<br>
asking it to create degenerate tetrahedrons, so it should not be<br>
surprising that it fails on one or more of the points.<br>
<br>
Checking to see if a neighbor is within a 2D convex hull should be<br>
easy, you can use vtkPolygon::PointInPolygon() or, since the hull is<br>
convex, you can do a quick orientation check with the closest edge<br>
of the polygon.<br>
<div><div></div><div class="h5"><br>
- David<br>
<br>
<br>
2011/7/25 Miguel Sotaquirá <<a href="mailto:msotaquira@gmail.com">msotaquira@gmail.com</a>>:<br>
> Hi David,<br>
><br>
> Yes indeed, it is a triangle mesh... However as I mentioned vtkDelaunay3D<br>
> seems to work on all of the other vertices of my mesh, except on the one<br>
> included the previous e-mail... This seems so odd!<br>
><br>
> The problem is that I need the 3-D convex hull, since I later want to know<br>
> if current vertex is enclosed by its neighbors' convex hull... If I use<br>
> delaunay2D (by projecting my mesh onto a flat surface) would still be<br>
> possible to check if the point is contained in this convex hull.<br>
><br>
> Thanks,<br>
><br>
> Miguel<br>
><br>
> 2011/7/26 David Gobbi <<a href="mailto:david.gobbi@gmail.com">david.gobbi@gmail.com</a>><br>
>><br>
>> Hi Miguel,<br>
>><br>
>> The vtkDelaunay3D filter is for tetrahedral meshes, but your mesh<br>
>> looks like a triangle mesh. So my guess is that you should be using<br>
>> vtkDelaunay2D instead. But since Delanay2D is a 2D filter, you might<br>
>> have to project your mesh onto a flat surface first.<br>
>><br>
>> Also, Delaunay often performs worse on noiseless data. If you are<br>
>> working with synthetic data, you will get better results if you<br>
>> perturb each point with a small, random displacement. With noiseless<br>
>> data, it is often the case that three points will lie along a straight<br>
>> line, and the Delaunay algorithm will consider three such points as<br>
>> forming a degenerate triangle. Another problem with noiseless data,<br>
>> specifically for rectangular grids, is that they can result in<br>
>> situations where there is more than one valid Delaunay triangulation.<br>
>> These will cause the algorithm to go into deep recursion.<br>
>><br>
>> - David<br>
>><br>
>><br>
>> 2011/7/25 Miguel Sotaquirá <<a href="mailto:msotaquira@gmail.com">msotaquira@gmail.com</a>>:<br>
>> > Hi,<br>
>> > I'm using vtkDelaunay3D to create the local (1-ring neighborhood) convex<br>
>> > hull for each point in a mesh. For now I'm using a synthetic, perfectly<br>
>> > regular, noiseless mesh, where each vertex has exactly 6 neighbors.<br>
>> > I'm having troubles creating this convex hull only on one of the<br>
>> > vertices<br>
>> > (the others are computed correctly). In this particular case the convex<br>
>> > hull<br>
>> > computed does NOT include one of the six neighbors, as seen on the image<br>
>> > below:<br>
>> > <a href="http://tinypic.com/r/2944hag/7" target="_blank">http://tinypic.com/r/2944hag/7</a><br>
>> > the purple point being the center of the neighborhood, the gray spheres<br>
>> > its<br>
>> > neighbors and the gray lines the convex hull obtained from<br>
>> > vtkDelaunay3D.<br>
>> > Here's the code I'm using (neighbors are introduced as a polydata named<br>
>> > "pointcloud"):<br>
>> > vtkSmartPointer<vtkDelaunay3D> delaunay3D =<br>
>> > vtkSmartPointer<vtkDelaunay3D>::New();<br>
>> > delaunay3D->SetInput(pointCloud);<br>
>> > delaunay3D->Update();<br>
>> > during execution I get this warning: "vtkDelaunay3D (0x10345a490): 1<br>
>> > degenerate triangles encountered, mesh quality suspect"<br>
>> > How come, since I'm using a synthetic and perfectly regular mesh? As I<br>
>> > mentioned before, for other points (which have the exact same<br>
>> > characteristics) the convex hull is computed correctly.... Also, I've<br>
>> > tried<br>
>> > using the methods "SetTolerance" and "BoundingTriangulationOn" of<br>
>> > vtkDelaunay3D but with no success<br>
>> > Thanks!<br>
>> > Miguel<br>
</div></div></blockquote></div><br></div>