## Triangulation

Triangulation — Delaunay and Voronoi triangulation and interpolation

## Functions

GwyTriangulation * | gwy_triangulation_new ()
gboolean | gwy_triangulation_triangulate ()
gboolean | gwy_triangulation_triangulate_iterative ()
gboolean | gwy_triangulation_interpolate ()
void | gwy_triangulation_data_free ()
GwyTriangulationData * | gwy_triangulation_delaunay ()
GwyTriangulationData * | gwy_triangulation_boundary ()
GwyTriangulationData * | gwy_triangulation_voronoi ()

## Types and Values

#define | GWY_TRIANGULATION_NONE
| GwyTriangulationData
struct | GwyTriangulation
struct | GwyTriangulationClass

## Object Hierarchy

        GObject
        ╰── GwyTriangulation

## Includes

    #include <libgwyddion/gwyddion.h>

## Description

## Functions

### gwy_triangulation_new()

    GwyTriangulation *
    gwy_triangulation_new (void);

Creates a new triangulation.

#### Returns

A new empty triangulation.

### gwy_triangulation_triangulate()

    gboolean
    gwy_triangulation_triangulate (GwyTriangulation *triangulation,
                                   guint npoints,
                                   gconstpointer points,
                                   gsize point_size);

Finds Delaunay and Voronoi triangulations for a set of points in plane.

The triangulation might not work in numerically unstable cases. At present this includes various ambiguous cases with neighbour points on straight lines or circles. Also, no points in the input set may coincide.

It is possible to call this method successively on several different sets of points to triangulate each separately. Note that pointers in data returned by methods such as `gwy_triangulation_delaunay()` become invalid then.

#### Parameters

triangulation | Triangulation. |
npoints | Number of points. |
points | Array of points. They must be typecastable to GwyXY for triangulation and to GwyXYZ for interpolation. However, they can be larger than that. The actual struct size is indicated by `point_size` . | [array length=npoints]
point_size | Size of point struct, in bytes. |

#### Returns

`TRUE` on success, `FALSE` on failure. On failure the triangulation is empty.

### gwy_triangulation_triangulate_iterative()

    gboolean
    gwy_triangulation_triangulate_iterative
                                   (GwyTriangulation *triangulation,
                                    guint npoints,
                                    gconstpointer points,
                                    gsize point_size,
                                    GwySetFractionFunc set_fraction,
                                    GwySetMessageFunc set_message);

Finds Delaunay and Voronoi triangulations for a set of points in plane.

See `gwy_triangulation_triangulate()` for discussion. This function differs only by the optional `set_fraction` and `set_message` arguments that permit providing user feedback for large triangulations and cancelling the procedure upon request.

#### Parameters

triangulation | Triangulation. |
npoints | Number of points. |
points | Array of points. They must be typecastable to GwyXY for triangulation and to GwyXYZ for interpolation. However, they can be larger than that. The actual struct size is indicated by `point_size` . | [array length=npoints]
point_size | Size of point struct, in bytes. |
set_fraction | Function that sets fraction to output (or `NULL`). | [scope call][nullable]
set_message | Function that sets message to output (or `NULL`). | [scope call][nullable]

#### Returns

`TRUE` on success, `FALSE` on failure. On failure the triangulation is empty. Cancellation via `set_fraction` or `set_message` callback also counts as failure.

### gwy_triangulation_interpolate()

    gboolean
    gwy_triangulation_interpolate (GwyTriangulation *triangulation,
                                   GwyInterpolationType interpolation,
                                   GwyField *dfield);

Regularizes XYZ data to a grid, represented by a data field.

The area and resolution of the regular grid is given by the dimensions and offsets of `dfield` .

#### Parameters

triangulation | Triangulation. |
interpolation | Interpolation to use. Only `GWY_INTERPOLATION_ROUND` and `GWY_INTERPOLATION_LINEAR` are implemented. Is is an error to pass any other interpolation type. |
dfield | Data field to fill with interpolated values. |

#### Returns

`TRUE` if the interpolation succeeds, `FALSE` on failure, e.g. due to numerical errors. In the latter case the contents of `dfield` is undefined.

### gwy_triangulation_data_free()

    void
    gwy_triangulation_data_free (GwyTriangulationData *triangulation_data);

Frees raw triangulation data.

