Convex Hull

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

Convex Hull

Rafael Roberto
Hi everyone,

I have some points from a cube. They are very well distributed so that every face have 100 points. But, when I call CGAL::convex_hull some points are connected to the others. Some faces have only two triangle, others have 5 or 6, but it never generate a convex hull with all the points triangulated (attached we have one of its faces projected).

Does anybody know if there is any way to use this CGAL function and all points be triangulated?


Thank you all,
Rafael Roberto
[hidden email]

hull.JPG (34K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Convex Hull

Stefan Schirra
Hi,

Rafael Roberto wrote:

> I have some points from a cube. They are very well distributed so that
> every face have 100 points. But, when I call CGAL::convex_hull some
> points are connected to the others. Some faces have only two triangle,
> others have 5 or 6, but it never generate a convex hull with all the
> points triangulated (attached we have one of its faces projected).

I guess, you use a incremental CGAL algorithm that processes the points
one by one. Whenever a point to be processed is outside of the current
hull, it is a new vertex and hence connected to the vertices of the
ridges of the visible part of the current hull, in your terminology, "it
is triangulated"; If the point is inside or on the boundary of the
current hull, nothing happens.

> Does anybody know if there is any way to use this CGAL function and all
> points be triangulated?

Well, you need to process the points in such a way that points are
always outside the present hull, for example, row by row per face. This
works, unless the CGAL algorithm permutes the points internally in order
to guarantee good expected worst case behavior. I don't know whether a
random permutation is applied, I guess not.

best regards

        Stefan



--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss
Reply | Threaded
Open this post in threaded view
|

Re: Convex Hull

andreas.fabri
Stefan Schirra wrote:

> Hi,
>
> Rafael Roberto wrote:
>
>> I have some points from a cube. They are very well distributed so that
>> every face have 100 points. But, when I call CGAL::convex_hull some
>> points are connected to the others. Some faces have only two triangle,
>> others have 5 or 6, but it never generate a convex hull with all the
>> points triangulated (attached we have one of its faces projected).
>
> I guess, you use a incremental CGAL algorithm that processes the points
> one by one. Whenever a point to be processed is outside of the current
> hull, it is a new vertex and hence connected to the vertices of the
> ridges of the visible part of the current hull, in your terminology, "it
> is triangulated"; If the point is inside or on the boundary of the
> current hull, nothing happens.
>
>> Does anybody know if there is any way to use this CGAL function and
>> all points be triangulated?
>
> Well, you need to process the points in such a way that points are
> always outside the present hull, for example, row by row per face. This
> works, unless the CGAL algorithm permutes the points internally in order
> to guarantee good expected worst case behavior. I don't know whether a
> random permutation is applied, I guess not.
>
> best regards
>
>     Stefan
>
>
>


Hi Rafael,

An alternative might be to use the 3D Delaunay triangulation.  The faces
opposite to the infinite vertex are the triangles on the convex hull.
We had users who found it a drawback that points on the interior of convex hull faces
don't get removed. For you this would be the desired feature. It remains to
convert this to a Polyhedron though.

andreas

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss