triangulation

triangulation — Delaunay and Voronoi triangulation and interpolation

Synopsis

#include <libprocess/gwyprocess.h>

struct              GwyTriangulation;
struct              GwyTriangulationClass;
#define             GWY_TRIANGULATION_NONE
                    GwyTriangulationPointXY;
                    GwyTriangulationPointXYZ;
                    GwyTriangulationData;
GwyTriangulation *  gwy_triangulation_new               (void);
gboolean            gwy_triangulation_triangulate       (GwyTriangulation *triangulation,
                                                         guint npoints,
                                                         gconstpointer points,
                                                         gsize point_size);
gboolean            gwy_triangulation_interpolate       (GwyTriangulation *triangulation,
                                                         GwyInterpolationType interpolation,
                                                         GwyDataField *dfield);
void                gwy_triangulation_data_free         (GwyTriangulationData *triangulation_data);
GwyTriangulationData * gwy_triangulation_delaunay       (GwyTriangulation *triangulation);
GwyTriangulationData * gwy_triangulation_boundary       (GwyTriangulation *triangulation);
GwyTriangulationData * gwy_triangulation_voronoi        (GwyTriangulation *triangulation,
                                                         guint *nvpoints,
                                                         const GwyTriangulationPointXY **vpoints);

Object Hierarchy

  GObject
   +----GwyTriangulation

Description

Details

struct GwyTriangulation

struct GwyTriangulation;


struct GwyTriangulationClass

struct GwyTriangulationClass {
    GObjectClass parent_class;
};


GWY_TRIANGULATION_NONE

#define GWY_TRIANGULATION_NONE G_MAXUINT

Point index value representing no point.

Since 2.18


GwyTriangulationPointXY

typedef struct {
    gdouble x;
    gdouble y;
} GwyTriangulationPointXY;

Representation of a point in plane for triangulation.

gdouble x;

X-coordinate.

gdouble y;

Y-coordinate.

Since 2.18


GwyTriangulationPointXYZ

typedef struct {
    gdouble x;
    gdouble y;
    gdouble z;
} GwyTriangulationPointXYZ;

Representation of a point in plane with associated value for interpolation.

gdouble x;

X-coordinate.

gdouble y;

Y-coordinate.

gdouble z;

Z-coordinate, i.e. the value in point (x,y).

Since 2.18


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.

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.

Since 2.18


gwy_triangulation_new ()

GwyTriangulation *  gwy_triangulation_new               (void);

Creates a new triangulation.

Returns :

A new empty triangulation.

Since 2.18


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.

triangulation :

Triangulation.

npoints :

Number of points.

points :

Array of points. They must be typecastable to GwyTriangulationPointXY for triangulation and to GwyTriangulationPointXYZ for interpolation. However, they can be larger than that. The actual struct size is indicated by point_size.

point_size :

Size of point struct, in bytes.

Returns :

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

Since 2.18


gwy_triangulation_interpolate ()

gboolean            gwy_triangulation_interpolate       (GwyTriangulation *triangulation,
                                                         GwyInterpolationType interpolation,
                                                         GwyDataField *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.

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.

Since 2.18


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.

triangulation_data :

Raw triangulation data.

Since 2.18


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().

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.

Since 2.18


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.

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.

Since 2.18


gwy_triangulation_voronoi ()

GwyTriangulationData * gwy_triangulation_voronoi        (GwyTriangulation *triangulation,
                                                         guint *nvpoints,
                                                         const GwyTriangulationPointXY **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.

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.

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.

Since 2.18