CGAL users discussion list

[Marc Glisse <>]

On Tue, 14 Feb 2017, Muthukumaran Chandrasekaran wrote:

> I am new to CGAL. I have installed CGAL 4.8.2
> <http://www.cgal.org/2016/09/19/cgal-482/> on the latest version of Ubuntu
>
> I would like some help with writing the following method
> *barycentric_subdivide*:
>
> The method should take in the *n+1* vertices (each vertex for me represents
> a probability distribution) that define the convex hull (boundary) of
> an *n*-dimensional
> simplex as input, partition that simplex using barycentric subdivision, and
> return *(n+1)!* sub-simplices (with the same dimensionality) as output.
>
> *Input*: *n+1* vertices that define the convex hull of an n-dimensional
> simplex. For eg:
>
> For 1D: {(0,1), (1,0)} for 1D,
>
> For 2D: {(0,0,1),(0,1,0),(1,0,0)}, and so on..
>
> *Output*: *(n+1)!* sub-simplices (i.e *(n+1)!* sets of vertices that define
> the convex hull of the (n+1)! sub-simplices). For eg:
>
> For 1D: {{(0,1),(0.5,0.5)} , {(0.5,0.5),(1,0)}},
>
> For 2D: {{(0,0,1),(1/3,1/3,1/3),(0,1/2,1/2)} ,
> {(0,1,0),(1/3,1/3,1/3),(0,1/2,1/2)}, {(0,0,1),(1/3,1/3,1/3),(1/2,0,1/2)} ,
> {(1,0,0),(1/3,1/3,1/3),(1/2,0,1/2)}, {(1,0,0),(1/3,1/3,1/3),(1/2,1/2,0)} ,
> {(0,1,0),(1/3,1/3,1/3),(1/2,1/2,0)}, and so on..
>
> I tried running http://doc.cgal.org/latest/Triangulation/#title11 but it
> doesn't provide what I want. Any help is greatly appreciated.

You could build a triangulation of your points, which has just one finite 
cell, then apply a variant of barycentric_subdivide from the example to it 
(the example works on the TDS, you would want to work on a full 
triangulation, with points with coordinates), and iterate on the resulting 
finite cells.

Otherwise, you'll have to implement it yourself, it isn't hard to do 
recursively: get the barycentric subdivision of each facet, and append the 
centroid to them.

--
Marc Glisse