Unstructured 2D Triangular Mesh Generation in Matlab
Intro
For most of the Numerical simulations Unstructured Mesh are very common. Especially for Finite Element methods triangular meshes they offer the best trade-off between flexibility and precision of calculus. Today I am going to write about unstructured Mesh generation in MATLAB.
MESH2D – Automatic Mesh Generation
MESH2D is a toolbox of 2D meshing routines that allows for the automatic generation of unstructured triangular meshes for general 2D geometry.
An iterative algorithm is used that attempts to optimise the mesh topology/vertex position to achieve high quality triangulations.
In addition to the fully automatic settings, MESH2D allows the user to specify sizing information, allowing for varying levels of mesh resolution within the domain.
MESH2D includes a large set of demos/benchmarks. Please see the following:
- meshdemo – runs a standard set of demos.
- mesh_collection – a collection of user contributed geometries.
- facedemo – examples of geometry with connected faces.
It has one disavantage, due to the use of the qhull.mex routine (delaunay triangulator), despite of the slower standard matlab delaunay, it is only windows compatible.
Matlab PDE toolbox
Another solution is to use (and buy) the matlab MATLAB PDE Toolbox.
The PDE toolbox is designed to solve two-dimensional linear partial differential equations by finite element methods, but it also offers some simple CAD and mesh generation feature. By typing on the MATLAB command window:
pdetool
You will access the drawing tools which are pretty simple. It is possible to draw simple geometric primitives and combine them with boolean operations. After finished the 2D geometry by pressing the mesh command, you will realize unstructered mesh generation that can be used to solve pdes, but also to export on the workspace.
Triangle.m
Triangle.m is a MATLAB graphical user interface for creating 2D models and generating finite element triangulation grids. Grid generation is accomplished by an external call to the C-code Triangle.c, written by Jonathan Shewchuk at UC Berkeley. The features included in the MATLAB interface were created with the intent to handle 2D geophysical modeling applications. However, the generality of the interface should allow for multidisciplinary usage.
DistMesh
DistMesh is a simple MATLAB code for generation of unstructured triangular and tetrahedral meshes. It was developed by Per-Olof Persson and Gilbert Strang in the Department of Mathematics at MIT.
More infos can be found at the DistMesh Home page.
Popularity: 1% [?]
Quick Delaunay Triangulation
Filed under: Algorithms, C, Computational Geometry, FEM, Geometry
Contents
QuickDel
It has always been a dream of mine to code a Delaunay triangulator. Last week I had 3 free days and I did it. I actually thought it was more complicated, as it often happens, when you are outside the problem it seems bigger than it really is.
In this post you will find a Delaunay triangulation algorithm. My idea is to start a project which purpose is to create a robust an efficient triangulation/meshing tool.
The first release will be Delaunay triangulation function QuickDelMex
Below a comparison with DelaunayTri from the computational geometry toolbox.
Number of points QuickDel Built-in Matlab speed-up
10 0.0002 s 0.0142 98.69% s
100 0.0002 s 0.0094 97.61% s
1000 0.0016 s 0.0099 84.13% s
10000 0.0149 s 0.0707 78.96% s
100000 0.1856 s 1.2044 84.59% s
1000000 2.5094 s 14.1102 82.22% s
t=QuickDelMex(p) (version 0.3)
returns the Delaunay triangulation of the 2D point set p;
INPUT:
- * p: double array of size 2xN. The list of unique points [x1 y1,x2 y2];
OUTPUT:
- * t: double array of size ntx3. It contains the triangles of the Delaunay triangulation. Each rows contains 3 indexes of the points forming the triangle. Indexes are sorted counterclockwise; first points is flagged as one.
NOTES:
- * -This function is a prototype so don’t trust too much, please check the results and in case send bug report.
- * -This function is optimized for uniform random dataset, sparse datasets may slow down the algorithm.
- * -This function may not return the whole convex hull. Thin boundary triangles may be discarded.
- *- v0.3 is alittle slower but much more robust than v0.2.
Author: Luigi Giaccari (giaccariluigi@msn.com)
see also DelaunayTri delaunay delaunayn
Downloads
Matlab
You can download MEX Files of QuickDel here (win32 and linux):
A test to evaluate performances is also available on Matlab file exchange (Download Now)
C++
A Win32 executable is available here (v0.2):
it asks for the number of points to be triangulated. Once the triangulation has been done it prints a text file (a matlab m-file) which allows to visualize the triangulations inside Matlab.
I can also build a win32 .dll, but I was too lazy to do it, if you want it please contact me.
Acknowledgements
- This function uses the robust predicates from Jonathan Richard Shewchuk
Contacts
Please send bug reports/suggestions at: giaccariluigi@msn.com
This utility can be greatly enlarged, please compile the following survey.
Popularity: 2% [?]
Geometric Primitives and Geomtric Operations with Matlab
Matlab does not come by default with a geometric primitives library. About for some simple function like the “sphere” command, using some geometric entities may be an issue. Fortunately on Matlab file exchange are available these two packages, from David Legland ,that help us to develop geometric projects.
- Geom2D Download Now
- Geom3D Download Now
The packages include functions for computations on planar and spatial geometrical shapes (points, lines, circles, polygons…)
The goal is to provide a low-level library for manipulating geometrical primitives, making easier the development of more complex geometric algorithms.
The library proposes functions to:
- create various shapes (points, circles, lines, ellipses, polylines, polygons) using an intuitive syntax. Ex: createCircle(p1, p2, p3) to create a circle through 3 points.
- derive new shapes: intersection between 2 lines, between a line and a circle, parallel and perpendicular lines
Functions to compute intersections - work on polylines and polygons: compute centroid and area, expand, clip with half-plane…
- measure distances (between points, a point and a line, a point and a group of points), angle (of a line, between 3 points), or test geometry (point on a line, on a circle).
- manipulate planar transformation. Ex: P2 = transformPoint(P1, createRotation(CENTER, THETA));
- draw shapes easily. Ex: drawCircle([50 50], 25), drawLine([X0 Y0 DX DY]). Some clipping is performed for infinite shapes such as lines or rays.
- functions for 3D polygons and polyhedra. Polyhedra use classical vertex-faces arrays (face array contain indices of vertices), and support faces with any number of vertices. Some basic models are provided (createOctaedron, createCubeoctaedron…), as well as some computation (like faceNormal or centroid)
- direct drawing of shapes with specialized functions. Clipping is performed automatically for unbounded shapes such as lines or rays. Ex:
drawPoint3d([50 50 25; 20 70 10], ‘ro’); % draw some points
drawLine3d([X0 Y0 Z0 DX DY DZ]); % clip and draw straight line
Popularity: 1% [?]
Translator
Follow Us
Video Posts