This function should be used to free triangulation data returned by `gwy_triangulation_delaunay()` and similar. It does not free the array members as they are owned by the triangulation object.

#### Parameters

triangulation_data | Raw triangulation data. |

### gwy_triangulation_delaunay()

    GwyTriangulationData *
    gwy_triangulation_delaunay (GwyTriangulation *triangulation);

Obtains the Delaunay triangulation data.

Notes to the fields in the returned struct:

`npoints` equals to the number of points passed to `gwy_triangulation_triangulate()`.

#### Parameters

triangulation | Triangulation. |

#### Returns

Newly clreated GwyTriangulationData that must be freed with `gwy_triangulation_data_free()` when no longer used. The data within is owned by `triangulation` , see GwyTriangulationData.

### gwy_triangulation_boundary()

    GwyTriangulationData *
    gwy_triangulation_boundary (GwyTriangulation *triangulation);

Obtains the boundary, i.e. convex hull, of Delaunay triangulation.

Notes to the fields in the returned struct:

`npoints` equals to the number of points passed to `gwy_triangulation_triangulate()`.

`size` is the boundary length.

`index` [] contains point indices in the boundary for points on the boundary; and `GWY_TRIANGULATION_NONE` for points not on the boundary.

`neighbours` [] lists sequentially the boundary points.

#### Parameters

triangulation | Triangulation. |

#### Returns

Newly clreated GwyTriangulationData that must be freed with `gwy_triangulation_data_free()` when no longer used. The data within is owned by `triangulation` , see GwyTriangulationData.

### gwy_triangulation_voronoi()

    GwyTriangulationData *
    gwy_triangulation_voronoi (GwyTriangulation *triangulation,
                               guint *nvpoints,
                               const GwyXY **vpoints);

Obtains the Voronoi triangulation data.

Notes to the fields in the returned struct:

`npoints` equals to the number of Delaunay triangulation points passed to `gwy_triangulation_triangulate()` plus the number of points in the Voronoi triangulation, `nvpoints` . Voronoi triangulation points are the vertices of Voronoi cells. So each triangle has one original (Delaunay) point and two cell vertices (Voronoi points).

`index` [] is the usual index of blocks in `neighbours` , however, point indices smaller than the number of Delaunay points correspond to the Delaunay points, point indices equal or larger correspond to points in `vpoints` (it is necessary to subtract the number of original points to obtain the real position in `vpoints` ).

`neighbours` [] contains the neighbour blocks, with above caveats about point numbering.

#### Parameters

triangulation | Triangulation. |
nvpoints | Location to store the number of new Voronoi triangulation points, or `NULL`. |
vpoints | Location to store pointer to the Voronoi triangulation points, or `NULL`. |

#### Returns

Newly clreated GwyTriangulationData that must be freed with `gwy_triangulation_data_free()` when no longer used. The data within is owned by `triangulation` , see GwyTriangulationData.

## Types and Values

### GWY_TRIANGULATION_NONE

    #define GWY_TRIANGULATION_NONE G_MAXUINT

Point index value representing no point.

### GwyTriangulationData

    typedef struct {
        guint npoints;
        guint size;
        const guint *index;
        const guint *neighbours;
    } GwyTriangulationData;

Representation of raw triangulation data.

Members `index` and `neighbours` are owned by the GwyTriangulation object that provided this data and remain valid only until this object is destroyed or used to perform another triangulation.

The exact interpretation of individual parts depends on what kind of triangulation data it is and may differ a bit from the general description provided here. See the descriptions of individual methods returning GwyTriangulationData.

#### Members

guint `npoints`; | Number of points in the set, also detrmines the size of `index` . |
guint `size`; | The length of `neighbours` . |
const guint *`index`; | Array of size `npoints` +1 defining the blocks of neighbours in `neighbours` . The block for point `i` starts at `index` [`i` ] and ends one element before `index` [`i` +1]. Hence the last of `index` is equal to `size` . |
const guint *`neighbours`; | Neighbours of each point, represented as indices into some array (which array, that depends on what kind of data it is). The points in each block are sorted counter-clockwise. |

### struct GwyTriangulation

    struct GwyTriangulation;

### struct GwyTriangulationClass

    struct GwyTriangulationClass {
        GObjectClass parent_class;
    };