Fwd: Barycentric subdivision of n-dimensional simplex using CGAL

5 messages
Open this post in threaded view
|
Report Content as Inappropriate

Fwd: Barycentric subdivision of n-dimensional simplex using CGAL

 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 ChandrasekaranDepartment of Computer ScienceUniversity of GeorgiaPhone: 7062472873Website: http://muthuchandrasekaran.com -- Muthukumaran ChandrasekaranDepartment of Computer ScienceUniversity of GeorgiaPhone: 7062472873Website: http://muthuchandrasekaran.com
Open this post in threaded view
|
Report Content as Inappropriate

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

 On Tue, 14 Feb 2017, Muthukumaran Chandrasekaran wrote: > 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. 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
Open this post in threaded view
|
Report Content as Inappropriate

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

 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 ChandrasekaranDepartment of Computer ScienceUniversity of GeorgiaPhone: 7062472873Website: http://muthuchandrasekaran.com
Open this post in threaded view
|
Report Content as Inappropriate

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

 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 triangulation3) Had to reimplement CGAL::barycenter() because it wasn't defined for Point_dHowever, 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 >}’ and ‘Point_d {aka CGAL::Wrap::Point_d >}’)"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? ThanksMuthu ChandrasekaranPhD Candidate, THINC Lab Department of Comp. ScienceUniversity of GeorgiaOn Wed, Feb 15, 2017 at 2:14 PM, Muthukumaran Chandrasekaran 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 ChandrasekaranDepartment of Computer ScienceUniversity of GeorgiaPhone: 7062472873Website: http://muthuchandrasekaran.com -- Muthukumaran ChandrasekaranDepartment of Computer ScienceUniversity of GeorgiaPhone: 7062472873Website: http://muthuchandrasekaran.com barycentric_subdivision_test.cpp (9K) Download Attachment