test_triangulation

test_triangulation, an Octave code which sets up a number of triangulation test problems.

As far as possible, a uniform and abstract approach has been used. For each test region, a number of routines are provided, via which it is possible for the user to determine many things about the region. Often, just one or two routines would be needed for a particular purpose. The names of the routines, and their purposes are:

• BOUNDARY_NEAREST: returns the nearest point on the boundary of the region to a given point or set of points;
• BOUNDARY_PROJECT: replaces an exterior point by the nearest point on the boundary;
• BOUNDARY_SEGMENT: returns a sequence of roughly equally spaced points that lie on one particular boundary segment;
• BOUNDARY_SEGMENT_LENGTH: returns the "length" (number of nodes) of a particular boundary segment. This simply counts the number of points needed to trace or approximate the boundary segment;
• BOUNDARY_SEGMENT_NUM: returns the number of boundary segments. Simple regions have one boundary segment. A region with one hole has two, and so on;
• BOX: returns a bounding box for the region. All points in the region are within this box;
• DENSITY: the value of the mesh density function at any point in the region. If this is not constant, then high values correspond to places where many more mesh points should be placed;
• ELEMENT_SIZE: returns a requested typical element size. This refers to the average size of the triangles formed by a triangulation of the points;
• FIXED_NUM: returns the number of points which must be included as nodes of the mesh (which may be zero);
• FIXED_POINTS: returns the coordinates of the points which must be included as nodes of the mesh;
• HEADER: prints a brief description of the problem;
• HOLE_NUM: returns the number of "holes" in the region;
• HOLE_POINT: returns the coordinates of one point in a hole (useful when TRIANGLE is to be invoked);
• INSIDE: reports which of a given set of points are inside the regioin.
• SAMPLE: returns a set of sample points from the region, chosen with uniform probability;
• SAMPLE_H1: returns a set of sample points from the region after it has been enlarged by an amount H1;
• SDIST: returns the signed distance to the boundary of the region for each of a set of input points. (a positive distance means the point is outside the region, a negative distance means it is inside); (Not ready for problems 4, 5, 6, 7, 8, 9 )
• TITLE: a title for the problem;

The test problems include:

1. The unit circle;
2. The unit circle with a circular hole;
3. A square with a circular hole;
4. A hexagon with a hexagonal hole;
5. The horn;
6. The superellipse with a superelliptical hole;
7. The bicycle seat;
8. The slice of pie with a circular hole and triangular notch;
9. Jeff Borggaard's square with two hexagonal holes;
10. The unit square;
11. The L-shaped region;
12. John Shadid's H-shaped region;
13. The Sandia fork;
14. Marcus Garvie's Lake Alpha, with Beta Island;
15. Sangbum Kim's forward step;

Licensing:

The computer code and data files described and made available on this web page are distributed under the MIT license

Languages:

test_triangulation is available in a Fortran90 version and a MATLAB version and an Octave version.

Related Data and Programs:

test_triangulation_test

distmesh, an Octave code which can work from a simple description of the boundary of a region to produce a triangulation of that region.

mesh2d, an Octave code which can automatically create a triangular mesh for a given polygonal region, by darren engwirda.

test_triangulation, an Octave code which defines a number of test regions to be triangulated.

triangulation, an Octave code which carries out various operations on order 3 ("linear") or order 6 ("quadratic") triangulations.

triangulation_order3, a data directory which describes the format for triangulations of order 3.

triangulation_order6, a data directory which describes the format for triangulations of order 6.

Reference:

1. Per-Olof Persson and Gilbert Strang,
   A Simple Mesh Generator in MATLAB,
   SIAM Review,
   Volume 46, Number 2, June 2004, pages 329-345.

Source Code:

