# developing the delaunayTriangulation class for Octave

29 messages
12
Open this post in threaded view
|

## developing the delaunayTriangulation class for Octave

 I am very interested in writing delaunayTriangulation class for Octave. I have already wrote functions that create a list of neighbors for all triangles from delaunayn(), functions which sort the neighbors list in different ways, computes the surface vectors for all triangles, including surface area and direction, volume of the triangles, and wrote functions that plot the mesh with special numerical labeling for debugging purposes. These functions work in any dimension. The next step is to package all of these functions into a class for Octave users, which I need help in finding documentation in learning how to do this. I am a physics student with good math skills, moderate documenting skills and moderate programming skills. I created these functions from my knowledge of math without looking up the source code for Matlab.  I like Octave's "T = delaunay( p )" for constructing triangular meshes from a given set of points "p," but I am confused on how to call all neighbors for a specified triangle list "T." The example Octave code below uses a crude function I wrote that computes all neighbors in a O(n^2) number of steps. ``````octave:15> [(1:size(T,1))' T neighbors ] ans = 1 3 2 1 0 4 2 2 5 3 2 1 3 5 3 5 4 2 0 2 6 4 7 3 1 1 0 5 5 5 7 3 4 2 7 6 6 5 4 3 8 7 7 6 5 7 5 9 6 8 6 4 8 0 9 6 9 6 7 8 0 8 7 `````` The first column contains the numerically ordered triangles. The second through fourth columns are the numerically labeled points contained by the triangles computed from T = delaunay(p). The fifth through seventh columns are the numerically labeled triangles who are neighbors to the specified ordered triangles.
Open this post in threaded view
|

## Re: developing the delaunayTriangulation class for Octave

 On 10 Feb 2014, at 17:38, Linux User <[hidden email]> wrote: > I am very interested in writing delaunayTriangulation class for Octave. I have already wrote functions that create a list of neighbors for all triangles from delaunayn(), functions which sort the neighbors list in different ways, computes the surface vectors for all triangles, including surface area and direction, volume of the triangles, and wrote functions that plot the mesh with special numerical labeling for debugging purposes. These functions work in any dimension. Have you looked at the msh*m_geometric_properties and msh*m_topological_properties in teh package msh? They essentially implement the same functions you mention. > The next step is to package all of these functions into a class for Octave users, which I need help in finding documentation in learning how to do this. To do this in a Matlab compatible way you should be working with the bleading edge development version of Octave, wich implements classdef style OOP in the Octave interpreted language. So as a first step you should try to build the default branch of Octave sources. c.
Open this post in threaded view
|

## Re: developing the delaunayTriangulation class for Octave

 Please don't top-post, i.e. add your replies below the previous message, not above, and keep the list in CC as others could want to take part in the conversation. On 10 Feb 2014, at 19:52, Linux User <[hidden email]> wrote: > Thanks for showing me the msh package. I will look into it to understand it before trying to invent the same wheel all over again. > But, if you feel I may have something useful, then let me know and I will get to work on it. It would be a very useful contribution if you could try to make the implementation Matlab compatible, implementing the triangulation [1] and delaunayTriangulation [2] classes. You said you are a student, you could consider proposing this as a GSoC project [3,4]? > I was surprised to see that Octave did not have the delaunayTriangulation class that Matlab uses, but it looks Octave use something complete different that what I had anticipated. The main reason for that is probably that those classes require classdef, and classdef implementation is not yet complete in Octave. > Thanks. c. [1] http://www.mathworks.it/it/help/matlab/ref/triangulationclass.html[2] http://www.mathworks.it/it/help/matlab/ref/delaunaytriangulationclass.html[3] http://wiki.octave.org/GSoC_Project_Ideas[4] http://www.google-melange.com/gsoc/homepage/google/gsoc2014
Open this post in threaded view
|

## Re: developing the delaunayTriangulation class for Octave

Open this post in threaded view
|

## Re: developing the delaunayTriangulation class for Octave

 Let me know if I have implemented the correct email writing style. > >You said you are a student, you could consider proposing this as a GSoC project [3,4]? I have created a GSOC profile account and I would be very interested in submitting a proposed project application for triangulation [1] and delaunayTriangulation [2]. The deadline for the Mentoring organization application is 14 February 19:00 UTC. I do not have a mentor, and I am not sure if there is enough time to get everything ready to submit on time. Would you like to act as a mentor or recommend someone else. My username for https://www.google-melange.com/gsoc/homepage/google/gsoc2014is "linuxfreebird" . By the way... >>[3,4] what does that mean? Thanks.
Open this post in threaded view
|

## Re: developing the delaunayTriangulation class for Octave

Open this post in threaded view
|

