Quantcast

Fwd: Barycentric subdivision of n-dimensional simplex using CGAL

classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Fwd: Barycentric subdivision of n-dimensional simplex using CGAL

Muthukumaran Chandrasekaran

I am new to CGAL. I have installed CGAL 4.8.2 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.

Thanks!

--
Muthukumaran Chandrasekaran
Department of Computer Science
University of Georgia

Phone: <a href="tel:(706)%20247-2873" value="+17062472873" target="_blank">7062472873
Email: [hidden email]
          [hidden email]



--
Muthukumaran Chandrasekaran
Department of Computer Science
University of Georgia

Phone: 7062472873
Email: [hidden email]
          [hidden email]
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Fwd: Barycentric subdivision of n-dimensional simplex using CGAL

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

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


Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Fwd: Barycentric subdivision of n-dimensional simplex using CGAL

Muthukumaran Chandrasekaran
Dear Marc,

Thank you for getting back to me so quickly!

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.

Is there an example/demo/code of how I could build a full triangulation of points (which has 1 finite cell)?

I am trying to read up on all this as quickly as I can. Apparently there is a LOT that I don't know about geometry :P. Its getting a little overwhelming. Any direction would immensely help.

Sincerely,
Muthu


--
Muthukumaran Chandrasekaran
Department of Computer Science
University of Georgia

Phone: 7062472873
Email: [hidden email]
          [hidden email]
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Fwd: Barycentric subdivision of n-dimensional simplex using CGAL

Muthukumaran Chandrasekaran
Hi,

Please find my attempt at doing what Marc suggested. Code is attached.

1) I create a full triangulation of points with 1 finite cell.
2) Rewrote a variant of the barycentric_subdivide that now uses the full triangulation
3) Had to reimplement CGAL::barycenter() because it wasn't defined for Point_d

However, I am not sure if what I am doing is 100% correct.

I couldn't test this because I kept getting an error at compile time at line 48 (v = v + it - CGAL::ORIGIN;)

The error:
 "no match for ‘operator+’ (operand types are ‘Point_d {aka CGAL::Wrap::Point_d<CGAL::Epick_d<CGAL::Dynamic_dimension_tag> >}’ and ‘Point_d {aka CGAL::Wrap::Point_d<CGAL::Epick_d<CGAL::Dynamic_dimension_tag> >}’)"

Can someone please tell me why I am getting this error?

Also, can you please check the rest of the code to see if the implementation seems right?

Thanks

Muthu Chandrasekaran
PhD Candidate, THINC Lab
Department of Comp. Science
University of Georgia






On Wed, Feb 15, 2017 at 2:14 PM, Muthukumaran Chandrasekaran <[hidden email]> wrote:
Dear Marc,

Thank you for getting back to me so quickly!

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.

Is there an example/demo/code of how I could build a full triangulation of points (which has 1 finite cell)?

I am trying to read up on all this as quickly as I can. Apparently there is a LOT that I don't know about geometry :P. Its getting a little overwhelming. Any direction would immensely help.

Sincerely,
Muthu


--
Muthukumaran Chandrasekaran
Department of Computer Science
University of Georgia

Phone: <a href="tel:(706)%20247-2873" value="+17062472873" target="_blank">7062472873
Email: [hidden email]
          [hidden email]



--
Muthukumaran Chandrasekaran
Department of Computer Science
University of Georgia

Phone: 7062472873
Email: [hidden email]
          [hidden email]

barycentric_subdivision_test.cpp (9K) Download Attachment
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Barycentric subdivision of n-dimensional simplex using CGAL

Muthukumaran Chandrasekaran
Hi,

Please find my attempt at doing what Marc suggested. Code is attached.

1) I create a full triangulation of points with 1 finite cell.
2) Rewrote a variant of the barycentric_subdivide that now uses the full triangulation
3) Had to reimplement CGAL::barycenter() because it wasn't defined for Point_d

However, I am not sure if what I am doing is 100% correct.

I couldn't test this because I kept getting an error at compile time at line 48 (v = v + it - CGAL::ORIGIN;)

The error:
 "no match for ‘operator+’ (operand types are ‘Point_d {aka CGAL::Wrap::Point_d<CGAL::Epick_d<CGAL::Dynamic_dimension_tag> >}’ and ‘Point_d {aka CGAL::Wrap::Point_d<CGAL::Epick_d<CGAL::Dynamic_dimension_tag> >}’)"

Can someone please tell me why I am getting this error?

Also, can you please check the rest of the code to see if the implementation seems right?

Thanks

Muthu Chandrasekaran
PhD Candidate, THINC Lab
Department of Comp. Science
University of Georgia



On Wed, Feb 15, 2017 at 2:14 PM, Muthukumaran Chandrasekaran <[hidden email]> wrote:
Dear Marc,

Thank you for getting back to me so quickly!

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.

This is what I'm trying to do:

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.

Inputn+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



--
Muthukumaran Chandrasekaran
Department of Computer Science
University of Georgia

Phone: <a href="tel:(706)%20247-2873" value="+17062472873" target="_blank">7062472873
Email: [hidden email]
          [hidden email]


barycentric_subdivision_test.cpp (9K) Download Attachment
Loading...