• angle_contains_point_2d.m, determines whether an angle contains a point.
• angle_half_2d.m, divides an angle in half.
• angle_rad_2d.m, determines the angle swept out between two rays.
• atan4.m, computes the inverse tangent of the ratio Y / X.
• box_contains_point_2d.m, determines if a box contains a point in 2D.
• circle_arc_point_near_2d.m, nearest point on a circular arc in 2D.
• circle_imp_contains_point_2d.m, determines if a circle contains a point in 2D.
• circle_imp_point_near_2d.m, nearest point on a circle in 2D.
• circle_sector_contains_point_2d.m, determines if a circle sector contains a point in 2D.
• cos_deg.m, returns the cosine of an angle given in degrees.
• file_name_inc.m, generates the next filename in a series.
• fmin_rc.m, seeks the minimum of a scalar function of a scalar argument.
• hex_grid_angle.m, sets the points in an angled hex grid in a box.
• hex_grid_angle_size.m, counts the points in an angled hex grid in a box.
• hexagon_contains_point_2d.m, is TRUE if a point is contained in a hexagon.
• i4_modp.m, returns the remainder of integer division, but always positive.
• i4_wrap.m, forces an integer to lie between two values.
• p00_boundary_eps.m, draws the boundary of the region for any problem.
• p00_boundary_nearest.m, returns the nearest boundary point for any problem.
• p00_boundary_segment.m, returns points on a boundary segment for any problem.
• p00_boundary_segment_length.m, returns the number of points to use for boundary segments for any problem.
• p00_boundary_segment_num.m, returns the number of boundary segments for any problem.
• p00_box.m, returns a bounding box for any problem.
• p00_density.m, returns the mesh density for any problem.
• p00_element_size.m, returns a suggested element size for any problem.
• p00_fixed_num.m, returns the number of fixed points for any problem.
• p00_fixed_points.m, returns the fixed points for any problem.
• p00_header.m, prints the header for any problem.
• p00_hex_grid.m, returns hex grid points in a region.
• p00_hex_grid_count.m, counts the number of hex grid points in a region.
• p00_hole_num.m, returns the number of holes in the region for any problem.
• p00_hole_point.m, returns a point in a hole in the region for any problem.
• p00_inside.m, is TRUE for each point that is inside the region, for any problem.
• p00_points_eps.m, draws a plot of the region and some sample points for any problem.
• p00_poly_write.m, assembles geometric information and writes it as a POLY file for any problem.
• p00_sample.m, returns sample points from the region for any problem.
• p00_test_num.m, returns the number of problems.
• p00_title.m, returns the title for any problem.
• p01_boundary_nearest.m, returns the nearest boundary point for problem 01.
• p01_boundary_project.m, projects exterior points onto the boundary for problem 01.
• p01_boundary_segment.m, returns points on a boundary segment for problem 01.
• p01_boundary_segment_length.m, returns the number of points to use for boundary segments for problem 01.
• p01_boundary_segment_num.m, returns the number of boundary segments for problem 01.
• p01_box.m, returns a bounding box for problem 01.
• p01_density.m, returns the mesh density for problem 01.
• p01_element_size.m, returns a suggested element size for problem 01.
• p01_fixed_num.m, returns the number of fixed points for problem 01.
• p01_fixed_points.m, returns the fixed points for problem 01.
• p01_header.m, prints the header for problem 01.
• p01_hole_num.m, returns the number of holes in the region for problem 01.
• p01_hole_point.m, returns a point in a hole in the region for problem 01.
• p01_inside.m, is TRUE for each point inside the region in problem 01.
• p01_sample.m, returns sample points from the region for problem 01.
• p01_title.m, returns a title for problem 01.
• p02_boundary_nearest.m, returns the nearest boundary point for problem 02.
• p02_boundary_segment.m, returns points on a boundary segment for problem 02.
• p02_boundary_segment_length.m, returns the number of points to use for boundary segments for problem 02.
• p02_boundary_segment_num.m, returns the number of boundary segments for problem 02.
• p02_box.m, returns a bounding box for problem 02.
• p02_density.m, returns the mesh density for problem 02.
• p02_element_size.m, returns a suggested element size for problem 02.
• p02_fixed_num.m, returns the number of fixed points for problem 02.
• p02_fixed_points.m, returns the fixed points for problem 02.
• p02_header.m, prints the header for problem 02.
• p02_hole_num.m, returns the number of holes in the region for problem 02.
• p02_hole_point.m, returns a point in a hole in the region for problem 02.
• p02_inside.m, is TRUE for each point inside the region in problem 02.
• p02_sample.m, returns sample points from the region for problem 02.
• p02_title.m, returns a title for problem 02.
• p03_boundary_nearest.m, returns the nearest boundary point for problem 03.
• p03_boundary_segment.m, returns points on a boundary segment for problem 03.
• p03_boundary_segment_length.m, returns the number of points to use for boundary segments for problem 03.
• p03_boundary_segment_num.m, returns the number of boundary segments for problem 03.
• p03_box.m, returns a bounding box for problem 03.
• p03_density.m, returns the mesh density for problem 03.
• p03_element_size.m, returns a suggested element size for problem 03.
• p03_fixed_num.m, returns the number of fixed points for problem 03.
• p03_fixed_points.m, returns the fixed points for problem 03.
• p03_header.m, prints the header for problem 03.
• p03_hole_num.m, returns the number of holes in the region for problem 03.
• p03_hole_point.m, returns a point in a hole in the region for problem 03.
• p03_inside.m, is TRUE for each point inside the region in problem 03.
• p03_sample.m, returns sample points from the region for problem 03.
• p03_title.m, returns a title for problem 03.
• p04_boundary_nearest.m, returns the nearest boundary point for problem 04.
• p04_boundary_segment.m, returns points on a boundary segment for problem 04.
• p04_boundary_segment_length.m, returns the number of points to use for boundary segments for problem 04.
• p04_boundary_segment_num.m, returns the number of boundary segments for problem 04.
• p04_box.m, returns a bounding box for problem 04.
• p04_density.m, returns the mesh density for problem 04.
• p04_element_size.m, returns a suggested element size for problem 04.
• p04_fixed_num.m, returns the number of fixed points for problem 04.
• p04_fixed_points.m, returns the fixed points for problem 04.
• p04_header.m, prints the header for problem 04.
• p04_hole_num.m, returns the number of holes in the region for problem 04.
• p04_hole_point.m, returns a point in a hole in the region for problem 04.
• p04_inside.m, is TRUE for each point inside the region in problem 04.
• p04_sample.m, returns sample points from the region for problem 04.
• p04_title.m, returns a title for problem 04.
• p05_boundary_nearest.m, returns the nearest boundary point for problem 05.
• p05_boundary_segment.m, returns points on a boundary segment for problem 05.
• p05_boundary_segment_length.m, returns the number of points to use for boundary segments for problem 05.
• p05_boundary_segment_num.m, returns the number of boundary segments for problem 05.
• p05_box.m, returns a bounding box for problem 05.
• p05_density.m, returns the mesh density for problem 05.
• p05_element_size.m, returns a suggested element size for problem 05.
• p05_fixed_num.m, returns the number of fixed points for problem 05.
• p05_fixed_points.m, returns the fixed points for problem 05.
• p05_header.m, prints the header for problem 05.
• p05_hole_num.m, returns the number of holes in the region for problem 05.
• p05_hole_point.m, returns a point in a hole in the region for problem 05.
• p05_inside.m, is TRUE for each point inside the region in problem 05.
• p05_sample.m, returns sample points from the region for problem 05.
• p05_title.m, returns a title for problem 05.
• p06_boundary_nearest.m, returns the nearest boundary point for problem 06.
• p06_boundary_segment_num.m, returns the number of boundary segments for problem 06.
• p06_boundary_segment_length.m, returns the number of points to use for boundary segments for problem 06.
• p06_boundary_segment_num.m, returns the number of boundary segments for problem 06.
• p06_box.m, returns a bounding box for problem 06.
• p06_density.m, returns the mesh density for problem 06.
• p06_element_size.m, returns a suggested element size for problem 06.
• p06_fixed_num.m, returns the number of fixed points for problem 06.
• p06_fixed_points.m, returns the fixed points for problem 06.
• p06_header.m, prints the header for problem 06.
• p06_hole_num.m, returns the number of holes in the region for problem 06.
• p06_hole_point.m, returns a point in a hole in the region for problem 06.
• p06_inside.m, is TRUE for each point inside the region in problem 06.
• p06_sample.m, returns sample points from the region for problem 06.
• p06_title.m, returns a title for problem 06.
• p07_boundary_nearest.m, returns the nearest boundary point for problem 07.
• p07_boundary_segment_num.m, returns the number of boundary segments for problem 07.
• p07_boundary_segment_length.m, returns the number of points to use for boundary segments for problem 07.
• p07_boundary_segment_num.m, returns the number of boundary segments for problem 07.
• p07_box.m, returns a bounding box for problem 07.
• p07_density.m, returns the mesh density for problem 07.
• p07_element_size.m, returns a suggested element size for problem 07.
• p07_fixed_num.m, returns the number of fixed points for problem 07.
• p07_fixed_points.m, returns the fixed points for problem 07.
• p07_header.m, prints the header for problem 07.
• p07_hole_num.m, returns the number of holes in the region for problem 07.
• p07_hole_point.m, returns a point in a hole in the region for problem 07.
• p07_inside.m, is TRUE for each point inside the region in problem 07.
• p07_sample.m, returns sample points from the region for problem 07.
• p07_title.m, returns a title for problem 07.
• p08_boundary_nearest.m, returns the nearest boundary point for problem 08.
• p08_boundary_segment.m, returns points on a boundary segment for problem 08.
• p08_boundary_segment_length.m, returns the number of points on a boundary segment for problem 08.
• p08_boundary_segment_num.m, returns the number of boundary segments for problem 08.
• p08_box.m, returns a bounding box for problem 08.
• p08_density.m, returns the mesh density for problem 08.
• p08_element_size.m, returns the element size for problem 08.
• p08_fixed_num.m, returns the number of fixed points for problem 08.
• p08_fixed_points.m, returns the fixed points for problem 08.
• p08_header.m, prints the header for problem 08.
• p08_hole_num.m, returns the number of holes for problem 08.
• p08_hole_point.m, returns a point in a given hole for problem 08.
• p08_inside.m, is TRUE for each point inside the region in problem 08.
• p08_sample.m, samples points from the region in problem 08.
• p08_sdist.m, returns the signed distance to the region for problem 08.
• p08_title.m, returns a title for problem 08.
• p09_boundary_nearest.m, returns the nearest boundary point for problem 09.
• p09_boundary_segment_num.m, returns the number of boundary segments for problem 09.
• p09_boundary_segment_length.m, returns the number of points to use for boundary segments for problem 09.
• p09_boundary_segment_num.m, returns the number of boundary segments for problem 09.
• p09_box.m, returns a bounding box for problem 09.
• p09_density.m, returns the mesh density for problem 09.
• p09_element_size.m, returns a suggested element size for problem 09.
• p09_fixed_num.m, returns the number of fixed points for problem 09.
• p09_fixed_points.m, returns the fixed points for problem 09.
• p09_header.m, prints the header for problem 09.
• p09_hole_num.m, returns the number of holes in the region for problem 09.
• p09_hole_point.m, returns a point in a hole in the region for problem 09.
• p09_inside.m, is TRUE for each point inside the region in problem 09.
• p09_sample.m, samples points from the region in problem 09.
• p09_title.m, returns a title for problem 09.
• p10_boundary_nearest.m, returns the nearest boundary point for problem 10.
• p10_boundary_segment_num.m, returns the number of boundary segments for problem 10.
• p10_boundary_segment_length.m, returns the number of points to use for boundary segments for problem 10.
• p10_boundary_segment_num.m, returns the number of boundary segments for problem 10.
• p10_box.m, returns a bounding box for problem 10.
• p10_density.m, returns the mesh density for problem 10.
• p10_element_size.m, returns a suggested element size for problem 10.
• p10_fixed_num.m, returns the number of fixed points for problem 10.
• p10_fixed_points.m, returns the fixed points for problem 10.
• p10_header.m, prints the header for problem 10.
• p10_hole_num.m, returns the number of holes in the region for problem 10.
• p10_hole_point.m, returns a point in a hole in the region for problem 10.
• p10_inside.m, is TRUE for each point inside the region in problem 10.
• p10_sample.m, samples points from the region in problem 10.
• p10_title.m, returns a title for problem 10.
• p11_boundary_nearest.m, returns the nearest boundary point for problem 11.
• p11_boundary_segment_num.m, returns the number of boundary segments for problem 11.
• p11_boundary_segment_length.m, returns the number of points to use for boundary segments for problem 11.
• p11_boundary_segment_num.m, returns the number of boundary segments for problem 11.
• p11_box.m, returns a bounding box for problem 11.
• p11_density.m, returns the mesh density for problem 11.
• p11_element_size.m, returns a suggested element size for problem 11.
• p11_fixed_num.m, returns the number of fixed points for problem 11.
• p11_fixed_points.m, returns the fixed points for problem 11.
• p11_header.m, prints the header for problem 11.
• p11_hole_num.m, returns the number of holes in the region for problem 11.
• p11_hole_point.m, returns a point in a hole in the region for problem 11.
• p11_inside.m, is TRUE for each point inside the region in problem 11.
• p11_sample.m, samples points from the region in problem 11.
• p11_title.m, returns a title for problem 11.
• p12_boundary_nearest.m, returns the nearest boundary point for problem 12.
• p12_boundary_segment_num.m, returns the number of boundary segments for problem 12.
• p12_boundary_segment_length.m, returns the number of points to use for boundary segments for problem 12.
• p12_boundary_segment_num.m, returns the number of boundary segments for problem 12.
• p12_box.m, returns a bounding box for problem 12.
• p12_density.m, returns the mesh density for problem 12.
• p12_element_size.m, returns a suggested element size for problem 12.
• p12_fixed_num.m, returns the number of fixed points for problem 12.
• p12_fixed_points.m, returns the fixed points for problem 12.
• p12_header.m, prints the header for problem 12.
• p12_hole_num.m, returns the number of holes in the region for problem 12.
• p12_hole_point.m, returns a point in a hole in the region for problem 12.
• p12_inside.m, is TRUE for each point inside the region in problem 12.
• p12_sample.m, samples points from the region in problem 12.
• p12_title.m, returns a title for problem 12.
• p13_boundary_nearest.m, returns the nearest boundary point for problem 13.
• p13_boundary_segment_num.m, returns the number of boundary segments for problem 13.
• p13_boundary_segment_length.m, returns the number of points to use for boundary segments for problem 13.
• p13_boundary_segment_num.m, returns the number of boundary segments for problem 13.
• p13_box.m, returns a bounding box for problem 13.
• p13_density.m, returns the mesh density for problem 13.
• p13_element_size.m, returns a suggested element size for problem 13.
• p13_fixed_num.m, returns the number of fixed points for problem 13.
• p13_fixed_points.m, returns the fixed points for problem 13.
• p13_header.m, prints the header for problem 13.
• p13_hole_num.m, returns the number of holes in the region for problem 13.
• p13_hole_point.m, returns a point in a hole in the region for problem 13.
• p13_inside.m, is TRUE for each point inside the region in problem 13.
• p13_sample.m, samples points from the region in problem 13.
• p13_title.m, returns a title for problem 13.
• p14_boundary_nearest.m, returns the nearest boundary point for problem 14.
• p14_boundary_segment_num.m, returns the number of boundary segments for problem 14.
• p14_boundary_segment_length.m, returns the number of points to use for boundary segments for problem 14.
• p14_boundary_segment_num.m, returns the number of boundary segments for problem 14.
• p14_box.m, returns a bounding box for problem 14.
• p14_density.m, returns the mesh density for problem 14.
• p14_element_size.m, returns a suggested element size for problem 14.
• p14_fixed_num.m, returns the number of fixed points for problem 14.
• p14_fixed_points.m, returns the fixed points for problem 14.
• p14_header.m, prints the header for problem 14.
• p14_hole_num.m, returns the number of holes in the region for problem 14.
• p14_hole_point.m, returns a point in a hole in the region for problem 14.
• p14_inside.m, is TRUE for each point inside the region in problem 14.
• p14_sample.m, samples points from the region in problem 14.
• p14_title.m, returns a title for problem 14.
• p15_boundary_nearest.m, returns the nearest boundary point for problem 15.
• p15_boundary_segment_num.m, returns the number of boundary segments for problem 15.
• p15_boundary_segment_length.m, returns the number of points to use for boundary segments for problem 15.
• p15_boundary_segment_num.m, returns the number of boundary segments for problem 15.
• p15_box.m, returns a bounding box for problem 15.
• p15_density.m, returns the mesh density for problem 15.
• p15_element_size.m, returns a suggested element size for problem 15.
• p15_fixed_num.m, returns the number of fixed points for problem 15.
• p15_fixed_points.m, returns the fixed points for problem 15.
• p15_header.m, prints the header for problem 15.
• p15_hole_num.m, returns the number of holes in the region for problem 15.
• p15_hole_point.m, returns a point in a hole in the region for problem 15.
• p15_inside.m, is TRUE for each point inside the region in problem 15.
• p15_sample.m, samples points from the region in problem 15.
• p15_title.m, returns a title for problem 15.
• poly_write.m, writes data to a POLY file.
• polygon_contains_point_2d.m, finds if a point is inside a simple polygon in 2D.
• polygon_expand_2d.m, expands a polygon in 2D.
• polygon_point_near_2d.m, finds the nearest point on a polygon in 2D.
• polyloop_arclength_nd.m, determines the arclength of points on a polyloop in ND.
• polyloop_length_nd.m, determines the length of a polyloop in ND.
• polyloop_points_nd.m, computes equally spaced points on a polyloop in ND.
• quad_contains_point_2d.m, finds if a point is inside a quadrilateral in 2D.
• r8_modp.m, returns the nonnegative remainder of R8 division.
• r8_sign.m, returns the sign of an R8.
• r8_uniform_01.m, returns a unit pseudorandom R8.
• r8mat_transpose_print.m, prints an R8MAT, transposed.
• r8mat_transpose_print_some.m, prints some of an R8MAT, transposed.
• r8mat_uniform_01.m, returns a unit pseudorandom R8MAT.
• r8mat_write.m, writes an R8MAT file.
• r8poly2_rroot.m, returns the real part of roots of a quadratic polynomial.
• r8vec_print.m, prints an R8VEC.
• s_len_trim.m, returns the length of a string to the last nonblank.
• segment_point_near_2d.m, finds the point on a line segment nearest a point in 2D.
• sin_deg.m, returns the sine of an angle given in degrees.
• triangle_contains_point_2d.m, determines whether a triangle contains a point.