unstructured grid

{{Short description|Unstructured (or irregular) grid is a tessellation of a part of the Euclidean plane}}

Image:Unstructured_grid.svg mesh]]

An unstructured grid or irregular grid is a tessellation of a part of the Euclidean plane or Euclidean space by simple shapes, such as triangles or tetrahedra, in an irregular pattern. Grids of this type may be used in finite element analysis when the input to be analyzed has an irregular shape.

Unlike structured grids, unstructured grids require a list of the connectivity which specifies the way a given set of vertices make up individual elements (see graph (data structure)).

Ruppert's algorithm is often used to convert an irregularly shaped polygon into an unstructured grid of triangles.

In addition to triangles and tetrahedra, other commonly used elements in finite element simulation include quadrilateral (4-noded) and hexahedral (8-noded) elements in 2D and 3D, respectively. One of the most commonly used algorithms to generate unstructured quadrilateral grid is "Paving".{{cite journal

| last1 = Blacker | first1 = Ted D.

| last2 = Stephenson | first2 = Michael B.

| date = September 1991

| doi = 10.1002/nme.1620320410

| issue = 4

| journal = International Journal for Numerical Methods in Engineering

| pages = 811–847

| title = Paving: A new approach to automated quadrilateral mesh generation

| volume = 32}} However, there is no such commonly used algorithm for generating unstructured hexahedral grid on a general 3D solid model. "Plastering" is a 3D version of Paving,{{cite conference

| last = Canann | first = Scott

| contribution = Plastering – A new approach to automated, 3-D hexahedral mesh generation

| date = April 1992

| doi = 10.2514/6.1992-2416

| publisher = American Institute of Aeronautics and Astronautics

| title = 33rd Structures, Structural Dynamics and Materials Conference}} but it has difficulty in forming hexahedral elements at the interior of a solid.