## Re: developing the delaunayTriangulation class for Octave

 In reply to this post by Linux User About the 2D Delaunay triangulation generation, there exist the Triangle library (http://www.cs.cmu.edu/~quake/triangle.html), which is by far the fastest implementation available. It permits also the generation of constrained triangulation (qhull has not such possibility AFAIK) and returns the list of vertices for each triangle, as qhull does. The problem is that Triangle is not free software. The last version was released on 2005. I have written a couple of times to the author asking about the possibility to release Triangle as free software, but I have not obtained any answer. Maybe some of the Octave core developers could ask again about such possibility in order to use Triangle in GNU Octave -- ***************************************** José Luis García Pallero [hidden email] (o< / / \ V_/_ Use Debian GNU/Linux and enjoy! *****************************************
Open this post in threaded view
|

## Re: developing the delaunayTriangulation class for Octave

 On 11/02/2014 11:45, José Luis García Pallero wrote: > About the 2D Delaunay triangulation generation, there exist the > Triangle library (http://www.cs.cmu.edu/~quake/triangle.html), which > is by far the fastest implementation available. It permits also the > generation of constrained triangulation (qhull has not such > possibility AFAIK) and returns the list of vertices for each triangle, > as qhull does. The problem is that Triangle is not free software. The > last version was released on 2005. I have written a couple of times to > the author asking about the possibility to release Triangle as free > software, but I have not obtained any answer. Maybe some of the Octave > core developers could ask again about such possibility in order to use > Triangle in GNU Octave > I have also contacted the author about Triangle to ask a technical question, but he did not respond, I wouldn't be too hopeful. I would actually suggest making the GPL gmsh (http://geuz.org/gmsh/) available through the (largely undocumented) C++ API which they now provide. I think the msh package is based on gmsh, but this would be a more direct approach. Yet another dependency though. There is a python gmsh interface that uses this. Richard -- The University of Edinburgh is a charitable body, registered in Scotland, with registration number SC005336.
Open this post in threaded view
|

## Re: developing the delaunayTriangulation class for Octave

 2014-02-11 12:58 GMT+01:00 Richard <[hidden email]>: > On 11/02/2014 11:45, José Luis García Pallero wrote: >> >> About the 2D Delaunay triangulation generation, there exist the >> Triangle library (http://www.cs.cmu.edu/~quake/triangle.html), which >> is by far the fastest implementation available. It permits also the >> generation of constrained triangulation (qhull has not such >> possibility AFAIK) and returns the list of vertices for each triangle, >> as qhull does. The problem is that Triangle is not free software. The >> last version was released on 2005. I have written a couple of times to >> the author asking about the possibility to release Triangle as free >> software, but I have not obtained any answer. Maybe some of the Octave >> core developers could ask again about such possibility in order to use >> Triangle in GNU Octave >> > > I have also contacted the author about Triangle to ask a technical question, > but he did not respond, I wouldn't be too hopeful. I would actually suggest > making the GPL gmsh (http://geuz.org/gmsh/) available through the (largely > undocumented) C++ API which they now provide. I think the msh package is > based on gmsh, but this would be a more direct approach. Yet another > dependency though. There is a python gmsh interface that uses this. Mmmm, I've discovered this new mail: [hidden email] (http://www.cs.berkeley.edu/~jrs/61bs14/) It is not the same as the old you can see in the Triangle page. I'll try again to ask him > > Richard > > -- > The University of Edinburgh is a charitable body, registered in > Scotland, with registration number SC005336. > -- ***************************************** José Luis García Pallero [hidden email] (o< / / \ V_/_ Use Debian GNU/Linux and enjoy! *****************************************
Open this post in threaded view
|

## Re: developing the delaunayTriangulation class for Octave

Open this post in threaded view
|

## Re: developing the delaunayTriangulation class for Octave

 In reply to this post by Richard Crozier 2014-02-11 12:58 GMT+01:00 Richard <[hidden email]>: > On 11/02/2014 11:45, José Luis García Pallero wrote: >> >> About the 2D Delaunay triangulation generation, there exist the >> Triangle library (http://www.cs.cmu.edu/~quake/triangle.html), which >> is by far the fastest implementation available. It permits also the >> generation of constrained triangulation (qhull has not such >> possibility AFAIK) and returns the list of vertices for each triangle, >> as qhull does. The problem is that Triangle is not free software. The >> last version was released on 2005. I have written a couple of times to >> the author asking about the possibility to release Triangle as free >> software, but I have not obtained any answer. Maybe some of the Octave >> core developers could ask again about such possibility in order to use >> Triangle in GNU Octave >> > > I have also contacted the author about Triangle to ask a technical question, > but he did not respond, I wouldn't be too hopeful. I would actually suggest > making the GPL gmsh (http://geuz.org/gmsh/) available through the (largely > undocumented) C++ API which they now provide. I think the msh package is > based on gmsh, but this would be a more direct approach. Yet another > dependency though. There is a python gmsh interface that uses this. Another possibility is to use the GNU Triangulated Surface library (http://gts.sourceforge.net/). It permits also the generation of constrained meshes. As a  bad issue, it is in general terribly slow, and also is apparently discontinued since 2006 > > Richard > > -- > The University of Edinburgh is a charitable body, registered in > Scotland, with registration number SC005336. > -- ***************************************** José Luis García Pallero [hidden email] (o< / / \ V_/_ Use Debian GNU/Linux and enjoy! *****************************************
Open this post in threaded view
|

## Re: developing the delaunayTriangulation class for Octave

 In reply to this post by Richard Crozier On 11 Feb 2014, at 12:58, Richard <[hidden email]> wrote: > I have also contacted the author about Triangle to ask a technical question, but he did not respond, I wouldn't be too hopeful. I would actually suggest making the GPL gmsh (http://geuz.org/gmsh/) available through the (largely undocumented) C++ API which they now provide. > I think the msh package is based on gmsh, Yes it allows to import/export meshes generated from gmsh and to invoke gmsh on a geometrical model to generate the mesh. > but this would be a more direct approach. Yet another dependency though. thanks to the ability to import FEnics meshes and thanks to the good selection of format conversion tools provided by FEnics, msh can now handle directly or indirectly a good number of different mesh generator. Therefore, I think it only makes sense to do new work on triangular/tetrahedral meshes if we want to do so in a Matlab compatible way, which requires using classdef. c.
Open this post in threaded view
|

## Re: developing the delaunayTriangulation class for Octave

 In reply to this post by Linux User On 11 Feb 2014, at 14:00, Linux User <[hidden email]> wrote: > This current email says that octave.maintainers will be carbon copied. > I am not sure if this will allow them to see the email. You are top-posting again. c.
Open this post in threaded view
|

## Re: developing the delaunayTriangulation class for Octave

 In reply to this post by José Luis García Pallero On Feb 11, 2014, at 7:44 AM, José Luis García Pallero <[hidden email]> wrote:2014-02-11 12:58 GMT+01:00 Richard <[hidden email]>:On 11/02/2014 11:45, José Luis García Pallero wrote:About the 2D Delaunay triangulation generation, there exist theTriangle library (http://www.cs.cmu.edu/~quake/triangle.html), whichis by far the fastest implementation available. It permits also thegeneration of constrained triangulation (qhull has not suchpossibility AFAIK) and returns the list of vertices for each triangle,as qhull does. The problem is that Triangle is not free software. Thelast version was released on 2005. I have written a couple of times tothe author asking about the possibility to release Triangle as freesoftware, but I have not obtained any answer. Maybe some of the Octavecore developers could ask again about such possibility in order to useTriangle in GNU OctaveI have also contacted the author about Triangle to ask a technical question,but he did not respond, I wouldn't be too hopeful. I would actually suggestmaking the GPL gmsh (http://geuz.org/gmsh/) available through the (largelyundocumented) C++ API which they now provide. I think the msh package isbased on gmsh, but this would be a more direct approach. Yet anotherdependency though. There is a python gmsh interface that uses this.Another possibility is to use the GNU Triangulated Surface library(http://gts.sourceforge.net/). It permits also the generation ofconstrained meshes. As a  bad issue, it is in general terribly slow,and also is apparently discontinued since 2006Richard--The University of Edinburgh is a charitable body, registered inScotland, with registration number SC005336.-- *****************************************José Luis García Pallero[hidden email](o. qhull is still out there, and has been used by octave in the past. --Marius Schamschula
Open this post in threaded view
|

## Re: developing the delaunayTriangulation class for Octave

Open this post in threaded view
|

## Re: developing the delaunayTriangulation class for Octave

 In reply to this post by c.-2 >>To  c. >> Cc octave maintainers mailing list This current email says that octave.maintainers will be carbon copied. I am not sure if this will allow them to see the email. >>It would be a very useful contribution if you could try to make the implementation Matlab compatible, implementing the triangulation [1] and delaunayTriangulation [2] classes. The main reason for that is probably that those classes require classdef, and classdef implementation is not yet complete in Octave. After thinking about this coding issue for some time and going back to our previous discussions, I have finally concluded that I am no help to this project. It sounds like to me that the one and only reason why Octave developers have not implemented class like functionality such as [1] and [2] is because classdef does not exist, which means once Octave developers have classdef complete they will immediately just copy and paste their solutions for every missing class function from Matlab to Octave, rendering me obsolete. My skills as a programmer are better suited to solving math or phyiscs related problems, like creating the method functionality for [1] and [2], not so much on creating the architecture after the functionality is complete. This is another reason why I think I am obsolete. On Tue, Feb 11, 2014 at 8:53 AM, c. <[hidden email]> wrote: > > On 11 Feb 2014, at 14:00, Linux User <[hidden email]> wrote: > >> This current email says that octave.maintainers will be carbon copied. >> I am not sure if this will allow them to see the email. > > You are top-posting again. > > c.
Open this post in threaded view
|

## Re: developing the delaunayTriangulation class for Octave

 On Tue, Feb 11, 2014 at 4:39 PM, Linux User <[hidden email]> wrote: >>>To  c. >>> Cc octave maintainers mailing list > > This current email says that octave.maintainers will be carbon copied. > I am not sure if this will allow them to see the email. > >>>It would be a very useful contribution if you could try to make the implementation Matlab compatible, implementing the triangulation [1] and delaunayTriangulation [2] classes. The main reason for that is probably that those classes require classdef, and classdef > implementation is not yet complete in Octave. > > After thinking about this coding issue for some time and going back to > our previous discussions, I have finally concluded that I am no help > to this project. It sounds like to me that the one and only reason why > Octave developers have not implemented class like functionality such > as [1] and [2] is because classdef does not exist, which means once > Octave developers have classdef complete they will immediately just > copy and paste their solutions for every missing class function from > Matlab to Octave, rendering me obsolete. > > My skills as a programmer are better suited to solving math or phyiscs > related problems, like creating the method functionality for [1] and > [2], not so much on creating the architecture after the functionality > is complete. This is another reason why I think I am obsolete. > > On Tue, Feb 11, 2014 at 8:53 AM, c. <[hidden email]> wrote: >> >> On 11 Feb 2014, at 14:00, Linux User <[hidden email]> wrote: >> >>> This current email says that octave.maintainers will be carbon copied. >>> I am not sure if this will allow them to see the email. >> >> You are top-posting again. >> >> c. Hi linuxfreebird, I followed your conversation and it seems to me that the msh project could benefit with contributions from somebody with your expertise and interest. Would you like to re-define your contributions to make the msh package better? It would be awesome to have a meshing package fast, compatible and extendable. I think you are not "obsolete", not at all, I am sure we have needs for your skills. Do you have other ideas you could work on? @Carlo: How good are we for calculating Voronoi diagrams? http://www.gnu.org/software/octave/doc/interpreter/Voronoi-Diagrams.htmlIs there any extension we need here?
Open this post in threaded view
|

## Re: developing the delaunayTriangulation class for Octave

 In reply to this post by Linux User On 11 Feb 2014, at 16:39, Linux User <[hidden email]> wrote: > After thinking about this coding issue for some time and going back to > our previous discussions, I have finally concluded that I am no help > to this project. It sounds like to me that the one and only reason why > Octave developers have not implemented class like functionality such > as [1] and [2] is because classdef does not exist, classdef does exist in Octave and, although it is still under development, but I think now would be a good time to start testing it by attempting the implementation of a reasonably complex project based on it. > which means once > Octave developers have classdef complete they will immediately just > copy and paste their solutions for every missing class function from > Matlab to Octave, rendering me obsolete. I really wish it really were a matter of just cut and paste! I actually think a matlab compatible implementation of the delaunayTriangulation class would be a quite complex project. To make it more complete I would suggest adding the implementaion of the closely related scatteredInterpolant class: http://www.mathworks.it/it/help/matlab/ref/scatteredinterpolantclass.html> My skills as a programmer are better suited to solving math or phyiscs > related problems, like creating the method functionality for [1] and > [2], not so much on creating the architecture after the functionality > is complete. This is another reason why I think I am obsolete. Most projects proposed for Octave (exept maybe those related to the GUI) do require a good mathematical background, but to produce useful results you should have (or be willing to acquire) some non trivial software engineering / development / collaboration skills. c.
Open this post in threaded view
|

## Re: developing the delaunayTriangulation class for Octave

 In reply to this post by Juan Pablo Carbajal-2 On 11 Feb 2014, at 19:38, Juan Pablo Carbajal <[hidden email]> wrote: > Would you like to re-define your contributions to make the msh package > better? It would be awesome to have a meshing package fast, compatible > and extendable. One thing that would be useful to add is better mesh refinement (possibly non-isotropic) and mesh smoothing methods, and maybe a de-refinement method. I have a student working on a standalone octree mesh generator based on p4est interfacing that with Octave would also be an interestin project. geometry preserving mesh refinement i.e. mapping boundary nodes to a CAD model would be another great contribution. c.