GtsPGraph

Name

GtsPGraph -- 

Synopsis

#define             GTS_C_VAR
extern              const guint gts_major_version;
extern              const guint gts_minor_version;
extern              const guint gts_micro_version;
extern              const guint gts_interface_age;
extern              const guint gts_binary_age;
#define             GTS_CHECK_VERSION                   (major,minor,micro)
#define             GTS_COMMENTS
#define             GTS_MAINTAINER
                    GtsObjectClassInfo;
void                (*GtsObjectClassInitFunc)           (GtsObjectClass *objclass);
void                (*GtsObjectInitFunc)                (GtsObject *obj);
void                (*GtsArgSetFunc)                    (GtsObject *obj);
void                (*GtsArgGetFunc)                    (GtsObject *obj);
typedef             GtsVector;
typedef             GtsVector4;
typedef             GtsMatrix;
gdouble             (*GtsKeyFunc)                       (gpointer item,
                                                         gpointer data);
enum                GtsIntersect;
                    GtsColor;
gint                (*GtsFunc)                          (gpointer item,
                                                         gpointer data);
                    GtsFile;
enum                GtsTokenType;
                    GtsFileVariable;
GtsFile *           gts_file_new                        (FILE *fp);
GtsFile *           gts_file_new_from_string            (gchar *s);
GtsFile *           gts_file_new_from_buffer            (gchar *buf,
                                                         size_t len);
void                gts_file_verror                     (GtsFile *f,
                                                         const gchar *format,
                                                         va_list args);
void                gts_file_error                      (GtsFile *f,
                                                         const gchar *format,
                                                         ...);
gint                gts_file_getc                       (GtsFile *f);
guint               gts_file_read                       (GtsFile *f,
                                                         gpointer ptr,
                                                         guint size,
                                                         guint nmemb);
gint                gts_file_getc_scope                 (GtsFile *f);
void                gts_file_next_token                 (GtsFile *f);
void                gts_file_first_token_after          (GtsFile *f,
                                                         GtsTokenType type);
void                gts_file_assign_start               (GtsFile *f,
                                                         GtsFileVariable *vars);
GtsFileVariable *   gts_file_assign_next                (GtsFile *f,
                                                         GtsFileVariable *vars);
void                gts_file_assign_variables           (GtsFile *f,
                                                         GtsFileVariable *vars);
void                gts_file_variable_error             (GtsFile *f,
                                                         GtsFileVariable *vars,
                                                         const gchar *name,
                                                         const gchar *format,
                                                         ...);
void                gts_file_destroy                    (GtsFile *f);
#define             GTS_OBJECT_CAST                     (obj, type, klass)
#define             GTS_OBJECT_CLASS_CAST               (objklass, type, klass)
#define             GTS_CLASS_NAME_LENGTH
enum                GtsObjectFlags;
#define             GTS_OBJECT_FLAGS                    (obj)
#define             GTS_OBJECT_DESTROYED                (obj)
#define             GTS_OBJECT_SET_FLAGS                (obj,flag)
#define             GTS_OBJECT_UNSET_FLAGS              (obj,flag)
                    GtsObject;
gpointer            gts_object_class_new                (GtsObjectClass *parent_class,
                                                         GtsObjectClassInfo *info);
GtsObjectClass *    gts_object_class                    (void);
gpointer            gts_object_check_cast               (gpointer object,
                                                         gpointer klass);
gpointer            gts_object_class_check_cast         (gpointer klass,
                                                         gpointer from);
gpointer            gts_object_is_from_class            (gpointer object);
gpointer            gts_object_class_is_from_class      (gpointer klass);
GtsObjectClass *    gts_object_class_from_name          (const gchar *name);
GtsObject *         gts_object_new                      (GtsObjectClass *klass);
GtsObject *         gts_object_clone                    (GtsObject *object);
void                gts_object_attributes               (GtsObject *object,
                                                         GtsObject *from);
void                gts_object_init                     (GtsObject *object,
                                                         GtsObjectClass *klass);
void                gts_object_reset_reserved           (GtsObject *object);
void                gts_object_destroy                  (GtsObject *object);
void                gts_finalize                        (void);
                    GtsRange;
void                gts_range_init                      (GtsRange *r);
void                gts_range_reset                     (GtsRange *r);
void                gts_range_add_value                 (GtsRange *r,
                                                         gdouble val);
void                gts_range_update                    (GtsRange *r);
void                gts_range_print                     (GtsRange *r,
                                                         FILE *fptr);
#define             GTS_IS_POINT                        (obj)
#define             GTS_POINT                           (obj)
#define             GTS_POINT_CLASS                     (klass)
                    GtsPoint;
GtsPointClass *     gts_point_class                     (void);
GtsPoint *          gts_point_new                       (GtsPointClass *klass,
                                                         gdouble x,
                                                         gdouble y,
                                                         gdouble z);
void                gts_point_set                       (GtsPoint *p,
                                                         gdouble x,
                                                         gdouble y,
                                                         gdouble z);
#define             gts_point_is_in_rectangle           (p, p1, p2)
GtsPoint *          gts_segment_triangle_intersection   (GtsSegment *s,
                                                         GtsTriangle *t,
                                                         gboolean boundary,
                                                         GtsPointClass *klass);
void                gts_point_transform                 (GtsPoint *p,
                                                         GtsMatrix *m);
gdouble             gts_point_distance                  (GtsPoint *p1,
                                                         GtsPoint *p2);
gdouble             gts_point_distance2                 (GtsPoint *p1,
                                                         GtsPoint *p2);
gdouble             gts_point_orientation_3d            (GtsPoint *p1,
                                                         GtsPoint *p2,
                                                         GtsPoint *p3,
                                                         GtsPoint *p4);
gint                gts_point_orientation_3d_sos        (GtsPoint *p1,
                                                         GtsPoint *p2,
                                                         GtsPoint *p3,
                                                         GtsPoint *p4);
GtsIntersect        gts_point_is_in_triangle            (GtsPoint *p,
                                                         GtsTriangle *t);
gdouble             gts_point_in_circle                 (GtsPoint *p,
                                                         GtsPoint *p1,
                                                         GtsPoint *p2,
                                                         GtsPoint *p3);
gdouble             gts_point_in_sphere                 (GtsPoint *p,
                                                         GtsPoint *p1,
                                                         GtsPoint *p2,
                                                         GtsPoint *p3,
                                                         GtsPoint *p4);
gdouble             gts_point_in_triangle_circle        (GtsPoint *p,
                                                         GtsTriangle *t);
gdouble             gts_point_orientation               (GtsPoint *p1,
                                                         GtsPoint *p2,
                                                         GtsPoint *p3);
gint                gts_point_orientation_sos           (GtsPoint *p1,
                                                         GtsPoint *p2,
                                                         GtsPoint *p3);
gdouble             gts_point_segment_distance2         (GtsPoint *p,
                                                         GtsSegment *s);
gdouble             gts_point_segment_distance          (GtsPoint *p,
                                                         GtsSegment *s);
void                gts_point_segment_closest           (GtsPoint *p,
                                                         GtsSegment *s,
                                                         GtsPoint *closest);
gdouble             gts_point_triangle_distance2        (GtsPoint *p,
                                                         GtsTriangle *t);
gdouble             gts_point_triangle_distance         (GtsPoint *p,
                                                         GtsTriangle *t);
void                gts_point_triangle_closest          (GtsPoint *p,
                                                         GtsTriangle *t,
                                                         GtsPoint *closest);
gboolean            gts_point_is_inside_surface         (GtsPoint *p,
                                                         GNode *tree,
                                                         gboolean is_open);
#define             GTS_IS_VERTEX                       (obj)
#define             GTS_VERTEX                          (obj)
#define             GTS_VERTEX_CLASS                    (klass)
                    GtsVertex;
GtsVertexClass *    gts_vertex_class                    (void);
GtsVertex *         gts_vertex_new                      (GtsVertexClass *klass,
                                                         gdouble x,
                                                         gdouble y,
                                                         gdouble z);
void                gts_vertex_replace                  (GtsVertex *v,
                                                         GtsVertex *with);
gboolean            gts_vertex_is_unattached            (GtsVertex *v);
GtsSegment *        gts_vertices_are_connected          (GtsVertex *v1,
                                                         GtsVertex *v2);
GSList *            gts_vertex_triangles                (GtsVertex *v,
                                                         GSList *list);
GSList *            gts_vertex_faces                    (GtsVertex *v,
                                                         GtsSurface *surface,
                                                         GSList *list);
GSList *            gts_vertex_neighbors                (GtsVertex *v,
                                                         GSList *list,
                                                         GtsSurface *surface);
GSList *            gts_vertices_from_segments          (GSList *segments);
gboolean            gts_vertex_is_boundary              (GtsVertex *v,
                                                         GtsSurface *surface);
GList *             gts_vertices_merge                  (GList *vertices,
                                                         gdouble epsilon,
                                                         gboolean (checkGtsVertex *, GtsVertex *) ());
GSList *            gts_vertex_fan_oriented             (GtsVertex *v,
                                                         GtsSurface *surface);
guint               gts_vertex_is_contact               (GtsVertex *v,
                                                         gboolean sever);
                    GtsVertexNormal;
#define             GTS_VERTEX_NORMAL                   (obj)
#define             GTS_IS_VERTEX_NORMAL                (obj)
GtsVertexClass *    gts_vertex_normal_class             (void);
                    GtsColorVertex;
#define             GTS_COLOR_VERTEX                    (obj)
#define             GTS_IS_COLOR_VERTEX                 (obj)
GtsVertexClass *    gts_color_vertex_class              (void);
#define             GTS_IS_SEGMENT                      (obj)
#define             GTS_SEGMENT                         (obj)
#define             GTS_SEGMENT_CLASS                   (klass)
                    GtsSegment;
GtsSegmentClass *   gts_segment_class                   (void);
GtsSegment *        gts_segment_new                     (GtsSegmentClass *klass,
                                                         GtsVertex *v1,
                                                         GtsVertex *v2);
#define             gts_segment_connect                 (s, e1, e2)
#define             gts_segments_are_identical          (s1, s2)
#define             gts_segments_touch                  (s1, s2)
GtsIntersect        gts_segments_are_intersecting       (GtsSegment *s1,
                                                         GtsSegment *s2);
GtsSegment *        gts_segment_is_duplicate            (GtsSegment *s);
GtsVertex *         gts_segment_midvertex               (GtsSegment *s,
                                                         GtsVertexClass *klass);
GSList *            gts_segments_from_vertices          (GSList *vertices);
gboolean            gts_segment_is_ok                   (GtsSegment *s);
#define             GTS_IS_EDGE                         (obj)
#define             GTS_EDGE                            (obj)
#define             GTS_EDGE_CLASS                      (klass)
                    GtsEdge;
GtsEdgeClass *      gts_edge_class                      (void);
GtsEdge *           gts_edge_new                        (GtsEdgeClass *klass,
                                                         GtsVertex *v1,
                                                         GtsVertex *v2);
#define             gts_edge_is_unattached              (s)
GtsFace *           gts_edge_has_parent_surface         (GtsEdge *e,
                                                         GtsSurface *surface);
GtsFace *           gts_edge_has_any_parent_surface     (GtsEdge *e);
GtsFace *           gts_edge_is_boundary                (GtsEdge *e,
                                                         GtsSurface *surface);
void                gts_edge_replace                    (GtsEdge *e,
                                                         GtsEdge *with);
GSList *            gts_edges_from_vertices             (GSList *vertices,
                                                         GtsSurface *parent);
guint               gts_edge_face_number                (GtsEdge *e,
                                                         GtsSurface *s);
gboolean            gts_edge_collapse_is_valid          (GtsEdge *e);
gboolean            gts_edge_collapse_creates_fold      (GtsEdge *e,
                                                         GtsVertex *v,
                                                         gdouble max);
GtsEdge *           gts_edge_is_duplicate               (GtsEdge *e);
GList *             gts_edges_merge                     (GList *edges);
gboolean            gts_edge_belongs_to_tetrahedron     (GtsEdge *e);
guint               gts_edge_is_contact                 (GtsEdge *e);
void                gts_edge_swap                       (GtsEdge *e,
                                                         GtsSurface *s);
gboolean            gts_edge_manifold_faces             (GtsEdge *e,
                                                         GtsSurface *s,
                                                         GtsFace **f1,
                                                         GtsFace **f2);
#define             GTS_IS_TRIANGLE                     (obj)
#define             GTS_TRIANGLE                        (obj)
#define             GTS_TRIANGLE_CLASS                  (klass)
                    GtsTriangle;
GtsTriangleClass *  gts_triangle_class                  (void);
void                gts_triangle_set                    (GtsTriangle *triangle,
                                                         GtsEdge *e1,
                                                         GtsEdge *e2,
                                                         GtsEdge *e3);
GtsTriangle *       gts_triangle_new                    (GtsTriangleClass *klass,
                                                         GtsEdge *e1,
                                                         GtsEdge *e2,
                                                         GtsEdge *e3);
#define             gts_triangle_vertex                 (t)
GtsVertex *         gts_triangle_vertex_opposite        (GtsTriangle *t,
                                                         GtsEdge *e);
GtsEdge *           gts_triangle_edge_opposite          (GtsTriangle *t,
                                                         GtsVertex *v);
gdouble             gts_triangles_angle                 (GtsTriangle *t1,
                                                         GtsTriangle *t2);
gboolean            gts_triangles_are_compatible        (GtsTriangle *t1,
                                                         GtsTriangle *t2,
                                                         GtsEdge *e);
gdouble             gts_triangle_area                   (GtsTriangle *t);
gdouble             gts_triangle_perimeter              (GtsTriangle *t);
gdouble             gts_triangle_quality                (GtsTriangle *t);
void                gts_triangle_normal                 (GtsTriangle *t,
                                                         gdouble *x,
                                                         gdouble *y,
                                                         gdouble *z);
gdouble             gts_triangle_orientation            (GtsTriangle *t);
void                gts_triangle_revert                 (GtsTriangle *t);
GSList *            gts_triangles_from_edges            (GSList *edges);
void                gts_triangle_vertices_edges         (GtsTriangle *t,
                                                         GtsEdge *e,
                                                         GtsVertex **v1,
                                                         GtsVertex **v2,
                                                         GtsVertex **v3,
                                                         GtsEdge **e1,
                                                         GtsEdge **e2,
                                                         GtsEdge **e3);
GtsTriangle *       gts_triangle_enclosing              (GtsTriangleClass *klass,
                                                         GSList *points,
                                                         gdouble scale);
guint               gts_triangle_neighbor_number        (GtsTriangle *t);
GSList *            gts_triangle_neighbors              (GtsTriangle *t);
GtsEdge *           gts_triangles_common_edge           (GtsTriangle *t1,
                                                         GtsTriangle *t2);
GtsTriangle *       gts_triangle_is_duplicate           (GtsTriangle *t);
GtsTriangle *       gts_triangle_use_edges              (GtsEdge *e1,
                                                         GtsEdge *e2,
                                                         GtsEdge *e3);
gboolean            gts_triangle_is_ok                  (GtsTriangle *t);
void                gts_triangle_vertices               (GtsTriangle *t,
                                                         GtsVertex **v1,
                                                         GtsVertex **v2,
                                                         GtsVertex **v3);
GtsPoint *          gts_triangle_circumcircle_center    (GtsTriangle *t,
                                                         GtsPointClass *point_class);
gboolean            gts_triangles_are_folded            (GSList *triangles,
                                                         GtsVertex *A,
                                                         GtsVertex *B,
                                                         gdouble max);
GtsObject *         gts_triangle_is_stabbed             (GtsTriangle *t,
                                                         GtsPoint *p,
                                                         gdouble *orientation);
void                gts_triangle_interpolate_height     (GtsTriangle *t,
                                                         GtsPoint *p);
#define             GTS_IS_FACE                         (obj)
#define             GTS_FACE                            (obj)
#define             GTS_FACE_CLASS                      (klass)
                    GtsFace;
GtsFaceClass *      gts_face_class                      (void);
GtsFace *           gts_face_new                        (GtsFaceClass *klass,
                                                         GtsEdge *e1,
                                                         GtsEdge *e2,
                                                         GtsEdge *e3);
gboolean            gts_face_has_parent_surface         (GtsFace *f,
                                                         GtsSurface *s);
GSList *            gts_faces_from_edges                (GSList *edges,
                                                         GtsSurface *s);
guint               gts_face_neighbor_number            (GtsFace *f,
                                                         GtsSurface *s);
GSList *            gts_face_neighbors                  (GtsFace *f,
                                                         GtsSurface *s);
void                gts_face_foreach_neighbor           (GtsFace *f,
                                                         GtsSurface *s,
                                                         GtsFunc func,
                                                         gpointer data);
gboolean            gts_face_is_compatible              (GtsFace *f,
                                                         GtsSurface *s);
#define             gts_vector_cross                    (C,A,B)
#define             gts_vector_init                     (v, p1, p2)
#define             gts_vector_scalar                   (v1, v2)
#define             gts_vector_norm                     (v)
#define             gts_vector_normalize                (v)
GtsMatrix *         gts_matrix_new                      (gdouble a00,
                                                         gdouble a01,
                                                         gdouble a02,
                                                         gdouble a03,
                                                         gdouble a10,
                                                         gdouble a11,
                                                         gdouble a12,
                                                         gdouble a13,
                                                         gdouble a20,
                                                         gdouble a21,
                                                         gdouble a22,
                                                         gdouble a23,
                                                         gdouble a30,
                                                         gdouble a31,
                                                         gdouble a32,
                                                         gdouble a33);
void                gts_matrix_assign                   (GtsMatrix *m,
                                                         gdouble a00,
                                                         gdouble a01,
                                                         gdouble a02,
                                                         gdouble a03,
                                                         gdouble a10,
                                                         gdouble a11,
                                                         gdouble a12,
                                                         gdouble a13,
                                                         gdouble a20,
                                                         gdouble a21,
                                                         gdouble a22,
                                                         gdouble a23,
                                                         gdouble a30,
                                                         gdouble a31,
                                                         gdouble a32,
                                                         gdouble a33);
GtsMatrix *         gts_matrix_projection               (GtsTriangle *t);
GtsMatrix *         gts_matrix_transpose                (GtsMatrix *m);
gdouble             gts_matrix_determinant              (GtsMatrix *m);
GtsMatrix *         gts_matrix_inverse                  (GtsMatrix *m);
GtsMatrix *         gts_matrix3_inverse                 (GtsMatrix *m);
void                gts_matrix_print                    (GtsMatrix *m,
                                                         FILE *fptr);
guint               gts_matrix_compatible_row           (GtsMatrix *A,
                                                         GtsVector b,
                                                         guint n,
                                                         GtsVector A1,
                                                         gdouble b1);
guint               gts_matrix_quadratic_optimization   (GtsMatrix *A,
                                                         GtsVector b,
                                                         guint n,
                                                         GtsMatrix *H,
                                                         GtsVector c);
GtsMatrix *         gts_matrix_product                  (GtsMatrix *m1,
                                                         GtsMatrix *m2);
GtsMatrix *         gts_matrix_zero                     (GtsMatrix *m);
GtsMatrix *         gts_matrix_identity                 (GtsMatrix *m);
GtsMatrix *         gts_matrix_scale                    (GtsMatrix *m,
                                                         GtsVector s);
GtsMatrix *         gts_matrix_translate                (GtsMatrix *m,
                                                         GtsVector t);
GtsMatrix *         gts_matrix_rotate                   (GtsMatrix *m,
                                                         GtsVector r,
                                                         gdouble angle);
void                gts_matrix_destroy                  (GtsMatrix *m);
void                gts_vector_print                    (GtsVector v,
                                                         FILE *fptr);
void                gts_vector4_print                   (GtsVector4 v,
                                                         FILE *fptr);
#define             gts_kdtree_destroy                  (tree)
GNode *             gts_kdtree_new                      (GPtrArray *points,
                                                         int (compareconst void *,const void *) ());
GSList *            gts_kdtree_range                    (GNode *tree,
                                                         GtsBBox *bbox,
                                                         int (compareconst void *,const void *) ());
void                (*GtsBBTreeTraverseFunc)            (GtsBBox *bb1,
                                                         GtsBBox *bb2,
                                                         gpointer data);
gdouble             (*GtsBBoxDistFunc)                  (GtsPoint *p,
                                                         gpointer bounded);
GtsPoint *          (*GtsBBoxClosestFunc)               (GtsPoint *p,
                                                         gpointer bounded);
#define             GTS_IS_BBOX                         (obj)
#define             GTS_BBOX                            (obj)
#define             GTS_BBOX_CLASS                      (klass)
                    GtsBBox;
GtsBBoxClass *      gts_bbox_class                      (void);
GtsBBox *           gts_bbox_new                        (GtsBBoxClass *klass,
                                                         gpointer bounded,
                                                         gdouble x1,
                                                         gdouble y1,
                                                         gdouble z1,
                                                         gdouble x2,
                                                         gdouble y2,
                                                         gdouble z2);
void                gts_bbox_set                        (GtsBBox *bbox,
                                                         gpointer bounded,
                                                         gdouble x1,
                                                         gdouble y1,
                                                         gdouble z1,
                                                         gdouble x2,
                                                         gdouble y2,
                                                         gdouble z2);
GtsBBox *           gts_bbox_segment                    (GtsBBoxClass *klass,
                                                         GtsSegment *s);
GtsBBox *           gts_bbox_triangle                   (GtsBBoxClass *klass,
                                                         GtsTriangle *t);
GtsBBox *           gts_bbox_surface                    (GtsBBoxClass *klass,
                                                         GtsSurface *surface);
GtsBBox *           gts_bbox_bboxes                     (GtsBBoxClass *klass,
                                                         GSList *bboxes);
GtsBBox *           gts_bbox_points                     (GtsBBoxClass *klass,
                                                         GSList *points);
#define             gts_bbox_point_is_inside            (bbox, p)
gboolean            gts_bboxes_are_overlapping          (GtsBBox *bb1,
                                                         GtsBBox *bb2);
void                gts_bbox_draw                       (GtsBBox *bb,
                                                         FILE *fptr);
gdouble             gts_bbox_diagonal2                  (GtsBBox *bb);
void                gts_bbox_point_distance2            (GtsBBox *bb,
                                                         GtsPoint *p,
                                                         gdouble *min,
                                                         gdouble *max);
gboolean            gts_bbox_is_stabbed                 (GtsBBox *bb,
                                                         GtsPoint *p);
gboolean            gts_bbox_overlaps_triangle          (GtsBBox *bb,
                                                         GtsTriangle *t);
gboolean            gts_bbox_overlaps_segment           (GtsBBox *bb,
                                                         GtsSegment *s);
GNode *             gts_bb_tree_new                     (GSList *bboxes);
GNode *             gts_bb_tree_surface                 (GtsSurface *s);
GSList *            gts_bb_tree_stabbed                 (GNode *tree,
                                                         GtsPoint *p);
GSList *            gts_bb_tree_overlap                 (GNode *tree,
                                                         GtsBBox *bbox);
gboolean            gts_bb_tree_is_overlapping          (GNode *tree,
                                                         GtsBBox *bbox);
void                gts_bb_tree_traverse_overlapping    (GNode *tree1,
                                                         GNode *tree2,
                                                         GtsBBTreeTraverseFunc func,
                                                         gpointer data);
void                gts_bb_tree_draw                    (GNode *tree,
                                                         guint depth,
                                                         FILE *fptr);
GSList *            gts_bb_tree_point_closest_bboxes    (GNode *tree,
                                                         GtsPoint *p);
gdouble             gts_bb_tree_point_distance          (GNode *tree,
                                                         GtsPoint *p,
                                                         GtsBBoxDistFunc distance,
                                                         GtsBBox **bbox);
GtsPoint *          gts_bb_tree_point_closest           (GNode *tree,
                                                         GtsPoint *p,
                                                         GtsBBoxClosestFunc closest,
                                                         gdouble *distance);
void                gts_bb_tree_segment_distance        (GNode *tree,
                                                         GtsSegment *s,
                                                         GtsBBoxDistFunc distance,
                                                         gdouble delta,
                                                         GtsRange *range);
void                gts_bb_tree_triangle_distance       (GNode *tree,
                                                         GtsTriangle *t,
                                                         GtsBBoxDistFunc distance,
                                                         gdouble delta,
                                                         GtsRange *range);
void                gts_bb_tree_surface_distance        (GNode *tree,
                                                         GtsSurface *s,
                                                         GtsBBoxDistFunc distance,
                                                         gdouble delta,
                                                         GtsRange *range);
void                gts_bb_tree_surface_boundary_distance
                                                        (GNode *tree,
                                                         GtsSurface *s,
                                                         GtsBBoxDistFunc distance,
                                                         gdouble delta,
                                                         GtsRange *range);
void                gts_bb_tree_destroy                 (GNode *tree,
                                                         gboolean free_leaves);
                    GtsSurfaceStats;
                    GtsSurfaceQualityStats;
GtsVertex *         (*GtsRefineFunc)                    (GtsEdge *e,
                                                         GtsVertexClass *klass,
                                                         gpointer data);
GtsVertex *         (*GtsCoarsenFunc)                   (GtsEdge *e,
                                                         GtsVertexClass *klass,
                                                         gpointer data);
gboolean            (*GtsStopFunc)                      (gdouble cost,
                                                         guint nedge,
                                                         gpointer data);
                    GtsSurface;
#define             GTS_IS_SURFACE                      (obj)
#define             GTS_SURFACE                         (obj)
#define             GTS_SURFACE_CLASS                   (klass)
GtsSurfaceClass *   gts_surface_class                   (void);
GtsSurface *        gts_surface_new                     (GtsSurfaceClass *klass,
                                                         GtsFaceClass *face_class,
                                                         GtsEdgeClass *edge_class,
                                                         GtsVertexClass *vertex_class);
void                gts_surface_add_face                (GtsSurface *s,
                                                         GtsFace *f);
void                gts_surface_remove_face             (GtsSurface *s,
                                                         GtsFace *f);
guint               gts_surface_read                    (GtsSurface *surface,
                                                         GtsFile *f);
gdouble             gts_surface_area                    (GtsSurface *s);
void                gts_surface_stats                   (GtsSurface *s,
                                                         GtsSurfaceStats *stats);
void                gts_surface_quality_stats           (GtsSurface *s,
                                                         GtsSurfaceQualityStats *stats);
void                gts_surface_print_stats             (GtsSurface *s,
                                                         FILE *fptr);
void                gts_surface_write                   (GtsSurface *s,
                                                         FILE *fptr);
void                gts_surface_write_oogl              (GtsSurface *s,
                                                         FILE *fptr);
void                gts_surface_write_vtk               (GtsSurface *s,
                                                         FILE *fptr);
void                gts_surface_write_oogl_boundary     (GtsSurface *s,
                                                         FILE *fptr);
void                gts_surface_foreach_vertex          (GtsSurface *s,
                                                         GtsFunc func,
                                                         gpointer data);
void                gts_surface_foreach_edge            (GtsSurface *s,
                                                         GtsFunc func,
                                                         gpointer data);
void                gts_surface_foreach_face            (GtsSurface *s,
                                                         GtsFunc func,
                                                         gpointer data);
guint               gts_surface_foreach_face_remove     (GtsSurface *s,
                                                         GtsFunc func,
                                                         gpointer data);
                    GtsSurfaceTraverse;
GtsSurfaceTraverse * gts_surface_traverse_new           (GtsSurface *s,
                                                         GtsFace *f);
GtsFace *           gts_surface_traverse_next           (GtsSurfaceTraverse *t,
                                                         guint *level);
void                gts_surface_traverse_destroy        (GtsSurfaceTraverse *t);
void                gts_surface_refine                  (GtsSurface *surface,
                                                         GtsKeyFunc cost_func,
                                                         gpointer cost_data,
                                                         GtsRefineFunc refine_func,
                                                         gpointer refine_data,
                                                         GtsStopFunc stop_func,
                                                         gpointer stop_data);
void                gts_surface_coarsen                 (GtsSurface *surface,
                                                         GtsKeyFunc cost_func,
                                                         gpointer cost_data,
                                                         GtsCoarsenFunc coarsen_func,
                                                         gpointer coarsen_data,
                                                         GtsStopFunc stop_func,
                                                         gpointer stop_data,
                                                         gdouble minangle);
gboolean            gts_coarsen_stop_number             (gdouble cost,
                                                         guint nedge,
                                                         guint *min_number);
gboolean            gts_coarsen_stop_cost               (gdouble cost,
                                                         guint nedge,
                                                         gdouble *max_cost);
void                gts_surface_tessellate              (GtsSurface *s,
                                                         GtsRefineFunc refine_func,
                                                         gpointer refine_data);
GtsSurface *        gts_surface_generate_sphere         (GtsSurface *s,
                                                         guint geodesation_order);
GtsSurface *        gts_surface_copy                    (GtsSurface *s1,
                                                         GtsSurface *s2);
void                gts_surface_merge                   (GtsSurface *s,
                                                         GtsSurface *with);
gboolean            gts_surface_is_manifold             (GtsSurface *s);
gboolean            gts_surface_is_closed               (GtsSurface *s);
gboolean            gts_surface_is_orientable           (GtsSurface *s);
gdouble             gts_surface_volume                  (GtsSurface *s);
gdouble             gts_surface_center_of_mass          (GtsSurface *s,
                                                         GtsVector cm);
gdouble             gts_surface_center_of_area          (GtsSurface *s,
                                                         GtsVector cm);
guint               gts_surface_vertex_number           (GtsSurface *s);
guint               gts_surface_edge_number             (GtsSurface *s);
guint               gts_surface_face_number             (GtsSurface *s);
void                gts_surface_distance                (GtsSurface *s1,
                                                         GtsSurface *s2,
                                                         gdouble delta,
                                                         GtsRange *face_range,
                                                         GtsRange *boundary_range);
GSList *            gts_surface_boundary                (GtsSurface *surface);
GSList *            gts_surface_split                   (GtsSurface *s);
gboolean            gts_vertex_mean_curvature_normal    (GtsVertex *v,
                                                         GtsSurface *s,
                                                         GtsVector Kh);
gboolean            gts_vertex_gaussian_curvature       (GtsVertex *v,
                                                         GtsSurface *s,
                                                         gdouble *Kg);
void                gts_vertex_principal_curvatures     (gdouble Kh,
                                                         gdouble Kg,
                                                         gdouble *K1,
                                                         gdouble *K2);
void                gts_vertex_principal_directions     (GtsVertex *v,
                                                         GtsSurface *s,
                                                         GtsVector Kh,
                                                         gdouble Kg,
                                                         GtsVector e1,
                                                         GtsVector e2);
                    GtsVolumeOptimizedParams;
GtsVertex *         gts_volume_optimized_vertex         (GtsEdge *edge,
                                                         GtsVertexClass *klass,
                                                         GtsVolumeOptimizedParams *params);
gdouble             gts_volume_optimized_cost           (GtsEdge *e,
                                                         GtsVolumeOptimizedParams *params);
GSList *            gts_surface_intersection            (GtsSurface *s1,
                                                         GtsSurface *s2,
                                                         GNode *faces_tree1,
                                                         GNode *faces_tree2);
enum                GtsBooleanOperation;
#define             GTS_IS_SURFACE_INTER                (obj)
#define             GTS_SURFACE_INTER                   (obj)
#define             GTS_SURFACE_INTER_CLASS             (klass)
                    GtsSurfaceInter;
GtsSurfaceInterClass * gts_surface_inter_class          (void);
GtsSurfaceInter *   gts_surface_inter_new               (GtsSurfaceInterClass *klass,
                                                         GtsSurface *s1,
                                                         GtsSurface *s2,
                                                         GNode *faces_tree1,
                                                         GNode *faces_tree2,
                                                         gboolean is_open1,
                                                         gboolean is_open2);
gboolean            gts_surface_inter_check             (GtsSurfaceInter *si,
                                                         gboolean *closed);
void                gts_surface_inter_boolean           (GtsSurfaceInter *si,
                                                         GtsSurface *surface,
                                                         GtsBooleanOperation op);
gboolean            gts_surface_foreach_intersecting_face
                                                        (GtsSurface *s,
                                                         GtsBBTreeTraverseFunc func,
                                                         gpointer data);
GtsSurface *        gts_surface_is_self_intersecting    (GtsSurface *s);
                    GtsHeap;
GtsHeap *           gts_heap_new                        (GCompareFunc compare_func);
void                gts_heap_insert                     (GtsHeap *heap,
                                                         gpointer p);
gpointer            gts_heap_remove_top                 (GtsHeap *heap);
gpointer            gts_heap_top                        (GtsHeap *heap);
void                gts_heap_thaw                       (GtsHeap *heap);
void                gts_heap_foreach                    (GtsHeap *heap,
                                                         GFunc func,
                                                         gpointer user_data);
void                gts_heap_freeze                     (GtsHeap *heap);
guint               gts_heap_size                       (GtsHeap *heap);
void                gts_heap_destroy                    (GtsHeap *heap);
                    GtsEHeap;
                    GtsEHeapPair;
GtsEHeap *          gts_eheap_new                       (GtsKeyFunc key_func,
                                                         gpointer data);
GtsEHeapPair *      gts_eheap_insert                    (GtsEHeap *heap,
                                                         gpointer p);
GtsEHeapPair *      gts_eheap_insert_with_key           (GtsEHeap *heap,
                                                         gpointer p,
                                                         gdouble key);
gpointer            gts_eheap_remove_top                (GtsEHeap *heap,
                                                         gdouble *key);
gpointer            gts_eheap_top                       (GtsEHeap *heap,
                                                         gdouble *key);
void                gts_eheap_thaw                      (GtsEHeap *heap);
void                gts_eheap_foreach                   (GtsEHeap *heap,
                                                         GFunc func,
                                                         gpointer data);
gpointer            gts_eheap_remove                    (GtsEHeap *heap,
                                                         GtsEHeapPair *p);
void                gts_eheap_decrease_key              (GtsEHeap *heap,
                                                         GtsEHeapPair *p,
                                                         gdouble new_key);
void                gts_eheap_freeze                    (GtsEHeap *heap);
guint               gts_eheap_size                      (GtsEHeap *heap);
void                gts_eheap_update                    (GtsEHeap *heap);
gdouble             gts_eheap_key                       (GtsEHeap *heap,
                                                         gpointer p);
void                gts_eheap_randomized                (GtsEHeap *heap,
                                                         gboolean randomized);
void                gts_eheap_destroy                   (GtsEHeap *heap);
                    GtsFifo;
GtsFifo *           gts_fifo_new                        (void);
void                gts_fifo_write                      (GtsFifo *fifo,
                                                         FILE *fp);
void                gts_fifo_push                       (GtsFifo *fifo,
                                                         gpointer data);
gpointer            gts_fifo_pop                        (GtsFifo *fifo);
gpointer            gts_fifo_top                        (GtsFifo *fifo);
guint               gts_fifo_size                       (GtsFifo *fifo);
gboolean            gts_fifo_is_empty                   (GtsFifo *fifo);
void                gts_fifo_foreach                    (GtsFifo *fifo,
                                                         GtsFunc func,
                                                         gpointer data);
void                gts_fifo_reverse                    (GtsFifo *fifo);
void                gts_fifo_destroy                    (GtsFifo *fifo);
                    GtsSplitCFace;
                    GtsSplit;
#define             GTS_IS_SPLIT                        (obj)
#define             GTS_SPLIT                           (obj)
#define             GTS_SPLIT_CLASS                     (klass)
#define             GTS_SPLIT_V1                        (vs)
#define             GTS_SPLIT_V2                        (vs)
GtsSplitClass *     gts_split_class                     (void);
GtsSplit *          gts_split_new                       (GtsSplitClass *klass,
                                                         GtsVertex *v,
                                                         GtsObject *o1,
                                                         GtsObject *o2);
void                gts_split_collapse                  (GtsSplit *vs,
                                                         GtsEdgeClass *klass,
                                                         GtsEHeap *heap);
void                gts_split_expand                    (GtsSplit *vs,
                                                         GtsSurface *s,
                                                         GtsEdgeClass *klass);
gboolean            (*GtsSplitTraverseFunc)             (GtsSplit *vs,
                                                         gpointer data);
void                gts_split_traverse                  (GtsSplit *root,
                                                         GTraverseType order,
                                                         gint depth,
                                                         GtsSplitTraverseFunc func,
                                                         gpointer data);
guint               gts_split_height                    (GtsSplit *root);
                    GtsPSurface;
#define             GTS_IS_PSURFACE                     (obj)
#define             GTS_PSURFACE                        (obj)
#define             GTS_PSURFACE_CLASS                  (klass)
#define             GTS_PSURFACE_IS_CLOSED              (ps)
GtsPSurfaceClass *  gts_psurface_class                  (void);
GtsPSurface *       gts_psurface_new                    (GtsPSurfaceClass *klass,
                                                         GtsSurface *surface,
                                                         GtsSplitClass *split_class,
                                                         GtsKeyFunc cost_func,
                                                         gpointer cost_data,
                                                         GtsCoarsenFunc coarsen_func,
                                                         gpointer coarsen_data,
                                                         GtsStopFunc stop_func,
                                                         gpointer stop_data,
                                                         gdouble minangle);
GtsSplit *          gts_psurface_add_vertex             (GtsPSurface *ps);
GtsSplit *          gts_psurface_remove_vertex          (GtsPSurface *ps);
guint               gts_psurface_max_vertex_number      (GtsPSurface *ps);
guint               gts_psurface_min_vertex_number      (GtsPSurface *ps);
void                gts_psurface_set_vertex_number      (GtsPSurface *ps,
                                                         guint n);
guint               gts_psurface_get_vertex_number      (GtsPSurface *ps);
void                gts_psurface_write                  (GtsPSurface *ps,
                                                         FILE *fptr);
GtsPSurface *       gts_psurface_open                   (GtsPSurfaceClass *klass,
                                                         GtsSurface *s,
                                                         GtsSplitClass *split_class,
                                                         GtsFile *f);
GtsSplit *          gts_psurface_read_vertex            (GtsPSurface *ps,
                                                         GtsFile *fp);
void                gts_psurface_close                  (GtsPSurface *ps);
void                gts_psurface_foreach_vertex         (GtsPSurface *ps,
                                                         GtsFunc func,
                                                         gpointer data);
                    GtsHSplit;
#define             GTS_IS_HSPLIT                       (obj)
#define             GTS_HSPLIT                          (obj)
#define             GTS_HSPLIT_CLASS                    (klass)
GtsHSplitClass *    gts_hsplit_class                    (void);
GtsHSplit *         gts_hsplit_new                      (GtsHSplitClass *klass,
                                                         GtsSplit *vs);
void                gts_hsplit_collapse                 (GtsHSplit *hs,
                                                         GtsHSurface *hsurface);
void                gts_hsplit_expand                   (GtsHSplit *hs,
                                                         GtsHSurface *hsurface);
void                gts_hsplit_force_expand             (GtsHSplit *hs,
                                                         GtsHSurface *hsurface);
                    GtsHSurface;
#define             GTS_IS_HSURFACE                     (obj)
#define             GTS_HSURFACE                        (obj)
#define             GTS_HSURFACE_CLASS                  (klass)
GtsHSurfaceClass *  gts_hsurface_class                  (void);
GtsHSurface *       gts_hsurface_new                    (GtsHSurfaceClass *klass,
                                                         GtsHSplitClass *hsplit_class,
                                                         GtsPSurface *psurface,
                                                         GtsKeyFunc expand_key,
                                                         gpointer expand_data,
                                                         GtsKeyFunc collapse_key,
                                                         gpointer collapse_data);
void                gts_hsurface_traverse               (GtsHSurface *hsurface,
                                                         GTraverseType order,
                                                         gint depth,
                                                         GtsSplitTraverseFunc func,
                                                         gpointer data);
void                gts_hsurface_foreach                (GtsHSurface *hsurface,
                                                         GTraverseType order,
                                                         GtsFunc func,
                                                         gpointer data);
guint               gts_hsurface_height                 (GtsHSurface *hsurface);
#define             GTS_IS_CONSTRAINT                   (obj)
#define             GTS_CONSTRAINT                      (obj)
#define             GTS_CONSTRAINT_CLASS                (klass)
                    GtsConstraint;
                    GtsConstraintClass;
GtsConstraintClass * gts_constraint_class               (void);
GtsFace *           gts_point_locate                    (GtsPoint *p,
                                                         GtsSurface *surface,
                                                         GtsFace *guess);
GtsVertex *         gts_delaunay_add_vertex_to_face     (GtsSurface *surface,
                                                         GtsVertex *v,
                                                         GtsFace *f);
GtsVertex *         gts_delaunay_add_vertex             (GtsSurface *surface,
                                                         GtsVertex *v,
                                                         GtsFace *guess);
void                gts_delaunay_remove_vertex          (GtsSurface *surface,
                                                         GtsVertex *v);
GtsFace *           gts_delaunay_check                  (GtsSurface *surface);
GSList *            gts_delaunay_add_constraint         (GtsSurface *surface,
                                                         GtsConstraint *c);
void                gts_delaunay_remove_hull            (GtsSurface *surface);
                    GtsListFace;
#define             GTS_LIST_FACE                       (obj)
#define             GTS_IS_LIST_FACE                    (obj)
GtsFaceClass *      gts_list_face_class                 (void);
gboolean            (*GtsEncroachFunc)                  (GtsVertex *v,
                                                         GtsEdge *e,
                                                         GtsSurface *s,
                                                         gpointer data);
gboolean            gts_vertex_encroaches_edge          (GtsVertex *v,
                                                         GtsEdge *e);
GtsVertex *         gts_edge_is_encroached              (GtsEdge *e,
                                                         GtsSurface *s,
                                                         GtsEncroachFunc encroaches,
                                                         gpointer data);
guint               gts_delaunay_conform                (GtsSurface *surface,
                                                         gint steiner_max,
                                                         GtsEncroachFunc encroaches,
                                                         gpointer data);
guint               gts_delaunay_refine                 (GtsSurface *surface,
                                                         gint steiner_max,
                                                         GtsEncroachFunc encroaches,
                                                         gpointer encroach_data,
                                                         GtsKeyFunc cost,
                                                         gpointer cost_data);
                    GtsGridPlane;
                    GtsIsoSlice;
                    GtsCartesianGrid;
void                (*GtsIsoCartesianFunc)              (gdouble **a,
                                                         GtsCartesianGrid g,
                                                         guint i,
                                                         gpointer data);
GtsGridPlane *      gts_grid_plane_new                  (guint nx,
                                                         guint ny);
void                gts_grid_plane_destroy              (GtsGridPlane *g);
GtsIsoSlice *       gts_iso_slice_new                   (guint nx,
                                                         guint ny);
void                gts_iso_slice_fill                  (GtsIsoSlice *slice,
                                                         GtsGridPlane *plane1,
                                                         GtsGridPlane *plane2,
                                                         gdouble **f1,
                                                         gdouble **f2,
                                                         gdouble iso,
                                                         GtsVertexClass *klass);
void                gts_iso_slice_fill_cartesian        (GtsIsoSlice *slice,
                                                         GtsCartesianGrid g,
                                                         gdouble **f1,
                                                         gdouble **f2,
                                                         gdouble iso,
                                                         GtsVertexClass *klass);
void                gts_iso_slice_destroy               (GtsIsoSlice *slice);
void                gts_isosurface_slice                (GtsIsoSlice *slice1,
                                                         GtsIsoSlice *slice2,
                                                         GtsSurface *surface);
void                gts_isosurface_cartesian            (GtsSurface *surface,
                                                         GtsCartesianGrid g,
                                                         GtsIsoCartesianFunc f,
                                                         gpointer data,
                                                         gdouble iso);
void                gts_isosurface_tetra                (GtsSurface *surface,
                                                         GtsCartesianGrid g,
                                                         GtsIsoCartesianFunc f,
                                                         gpointer data,
                                                         gdouble iso);
void                gts_isosurface_tetra_bcl            (GtsSurface *surface,
                                                         GtsCartesianGrid g,
                                                         GtsIsoCartesianFunc f,
                                                         gpointer data,
                                                         gdouble iso);
void                gts_isosurface_tetra_bounded        (GtsSurface *surface,
                                                         GtsCartesianGrid g,
                                                         GtsIsoCartesianFunc f,
                                                         gpointer data,
                                                         gdouble iso);
#define             GTS_NAME_LENGTH
#define             GTS_NVERTEX                         (obj)
#define             GTS_NVERTEX_CLASS                   (klass)
#define             GTS_IS_NVERTEX                      (obj)
                    GtsNVertex;
GtsNVertexClass *   gts_nvertex_class                   (void);
#define             GTS_NEDGE                           (obj)
#define             GTS_NEDGE_CLASS                     (klass)
#define             GTS_IS_NEDGE                        (obj)
                    GtsNEdge;
GtsNEdgeClass *     gts_nedge_class                     (void);
#define             GTS_NFACE                           (obj)
#define             GTS_NFACE_CLASS                     (klass)
#define             GTS_IS_NFACE                        (obj)
                    GtsNFace;
GtsNFaceClass *     gts_nface_class                     (void);
#define             GTS_CLUSTER                         (obj)
#define             GTS_CLUSTER_CLASS                   (klass)
#define             GTS_IS_CLUSTER                      (obj)
                    GtsClusterId;
                    GtsCluster;
GtsClusterClass *   gts_cluster_class                   (void);
GtsCluster *        gts_cluster_new                     (GtsClusterClass *klass,
                                                         GtsClusterId id,
                                                         GtsVertexClass *vklass);
void                gts_cluster_add                     (GtsCluster *c,
                                                         GtsPoint *p,
                                                         gpointer data);
void                gts_cluster_update                  (GtsCluster *c);
#define             GTS_CLUSTER_GRID                    (obj)
#define             GTS_CLUSTER_GRID_CLASS              (klass)
#define             GTS_IS_CLUSTER_GRID                 (obj)
                    GtsClusterGrid;
GtsClusterGridClass * gts_cluster_grid_class            (void);
GtsClusterGrid *    gts_cluster_grid_new                (GtsClusterGridClass *klass,
                                                         GtsClusterClass *cluster_class,
                                                         GtsSurface *s,
                                                         GtsBBox *bbox,
                                                         gdouble delta);
void                gts_cluster_grid_add_triangle       (GtsClusterGrid *cluster_grid,
                                                         GtsPoint *p1,
                                                         GtsPoint *p2,
                                                         GtsPoint *p3,
                                                         gpointer data);
GtsRange            gts_cluster_grid_update             (GtsClusterGrid *cluster_grid);
GSList *            gts_surface_strip                   (GtsSurface *s);
                    GtsContainee;
#define             GTS_CONTAINEE                       (obj)
#define             GTS_CONTAINEE_CLASS                 (klass)
#define             GTS_IS_CONTAINEE                    (obj)
GtsContaineeClass * gts_containee_class                 (void);
GtsContainee *      gts_containee_new                   (GtsContaineeClass *klass);
gboolean            gts_containee_is_contained          (GtsContainee *item,
                                                         GtsContainer *c);
void                gts_containee_replace               (GtsContainee *item,
                                                         GtsContainee *with);
                    GtsSListContainee;
#define             GTS_SLIST_CONTAINEE                 (obj)
#define             GTS_SLIST_CONTAINEE_CLASS           (klass)
#define             GTS_IS_SLIST_CONTAINEE              (obj)
GtsSListContaineeClass * gts_slist_containee_class      (void);
                    GtsContainer;
#define             GTS_CONTAINER                       (obj)
#define             GTS_CONTAINER_CLASS                 (klass)
#define             GTS_IS_CONTAINER                    (obj)
GtsContainerClass * gts_container_class                 (void);
GtsContainer *      gts_container_new                   (GtsContainerClass *klass);
void                gts_container_add                   (GtsContainer *c,
                                                         GtsContainee *item);
void                gts_container_remove                (GtsContainer *c,
                                                         GtsContainee *item);
void                gts_container_foreach               (GtsContainer *c,
                                                         GtsFunc func,
                                                         gpointer data);
guint               gts_container_size                  (GtsContainer *c);
                    GtsHashContainer;
#define             GTS_HASH_CONTAINER                  (obj)
#define             GTS_HASH_CONTAINER_CLASS            (klass)
#define             GTS_IS_HASH_CONTAINER               (obj)
GtsHashContainerClass * gts_hash_container_class        (void);
                    GtsSListContainer;
#define             GTS_SLIST_CONTAINER                 (obj)
#define             GTS_SLIST_CONTAINER_CLASS           (klass)
#define             GTS_IS_SLIST_CONTAINER              (obj)
GtsSListContainerClass * gts_slist_container_class      (void);
                    GtsGNode;
#define             GTS_GNODE                           (obj)
#define             GTS_GNODE_CLASS                     (klass)
#define             GTS_IS_GNODE                        (obj)
#define             GTS_GNODE_NEIGHBOR                  (n,e)
GtsGNodeClass *     gts_gnode_class                     (void);
GtsGNode *          gts_gnode_new                       (GtsGNodeClass *klass);
void                gts_gnode_foreach_neighbor          (GtsGNode *n,
                                                         GtsGraph *g,
                                                         GtsFunc func,
                                                         gpointer data);
void                gts_gnode_foreach_edge              (GtsGNode *n,
                                                         GtsGraph *g,
                                                         GtsFunc func,
                                                         gpointer data);
guint               gts_gnode_degree                    (GtsGNode *n,
                                                         GtsGraph *g);
gfloat              gts_gnode_move_cost                 (GtsGNode *n,
                                                         GtsGraph *src,
                                                         GtsGraph *dst);
gfloat              gts_gnode_weight                    (GtsGNode *n);
                    GtsNGNode;
#define             GTS_NGNODE                          (obj)
#define             GTS_NGNODE_CLASS                    (klass)
#define             GTS_IS_NGNODE                       (obj)
GtsNGNodeClass *    gts_ngnode_class                    (void);
GtsNGNode *         gts_ngnode_new                      (GtsNGNodeClass *klass,
                                                         guint id);
                    GtsWGNode;
#define             GTS_WGNODE                          (obj)
#define             GTS_WGNODE_CLASS                    (klass)
#define             GTS_IS_WGNODE                       (obj)
GtsWGNodeClass *    gts_wgnode_class                    (void);
GtsWGNode *         gts_wgnode_new                      (GtsWGNodeClass *klass,
                                                         gfloat weight);
                    GtsPNode;
#define             GTS_PNODE                           (obj)
#define             GTS_PNODE_CLASS                     (klass)
#define             GTS_IS_PNODE                        (obj)
GtsPNodeClass *     gts_pnode_class                     (void);
GtsPNode *          gts_pnode_new                       (GtsPNodeClass *klass,
                                                         gpointer data);
                    GtsFNode;
#define             GTS_FNODE                           (obj)
#define             GTS_FNODE_CLASS                     (klass)
#define             GTS_IS_FNODE                        (obj)
GtsFNodeClass *     gts_fnode_class                     (void);
GtsFNode *          gts_fnode_new                       (GtsFNodeClass *klass,
                                                         GtsFace *f);
                    GtsGEdge;
#define             GTS_GEDGE                           (obj)
#define             GTS_GEDGE_CLASS                     (klass)
#define             GTS_IS_GEDGE                        (obj)
GtsGEdgeClass *     gts_gedge_class                     (void);
GtsGEdge *          gts_gedge_new                       (GtsGEdgeClass *klass,
                                                         GtsGNode *n1,
                                                         GtsGNode *n2);
gfloat              gts_gedge_weight                    (GtsGEdge *e);
#define             gts_gedge_connects                  (e, a1, a2)
                    GtsPGEdge;
#define             GTS_PGEDGE                          (obj)
#define             GTS_PGEDGE_CLASS                    (klass)
#define             GTS_IS_PGEDGE                       (obj)
GtsPGEdgeClass *    gts_pgedge_class                    (void);
GtsPGEdge *         gts_pgedge_new                      (GtsPGEdgeClass *klass,
                                                         GtsGNode *n1,
                                                         GtsGNode *n2,
                                                         gpointer data);
                    GtsWGEdge;
#define             GTS_WGEDGE                          (obj)
#define             GTS_WGEDGE_CLASS                    (klass)
#define             GTS_IS_WGEDGE                       (obj)
GtsWGEdgeClass *    gts_wgedge_class                    (void);
GtsWGEdge *         gts_wgedge_new                      (GtsWGEdgeClass *klass,
                                                         GtsGNode *n1,
                                                         GtsGNode *n2,
                                                         gfloat weight);
                    GtsGraph;
#define             GTS_GRAPH                           (obj)
#define             GTS_GRAPH_CLASS                     (klass)
#define             GTS_IS_GRAPH                        (obj)
GtsGraphClass *     gts_graph_class                     (void);
GtsGraph *          gts_graph_new                       (GtsGraphClass *klass,
                                                         GtsGNodeClass *node_class,
                                                         GtsGEdgeClass *edge_class);
void                gts_graph_print_stats               (GtsGraph *g,
                                                         FILE *fp);
                    GtsGraphTraverse;
enum                GtsTraverseType;
GtsGraphTraverse *  gts_graph_traverse_new              (GtsGraph *g,
                                                         GtsGNode *n,
                                                         GtsTraverseType type,
                                                         gboolean reinit);
GtsGNode *          gts_graph_traverse_next             (GtsGraphTraverse *t);
GtsGNode *          gts_graph_traverse_what_next        (GtsGraphTraverse *t);
void                gts_graph_traverse_destroy          (GtsGraphTraverse *t);
void                gts_graph_foreach_edge              (GtsGraph *g,
                                                         GtsFunc func,
                                                         gpointer data);
gfloat              gts_graph_weight                    (GtsGraph *g);
guint               gts_graph_distance_sum              (GtsGraph *g,
                                                         GtsGNode *center);
GtsGNode *          gts_graph_farthest                  (GtsGraph *g,
                                                         GSList *gnodes);
guint               gts_graph_edges_cut                 (GtsGraph *g);
gfloat              gts_graph_edges_cut_weight          (GtsGraph *g);
void                gts_graph_write                     (GtsGraph *g,
                                                         FILE *fp);
void                gts_graph_write_dot                 (GtsGraph *g,
                                                         FILE *fp);
GtsGraph *          gts_graph_read                      (GtsFile *fp);
guint               gts_graph_read_jostle               (GtsGraph *g,
                                                         GtsFile *fp);
                    GtsWGraph;
#define             GTS_WGRAPH                          (obj)
#define             GTS_WGRAPH_CLASS                    (klass)
#define             GTS_IS_WGRAPH                       (obj)
GtsWGraphClass *    gts_wgraph_class                    (void);
gfloat              gts_wgraph_weight_max               (GtsWGraph *wg);
GtsGraph *          gts_surface_graph_new               (GtsGraphClass *klass,
                                                         GtsSurface *s);
GtsSurface *        gts_surface_graph_surface           (GtsGraph *surface_graph,
                                                         GtsSurface *s);
GtsGraph *          gts_segments_graph_new              (GtsGraphClass *klass,
                                                         GSList *segments);
                    GtsGNodeSplit;
#define             GTS_GNODE_SPLIT                     (obj)
#define             GTS_GNODE_SPLIT_CLASS               (klass)
#define             GTS_IS_GNODE_SPLIT                  (obj)
#define             GTS_GNODE_SPLIT_N1                  (ns)
#define             GTS_GNODE_SPLIT_N2                  (ns)
GtsGNodeSplitClass * gts_gnode_split_class              (void);
GtsGNodeSplit *     gts_gnode_split_new                 (GtsGNodeSplitClass *klass,
                                                         GtsGNode *n,
                                                         GtsObject *n1,
                                                         GtsObject *n2);
void                gts_gnode_split_collapse            (GtsGNodeSplit *ns,
                                                         GtsGraph *g,
                                                         GtsWGEdgeClass *klass);
void                gts_gnode_split_expand              (GtsGNodeSplit *ns,
                                                         GtsGraph *g);
                    GtsPGraph;
#define             GTS_PGRAPH                          (obj)
#define             GTS_PGRAPH_CLASS                    (klass)
#define             GTS_IS_PGRAPH                       (obj)
GtsPGraphClass *    gts_pgraph_class                    (void);
GtsPGraph *         gts_pgraph_new                      (GtsPGraphClass *klass,
                                                         GtsGraph *g,
                                                         GtsGNodeSplitClass *split_class,
                                                         GtsWGNodeClass *node_class,
                                                         GtsWGEdgeClass *edge_class,
                                                         guint min);
GtsGNodeSplit *     gts_pgraph_add_node                 (GtsPGraph *pg);
GtsGNodeSplit *     gts_pgraph_remove_node              (GtsPGraph *pg);
void                gts_pgraph_set_node_number          (GtsPGraph *pg,
                                                         guint n);
guint               gts_pgraph_get_node_number          (GtsPGraph *pg);
guint               gts_pgraph_min_node_number          (GtsPGraph *pg);
guint               gts_pgraph_max_node_number          (GtsPGraph *pg);
void                gts_pgraph_foreach_node             (GtsPGraph *pg,
                                                         GtsFunc func,
                                                         gpointer data);
gboolean            gts_pgraph_down                     (GtsPGraph *pg,
                                                         GtsFunc func,
                                                         gpointer data);
GSList *            gts_graph_bubble_partition          (GtsGraph *g,
                                                         guint np,
                                                         guint niter,
                                                         GtsFunc step_info,
                                                         gpointer data);
guint               gts_graph_partition_edges_cut       (GSList *partition);
gfloat              gts_graph_partition_edges_cut_weight
                                                        (GSList *partition);
void                gts_graph_partition_print_stats     (GSList *partition,
                                                         FILE *fp);
gfloat              gts_graph_partition_balance         (GSList *partition);
GSList *            gts_graph_partition_clone           (GSList *partition);
GSList *            gts_graph_recursive_bisection       (GtsWGraph *wg,
                                                         guint n,
                                                         guint ntry,
                                                         guint mmax,
                                                         guint nmin,
                                                         gfloat imbalance);
void                gts_graph_partition_destroy         (GSList *partition);
                    GtsGraphBisection;
gboolean            gts_graph_bisection_check           (GtsGraphBisection *bg);
GtsGraphBisection * gts_graph_ggg_bisection             (GtsGraph *g,
                                                         guint ntry);
GtsGraphBisection * gts_graph_bfgg_bisection            (GtsGraph *g,
                                                         guint ntry);
gdouble             gts_graph_bisection_kl_refine       (GtsGraphBisection *bg,
                                                         guint mmax);
gdouble             gts_graph_bisection_bkl_refine      (GtsGraphBisection *bg,
                                                         guint mmax,
                                                         gfloat imbalance);
GtsGraphBisection * gts_graph_bisection_new             (GtsWGraph *wg,
                                                         guint ntry,
                                                         guint mmax,
                                                         guint nmin,
                                                         gfloat imbalance);
void                gts_graph_bisection_destroy         (GtsGraphBisection *bg,
                                                         gboolean destroy_graphs);

Description

Details

GTS_C_VAR

#define             GTS_C_VAR


gts_major_version

extern const guint gts_major_version;


gts_minor_version

extern const guint gts_minor_version;


gts_micro_version

extern const guint gts_micro_version;


gts_interface_age

extern const guint gts_interface_age;


gts_binary_age

extern const guint gts_binary_age;


GTS_CHECK_VERSION()

#define             GTS_CHECK_VERSION(major,minor,micro)

major :

minor :

micro :


GTS_COMMENTS

#define GTS_COMMENTS  "#!"


GTS_MAINTAINER

#define GTS_MAINTAINER "popinet@users.sourceforge.net"


GtsObjectClassInfo

typedef struct {
  gchar name[GTS_CLASS_NAME_LENGTH];
  guint object_size;
  guint class_size;
  GtsObjectClassInitFunc class_init_func;
  GtsObjectInitFunc object_init_func;
  GtsArgSetFunc arg_set_func;
  GtsArgGetFunc arg_get_func;
} GtsObjectClassInfo;


GtsObjectClassInitFunc ()

void                (*GtsObjectClassInitFunc)           (GtsObjectClass *objclass);

objclass :


GtsObjectInitFunc ()

void                (*GtsObjectInitFunc)                (GtsObject *obj);

obj :


GtsArgSetFunc ()

void                (*GtsArgSetFunc)                    (GtsObject *obj);

obj :


GtsArgGetFunc ()

void                (*GtsArgGetFunc)                    (GtsObject *obj);

obj :


GtsVector

typedef gdouble                  GtsVector[3];


GtsVector4

typedef gdouble                  GtsVector4[4];


GtsMatrix

typedef GtsVector4               GtsMatrix;


GtsKeyFunc ()

gdouble             (*GtsKeyFunc)                       (gpointer item,
                                                         gpointer data);

item :

A pointer to an item to be stored in the heap.

data :

User data passed to gts_eheap_new().

Returns :

the value of the key for the given item.


enum GtsIntersect

typedef enum 
{ 
  GTS_OUT = -1,
  GTS_ON = 0,
  GTS_IN = 1
} GtsIntersect;


GtsColor

typedef struct {
  gfloat r, g, b;
} GtsColor;


GtsFunc ()

gint                (*GtsFunc)                          (gpointer item,
                                                         gpointer data);

item :

data :

Returns :


GtsFile

typedef struct {
  FILE * fp;
  guint line, pos;
  GString * token;
  GtsTokenType type;
  gchar * error;

  guint curline, curpos;
  guint scope, scope_max;
  gint next_token;
  gchar * delimiters;
  gchar * comments;
  gchar * tokens;
  gchar * buf;
  size_t len;
} GtsFile;


enum GtsTokenType

typedef enum {
  GTS_NONE   = 1 << 8,
  GTS_INT    = 1 << 9,
  GTS_UINT   = 1 << 10,
  GTS_FLOAT  = 1 << 11,
  GTS_DOUBLE = 1 << 12,
  GTS_STRING = 1 << 13,
  GTS_FILE   = 1 << 14,
  GTS_ERROR  = 1 << 15,
  GTS_OBJ    = 1 << 16,
} GtsTokenType;


GtsFileVariable

typedef struct {
  GtsTokenType type;
  gchar name[30];
  gboolean unique;
  gpointer data;
  gboolean set;
  guint line, pos;
} GtsFileVariable;


gts_file_new ()

GtsFile *           gts_file_new                        (FILE *fp);

fp :

a file pointer.

Returns :

a new GtsFile.


gts_file_new_from_string ()

GtsFile *           gts_file_new_from_string            (gchar *s);

s :

a string.

Returns :

a new GtsFile.


gts_file_new_from_buffer ()

GtsFile *           gts_file_new_from_buffer            (gchar *buf,
                                                         size_t len);

buf :

a buffer.

len :

the size of the buffer.

Returns :

a new GtsFile.


gts_file_verror ()

void                gts_file_verror                     (GtsFile *f,
                                                         const gchar *format,
                                                         va_list args);

Sets the error field of f using g_strdup_vprintf().

This function can be called only once and disables any other operation on f (gts_file_close() excepted).

f :

a GtsFile.

format :

the standard sprintf() format string.

args :

the list of parameters to insert into the format string.


gts_file_error ()

void                gts_file_error                      (GtsFile *f,
                                                         const gchar *format,
                                                         ...);

Sets the error field of f using gts_file_verror().

This function can be called only once and disables any other operation on f (gts_file_close() excepted).

f :

a GtsFile.

format :

the standard sprintf() format string.

... :

the parameters to insert into the format string.


gts_file_getc ()

gint                gts_file_getc                       (GtsFile *f);

f :

a GtsFile.

Returns :

the next character in f or EOF if the end of the file is reached or if an error occured.


gts_file_read ()

guint               gts_file_read                       (GtsFile *f,
                                                         gpointer ptr,
                                                         guint size,
                                                         guint nmemb);

Reads nmemb elements of data, each size bytes long, from f, storing them at the location given by ptr.

f :

a GtsFile.

ptr :

a pointer.

size :

size of an element.

nmemb :

number of elements.

Returns :

the number of elements read.


gts_file_getc_scope ()

gint                gts_file_getc_scope                 (GtsFile *f);

f :

a GtsFile.

Returns :

the next character in f in the scope defined by f->scope_max or EOF if the end of the file is reached or if an error occured.


gts_file_next_token ()

void                gts_file_next_token                 (GtsFile *f);

Reads next token from f and updates its token and delim fields.

f :

a GtsFile.


gts_file_first_token_after ()

void                gts_file_first_token_after          (GtsFile *f,
                                                         GtsTokenType type);

Finds and sets the first token of a type different from type occuring after a token of type type.

f :

a GtsFile.

type :

a GtsTokenType.


gts_file_assign_start ()

void                gts_file_assign_start               (GtsFile *f,
                                                         GtsFileVariable *vars);

Opens a block delimited by braces to read a list of optional arguments specified by vars.

If an error is encountered the error field of f is set.

f :

a GtsFile.

vars :

a GTS_NONE terminated array of GtsFileVariable.


gts_file_assign_next ()

GtsFileVariable *   gts_file_assign_next                (GtsFile *f,
                                                         GtsFileVariable *vars);

Assigns the next optional argument of vars read from f.

f :

a GtsFile.

vars :

a GTS_NONE terminated array of GtsFileVariable.

Returns :

the variable of vars which has been assigned or NULL if no variable has been assigned (if an error has been encountered the error field of f is set).


gts_file_assign_variables ()

void                gts_file_assign_variables           (GtsFile *f,
                                                         GtsFileVariable *vars);

Assigns all the variables belonging to vars found in f.

If an error is encountered the error field of f is set.

f :

a GtsFile.

vars :

an array of GtsFileVariable.


gts_file_variable_error ()

void                gts_file_variable_error             (GtsFile *f,
                                                         GtsFileVariable *vars,
                                                         const gchar *name,
                                                         const gchar *format,
                                                         ...);

Sets the error field of f using gts_file_verror().

String name must match one of the variable names in vars.

If variable name has been assigned (using gts_file_assign_variables()) sets the line and pos fields of f to the line and position where it has been assigned.

f :

a GtsFile.

vars :

an array of GtsFileVariable.

name :

the name of a variable in vars.

format :

the standard sprintf() format string.

... :

the parameters to insert into the format string.


gts_file_destroy ()

void                gts_file_destroy                    (GtsFile *f);

Frees all the memory allocated for f.

f :

a GtsFile.


GTS_OBJECT_CAST()

#define             GTS_OBJECT_CAST(obj, type, klass)

obj :

type :

klass :


GTS_OBJECT_CLASS_CAST()

#define             GTS_OBJECT_CLASS_CAST(objklass, type, klass)

objklass :

type :

klass :


GTS_CLASS_NAME_LENGTH

#define GTS_CLASS_NAME_LENGTH 40


enum GtsObjectFlags

typedef enum
{
  GTS_DESTROYED         = 1 << 0,
  GTS_USER_FLAG         = 1 /* user flags start from here */
} GtsObjectFlags;


GTS_OBJECT_FLAGS()

#define GTS_OBJECT_FLAGS(obj)             (GTS_OBJECT (obj)->flags)

obj :


GTS_OBJECT_DESTROYED()

#define GTS_OBJECT_DESTROYED(obj)         ((GTS_OBJECT_FLAGS (obj) & GTS_DESTROYED) != 0)

obj :


GTS_OBJECT_SET_FLAGS()

#define GTS_OBJECT_SET_FLAGS(obj,flag)	  G_STMT_START{ (GTS_OBJECT_FLAGS (obj) |= (flag)); }G_STMT_END

obj :

flag :


GTS_OBJECT_UNSET_FLAGS()

#define GTS_OBJECT_UNSET_FLAGS(obj,flag)  G_STMT_START{ (GTS_OBJECT_FLAGS (obj) &= ~(flag)); }G_STMT_END

obj :

flag :


GtsObject

typedef struct {
  GtsObjectClass * klass;

  gpointer reserved;
  guint32 flags;
} GtsObject;


gts_object_class_new ()

gpointer            gts_object_class_new                (GtsObjectClass *parent_class,
                                                         GtsObjectClassInfo *info);

parent_class :

a GtsObjectClass.

info :

a GtsObjectClassInfo, description of the new class to create.

Returns :

a new GtsObjectClass derived from parent_class and described by info.


gts_object_class ()

GtsObjectClass *    gts_object_class                    (void);

Returns :

the GtsObjectClass.


gts_object_check_cast ()

gpointer            gts_object_check_cast               (gpointer object,
                                                         gpointer klass);

object :

a GtsObject.

klass :

a GtsObjectClass.

Returns :

object while emitting warnings if object is not of class klass.


gts_object_class_check_cast ()

gpointer            gts_object_class_check_cast         (gpointer klass,
                                                         gpointer from);

klass :

a GtsObjectClass.

from :

a GtsObjectClass.

Returns :

klass while emitting warnings if klass is not derived from from.


gts_object_is_from_class ()

gpointer            gts_object_is_from_class            (gpointer object);

object :

Returns :


gts_object_class_is_from_class ()

gpointer            gts_object_class_is_from_class      (gpointer klass);

klass :

Returns :


gts_object_class_from_name ()

GtsObjectClass *    gts_object_class_from_name          (const gchar *name);

name :

the name of a GtsObjectClass.

Returns :

the GtsObjectClass with name name or NULL if it hasn't been instantiated yet.


gts_object_new ()

GtsObject *         gts_object_new                      (GtsObjectClass *klass);

klass :

a GtsObjectClass.

Returns :

a new initialized object of class klass.


gts_object_clone ()

GtsObject *         gts_object_clone                    (GtsObject *object);

Calls the clone method of object. The call to this function will fail if no clone method exists for the given object.

object :

a GtsObject.

Returns :

a new object clone of object.


gts_object_attributes ()

void                gts_object_attributes               (GtsObject *object,
                                                         GtsObject *from);

Calls the attributes() method of object using from as source.

object :

a GtsObject.

from :

a GtsObject.


gts_object_init ()

void                gts_object_init                     (GtsObject *object,
                                                         GtsObjectClass *klass);

Calls the init method of klass with object as argument. This is done recursively in the correct order (from the base class to the top). You should rarely need this function as it is called automatically by the constructor for each class.

object :

a GtsObject.

klass :

a GtsObjectClass.


gts_object_reset_reserved ()

void                gts_object_reset_reserved           (GtsObject *object);

Reset the reserved field of object.

object :

a GtsObject.


gts_object_destroy ()

void                gts_object_destroy                  (GtsObject *object);

Calls the destroy method of object, freeing all memory allocated for it.

object :

a GtsObject.


gts_finalize ()

void                gts_finalize                        (void);

Free all the memory allocated by the object system of GTS. No other GTS function can be called after this function has been called.


GtsRange

typedef struct {
  gdouble min, max, sum, sum2, mean, stddev;
  guint n;
} GtsRange;


gts_range_init ()

void                gts_range_init                      (GtsRange *r);

Initializes a GtsRange.

r :

a GtsRange.


gts_range_reset ()

void                gts_range_reset                     (GtsRange *r);

Sets all the fields of r to 0.

r :

a GtsRange.


gts_range_add_value ()

void                gts_range_add_value                 (GtsRange *r,
                                                         gdouble val);

Adds val to r.

r :

a GtsRange.

val :

a value to add to r.


gts_range_update ()

void                gts_range_update                    (GtsRange *r);

Updates the fields of r.

r :

a GtsRange.


gts_range_print ()

void                gts_range_print                     (GtsRange *r,
                                                         FILE *fptr);

Writes a text representation of r in fptr.

r :

a GtsRange.

fptr :

a file pointer.


GTS_IS_POINT()

#define             GTS_IS_POINT(obj)

obj :


GTS_POINT()

#define             GTS_POINT(obj)

obj :


GTS_POINT_CLASS()

#define             GTS_POINT_CLASS(klass)

klass :


GtsPoint

typedef struct {
  GtsObject object;

  gdouble x, y, z; /* must be contiguous (cast to robust functions) */
} GtsPoint;


gts_point_class ()

GtsPointClass *     gts_point_class                     (void);

Returns :

the GtsPointClass.


gts_point_new ()

GtsPoint *          gts_point_new                       (GtsPointClass *klass,
                                                         gdouble x,
                                                         gdouble y,
                                                         gdouble z);

klass :

a GtsPointClass.

x :

the x-coordinate.

y :

the y-coordinate.

z :

the z-coordinate.

Returns :

a new GtsPoint.


gts_point_set ()

void                gts_point_set                       (GtsPoint *p,
                                                         gdouble x,
                                                         gdouble y,
                                                         gdouble z);

Sets the coordinates of p.

p :

a GtsPoint.

x :

the x-coordinate.

y :

the y-coordinate.

z :

the z-coordinate.


gts_point_is_in_rectangle()

#define             gts_point_is_in_rectangle(p, p1, p2)

p :

p1 :

p2 :


gts_segment_triangle_intersection ()

GtsPoint *          gts_segment_triangle_intersection   (GtsSegment *s,
                                                         GtsTriangle *t,
                                                         gboolean boundary,
                                                         GtsPointClass *klass);

Checks if s intersects t. If this is the case, creates a new point pi intersection of s with t.

This function is geometrically robust in the sense that it will not return a point if s and t do not intersect and will return a point if s and t do intersect. However, the point coordinates are subject to round-off errors.

Note that this function will not return any point if s is contained in the plane defined by t.

s :

a GtsSegment.

t :

a GtsTriangle.

boundary :

if TRUE, the boundary of t is taken into account.

klass :

a GtsPointClass to be used for the new point.

Returns :

a summit of t (if boundary is set to TRUE), one of the endpoints of s or a new GtsPoint, intersection of s with t or NULL if s and t don't intersect.


gts_point_transform ()

void                gts_point_transform                 (GtsPoint *p,
                                                         GtsMatrix *m);

Transform the coordinates of p according to m. (p[] becomes m[][].p[]).

p :

a GtsPoint.

m :

the GtsMatrix representing the transformation to apply to the coordinates of p.


gts_point_distance ()

gdouble             gts_point_distance                  (GtsPoint *p1,
                                                         GtsPoint *p2);

p1 :

a GtsPoint.

p2 :

another GtsPoint.

Returns :

the Euclidean distance between p1 and p2.


gts_point_distance2 ()

gdouble             gts_point_distance2                 (GtsPoint *p1,
                                                         GtsPoint *p2);

p1 :

a GtsPoint.

p2 :

another GtsPoint.

Returns :

the square of the Euclidean distance between p1 and p2.


gts_point_orientation_3d ()

gdouble             gts_point_orientation_3d            (GtsPoint *p1,
                                                         GtsPoint *p2,
                                                         GtsPoint *p3,
                                                         GtsPoint *p4);

Checks if p4 lies above, below or on the plane passing through the points p1, p2 and p3. Below is defined so that p1, p2 and p3 appear in counterclockwise order when viewed from above the plane. The returned value is an approximation of six times the signed volume of the tetrahedron defined by the four points. This function uses adaptive floating point arithmetic and is consequently geometrically robust.

p1 :

a GtsPoint.

p2 :

a GtsPoint.

p3 :

a GtsPoint.

p4 :

a GtsPoint.

Returns :

a positive value if p4 lies below, a negative value if p4 lies above the plane, zero if the four points are coplanar.


gts_point_orientation_3d_sos ()

gint                gts_point_orientation_3d_sos        (GtsPoint *p1,
                                                         GtsPoint *p2,
                                                         GtsPoint *p3,
                                                         GtsPoint *p4);

Checks if p4 lies above or below the plane passing through the points p1, p2 and p3. Below is defined so that p1, p2 and p3 appear in counterclockwise order when viewed from above the plane. This function uses adaptive floating point arithmetic and is consequently geometrically robust.

Simulation of Simplicity (SoS) is used to break ties when the orientation is degenerate (i.e. p4 lies on the plane defined by p1, p2 and p3).

p1 :

a GtsPoint.

p2 :

a GtsPoint.

p3 :

a GtsPoint.

p4 :

a GtsPoint.

Returns :

+1 if p4 lies below, -1 if p4 lies above the plane.


gts_point_is_in_triangle ()

GtsIntersect        gts_point_is_in_triangle            (GtsPoint *p,
                                                         GtsTriangle *t);

Tests if the planar projection (x, y) of p is inside, outside or on the boundary of the planar projection of t. This function is geometrically robust.

p :

a GtsPoint.

t :

a GtsTriangle.

Returns :

GTS_IN if p is inside t, GTS_ON if p is on the boundary of t, GTS_OUT otherwise.


gts_point_in_circle ()

gdouble             gts_point_in_circle                 (GtsPoint *p,
                                                         GtsPoint *p1,
                                                         GtsPoint *p2,
                                                         GtsPoint *p3);

Tests if the planar projection (x, y) of p is inside or outside the circle defined by the planar projection of p1, p2 and p3.

p :

a GtsPoint.

p1 :

a GtsPoint.

p2 :

a GtsPoint.

p3 :

a GtsPoint.

Returns :

a positive number if p lies inside, a negative number if p lies outside and zero if p lies on the circle.


gts_point_in_sphere ()

gdouble             gts_point_in_sphere                 (GtsPoint *p,
                                                         GtsPoint *p1,
                                                         GtsPoint *p2,
                                                         GtsPoint *p3,
                                                         GtsPoint *p4);

Tests if p is inside or outside the sphere defined by p1, p2, p3 and p4.

p :

a GtsPoint.

p1 :

a GtsPoint.

p2 :

a GtsPoint.

p3 :

a GtsPoint.

p4 :

a GtsPoint.

Returns :

a positive number if p lies inside, a negative number if p lies outside and zero if p lies on the sphere.


gts_point_in_triangle_circle ()

gdouble             gts_point_in_triangle_circle        (GtsPoint *p,
                                                         GtsTriangle *t);

Tests if the planar projection (x, y) of p is inside or outside the circumcircle of the planar projection of t. This function is geometrically robust.

p :

a GtsPoint.

t :

a GtsTriangle.

Returns :

a positive number if p lies inside, a negative number if p lies outside and zero if p lies on the circumcircle of t.


gts_point_orientation ()

gdouble             gts_point_orientation               (GtsPoint *p1,
                                                         GtsPoint *p2,
                                                         GtsPoint *p3);

Checks for orientation of the projection of three points on the (x,y) plane. The result is also an approximation of twice the signed area of the triangle defined by the three points. This function uses adaptive floating point arithmetic and is consequently geometrically robust.

p1 :

a GtsPoint.

p2 :

a GtsPoint.

p3 :

a GtsPoint.

Returns :

a positive value if p1, p2 and p3 appear in counterclockwise order, a negative value if they appear in clockwise order and zero if they are colinear.


gts_point_orientation_sos ()

gint                gts_point_orientation_sos           (GtsPoint *p1,
                                                         GtsPoint *p2,
                                                         GtsPoint *p3);

Checks for orientation of the projection of three points on the (x,y) plane.

Simulation of Simplicity (SoS) is used to break ties when the orientation is degenerate (i.e. p3 lies on the line defined by p1 and p2).

p1 :

a GtsPoint.

p2 :

a GtsPoint.

p3 :

a GtsPoint.

Returns :

a positive value if p1, p2 and p3 appear in counterclockwise order or a negative value if they appear in clockwise order.


gts_point_segment_distance2 ()

gdouble             gts_point_segment_distance2         (GtsPoint *p,
                                                         GtsSegment *s);

p :

a GtsPoint.

s :

a GtsSegment.

Returns :

the square of the minimun Euclidean distance between p and s.


gts_point_segment_distance ()

gdouble             gts_point_segment_distance          (GtsPoint *p,
                                                         GtsSegment *s);

p :

a GtsPoint.

s :

a GtsSegment.

Returns :

the minimun Euclidean distance between p and s.


gts_point_segment_closest ()

void                gts_point_segment_closest           (GtsPoint *p,
                                                         GtsSegment *s,
                                                         GtsPoint *closest);

Set the coordinates of closest to the coordinates of the point belonging to s closest to p.

p :

a GtsPoint.

s :

a GtsSegment.

closest :

a GtsPoint.


gts_point_triangle_distance2 ()

gdouble             gts_point_triangle_distance2        (GtsPoint *p,
                                                         GtsTriangle *t);

p :

a GtsPoint.

t :

a GtsTriangle.

Returns :

the square of the minimun Euclidean distance between p and t.


gts_point_triangle_distance ()

gdouble             gts_point_triangle_distance         (GtsPoint *p,
                                                         GtsTriangle *t);

p :

a GtsPoint.

t :

a GtsTriangle.

Returns :

the minimun Euclidean distance between p and t.


gts_point_triangle_closest ()

void                gts_point_triangle_closest          (GtsPoint *p,
                                                         GtsTriangle *t,
                                                         GtsPoint *closest);

Set the coordinates of closest to those of the point belonging to t and closest to p.

p :

a GtsPoint.

t :

a GtsTriangle.

closest :

a GtsPoint.


gts_point_is_inside_surface ()

gboolean            gts_point_is_inside_surface         (GtsPoint *p,
                                                         GNode *tree,
                                                         gboolean is_open);

p :

a GtsPoint.

tree :

a bounding box tree of the faces of a closed, orientable surface (see gts_bb_tree_surface()).

is_open :

TRUE if the surface defined by tree is "open" i.e. its volume is negative, FALSE otherwise.

Returns :

TRUE if p is inside the surface defined by tree, FALSE otherwise.


GTS_IS_VERTEX()

#define             GTS_IS_VERTEX(obj)

obj :


GTS_VERTEX()

#define             GTS_VERTEX(obj)

obj :


GTS_VERTEX_CLASS()

#define             GTS_VERTEX_CLASS(klass)

klass :


GtsVertex

typedef struct {
  GtsPoint p;
  
  GSList * segments;
} GtsVertex;


gts_vertex_class ()

GtsVertexClass *    gts_vertex_class                    (void);

Returns :

the GtsVertexClass.


gts_vertex_new ()

GtsVertex *         gts_vertex_new                      (GtsVertexClass *klass,
                                                         gdouble x,
                                                         gdouble y,
                                                         gdouble z);

klass :

a GtsVertexClass.

x :

the x-coordinate of the vertex to create.

y :

the y-coordinate of the vertex to create.

z :

the y-coordinate of the vertex to create.

Returns :

a new GtsVertex with x, y and z as coordinates.


gts_vertex_replace ()

void                gts_vertex_replace                  (GtsVertex *v,
                                                         GtsVertex *with);

Replaces vertex v with vertex with. v and with must be different. All the GtsSegment which have v has one of their vertices are updated. The segments list of vertex v is freed and v->segments is set to NULL.

v :

a GtsVertex.

with :

another GtsVertex.


gts_vertex_is_unattached ()

gboolean            gts_vertex_is_unattached            (GtsVertex *v);

v :

a GtsVertex.

Returns :

TRUE if v is not the endpoint of any GtsSegment, FALSE otherwise.


gts_vertices_are_connected ()

GtsSegment *        gts_vertices_are_connected          (GtsVertex *v1,
                                                         GtsVertex *v2);

v1 :

a GtsVertex.

v2 :

another GtsVertex.

Returns :

if v1 and v2 are the vertices of the same GtsSegment this segment else NULL.


gts_vertex_triangles ()

GSList *            gts_vertex_triangles                (GtsVertex *v,
                                                         GSList *list);

Adds all the GtsTriangle which share v as a vertex and do not already belong to list.

v :

a GtsVertex.

list :

a list of GtsTriangle.

Returns :

the new list of unique GtsTriangle which share v as a vertex.


gts_vertex_faces ()

GSList *            gts_vertex_faces                    (GtsVertex *v,
                                                         GtsSurface *surface,
                                                         GSList *list);

Adds all the GtsFace belonging to surface (if not NULL) which share v as a vertex and do not already belong to list.

v :

a GtsVertex.

surface :

a GtsSurface or NULL.

list :

a list of GtsFace.

Returns :

the new list of unique GtsFace belonging to surface which share v as a vertex.


gts_vertex_neighbors ()

GSList *            gts_vertex_neighbors                (GtsVertex *v,
                                                         GSList *list,
                                                         GtsSurface *surface);

Adds to list all the GtsVertex connected to v by a GtsSegment and not already in list. If surface is not NULL only the vertices connected to v by an edge belonging to surface are considered.

v :

a GtsVertex.

list :

a list of GtsVertex.

surface :

a GtsSurface or NULL.

Returns :

the new list of unique GtsVertex.


gts_vertices_from_segments ()

GSList *            gts_vertices_from_segments          (GSList *segments);

segments :

a list of GtsSegment.

Returns :

a list of GtsVertex, vertices of a GtsSegment in segments. Each element in the list is unique (no duplicates).


gts_vertex_is_boundary ()

gboolean            gts_vertex_is_boundary              (GtsVertex *v,
                                                         GtsSurface *surface);

v :

a GtsVertex.

surface :

a GtsSurface or NULL.

Returns :

TRUE if v is used by a GtsEdge boundary of surface as determined by gts_edge_is_boundary(), FALSE otherwise.


gts_vertices_merge ()

GList *             gts_vertices_merge                  (GList *vertices,
                                                         gdouble epsilon,
                                                         gboolean (checkGtsVertex *, GtsVertex *) ());

For each vertex v in vertices look if there are any vertex of vertices contained in a box centered on v of size 2*epsilon. If there are and if check is not NULL and returns TRUE, replace them with v (using gts_vertex_replace()), destroy them and remove them from list. This is done efficiently using Kd-Trees.

vertices :

a list of GtsVertex.

epsilon :

half the size of the bounding box to consider for each vertex.

check :

function called for each pair of vertices about to be merged or NULL.

Returns :

the updated list of vertices.


gts_vertex_fan_oriented ()

GSList *            gts_vertex_fan_oriented             (GtsVertex *v,
                                                         GtsSurface *surface);

v :

a GtsVertex.

surface :

a GtsSurface.

Returns :

a list of GtsEdge describing in counterclockwise order the boundary of the fan of summit v, the faces of the fan belonging to surface.


gts_vertex_is_contact ()

guint               gts_vertex_is_contact               (GtsVertex *v,
                                                         gboolean sever);

v :

a GtsVertex.

sever :

if TRUE and if v is a contact vertex between two or more sets of connected triangles replaces it with as many vertices, clones of v.

Returns :

the number of sets of connected triangles sharing v as a contact vertex.


GtsVertexNormal

typedef struct {
  GtsVector n;
} GtsVertexNormal;


GTS_VERTEX_NORMAL()

#define             GTS_VERTEX_NORMAL(obj)

obj :


GTS_IS_VERTEX_NORMAL()

#define             GTS_IS_VERTEX_NORMAL(obj)

obj :


gts_vertex_normal_class ()

GtsVertexClass *    gts_vertex_normal_class             (void);

Returns :


GtsColorVertex

typedef struct {
  GtsColor c;
} GtsColorVertex;


GTS_COLOR_VERTEX()

#define             GTS_COLOR_VERTEX(obj)

obj :


GTS_IS_COLOR_VERTEX()

#define             GTS_IS_COLOR_VERTEX(obj)

obj :


gts_color_vertex_class ()

GtsVertexClass *    gts_color_vertex_class              (void);

Returns :


GTS_IS_SEGMENT()

#define             GTS_IS_SEGMENT(obj)

obj :


GTS_SEGMENT()

#define             GTS_SEGMENT(obj)

obj :


GTS_SEGMENT_CLASS()

#define             GTS_SEGMENT_CLASS(klass)

klass :


GtsSegment

typedef struct {
  GtsObject object;

  GtsVertex * v1;
  GtsVertex * v2;
} GtsSegment;


gts_segment_class ()

GtsSegmentClass *   gts_segment_class                   (void);

Returns :

the GtsSegmentClass.


gts_segment_new ()

GtsSegment *        gts_segment_new                     (GtsSegmentClass *klass,
                                                         GtsVertex *v1,
                                                         GtsVertex *v2);

klass :

a GtsSegmentClass.

v1 :

a GtsVertex.

v2 :

another GtsVertex different from v1.

Returns :

a new GtsSegment linking v1 and v2.


gts_segment_connect()

#define             gts_segment_connect(s, e1, e2)

s :

e1 :

e2 :


gts_segments_are_identical()

#define             gts_segments_are_identical(s1, s2)

s1 :

s2 :


gts_segments_touch()

#define             gts_segments_touch(s1, s2)

s1 :

s2 :


gts_segments_are_intersecting ()

GtsIntersect        gts_segments_are_intersecting       (GtsSegment *s1,
                                                         GtsSegment *s2);

s1 :

a GtsSegment.

s2 :

a GtsSegment.

Returns :

GTS_IN if s1 and s2 are intersecting, GTS_ON if one of the endpoints of s1 (resp. s2) lies on s2 (resp. s1), GTS_OUT otherwise.


gts_segment_is_duplicate ()

GtsSegment *        gts_segment_is_duplicate            (GtsSegment *s);

s :

a GtsSegment.

Returns :

the first GtsSegment different from s which shares the same endpoints or NULL if there is none.


gts_segment_midvertex ()

GtsVertex *         gts_segment_midvertex               (GtsSegment *s,
                                                         GtsVertexClass *klass);

s :

a GtsSegment.

klass :

a GtsVertexClass to be used for the new vertex.

Returns :

a new GtsVertex, midvertex of s.


gts_segments_from_vertices ()

GSList *            gts_segments_from_vertices          (GSList *vertices);

vertices :

a list of GtsVertex.

Returns :

a list of unique GtsSegment which have one of their vertices in vertices.


gts_segment_is_ok ()

gboolean            gts_segment_is_ok                   (GtsSegment *s);

s :

a GtsSegment.

Returns :

TRUE if s is not degenerate (i.e. s->v1 != s->v2) and not duplicate, FALSE otherwise.


GTS_IS_EDGE()

#define             GTS_IS_EDGE(obj)

obj :


GTS_EDGE()

#define             GTS_EDGE(obj)

obj :


GTS_EDGE_CLASS()

#define             GTS_EDGE_CLASS(klass)

klass :


GtsEdge

typedef struct {
  GtsSegment segment;

  GSList * triangles;
} GtsEdge;


gts_edge_class ()

GtsEdgeClass *      gts_edge_class                      (void);

Returns :

the GtsEdgeClass.


gts_edge_new ()

GtsEdge *           gts_edge_new                        (GtsEdgeClass *klass,
                                                         GtsVertex *v1,
                                                         GtsVertex *v2);

klass :

a GtsEdgeClass.

v1 :

a GtsVertex.

v2 :

a GtsVertex.

Returns :

a new GtsEdge linking v1 and v2.


gts_edge_is_unattached()

#define       gts_edge_is_unattached(s) ((s)->triangles == NULL ? TRUE : FALSE)

Evaluates to TRUE if no triangles uses s as an edge, FALSE otherwise.

s :

a GtsEdge.


gts_edge_has_parent_surface ()

GtsFace *           gts_edge_has_parent_surface         (GtsEdge *e,
                                                         GtsSurface *surface);

e :

a GtsEdge.

surface :

a GtsSurface.

Returns :

a GtsFace of surface having e as an edge, NULL otherwise.


gts_edge_has_any_parent_surface ()

GtsFace *           gts_edge_has_any_parent_surface     (GtsEdge *e);

e :

a GtsEdge.

Returns :

NULL if e is not an edge of any triangle or if all the faces having e has an edge do not belong to any surface, a GtsFace belonging to a surface and having e as an edge.


gts_edge_is_boundary ()

GtsFace *           gts_edge_is_boundary                (GtsEdge *e,
                                                         GtsSurface *surface);

e :

a GtsEdge.

surface :

a GtsSurface or NULL.

Returns :

the unique GtsFace (which belongs to surface) and which has e as an edge (i.e. e is a boundary edge (of surface)) or NULL if there is more than one or no faces (belonging to surface) and with e as an edge.


gts_edge_replace ()

void                gts_edge_replace                    (GtsEdge *e,
                                                         GtsEdge *with);

Replaces e with with. For each triangle which uses e as an edge, e is replaced with with. The with->triangles list is updated appropriately and the e->triangles list is freed and set to NULL.

e :

a GtsEdge.

with :

a GtsEdge.


gts_edges_from_vertices ()

GSList *            gts_edges_from_vertices             (GSList *vertices,
                                                         GtsSurface *parent);

vertices :

a list of GtsVertex.

parent :

a GtsSurface.

Returns :

a list of unique GtsEdge which have one of their vertices in vertices and are used by a face of parent.


gts_edge_face_number ()

guint               gts_edge_face_number                (GtsEdge *e,
                                                         GtsSurface *s);

e :

a GtsEdge.

s :

a GtsSurface.

Returns :

the number of faces using e and belonging to s.


gts_edge_collapse_is_valid ()

gboolean            gts_edge_collapse_is_valid          (GtsEdge *e);

An implementation of the topological constraints described in the "Mesh Optimization" article of Hoppe et al (1993).

e :

a GtsEdge.

Returns :

TRUE if e can be collapsed without violation of the topological constraints, FALSE otherwise.


gts_edge_collapse_creates_fold ()

gboolean            gts_edge_collapse_creates_fold      (GtsEdge *e,
                                                         GtsVertex *v,
                                                         gdouble max);

e :

a GtsEdge.

v :

a GtsVertex.

max :

the maximum value of the square of the cosine of the angle between two triangles.

Returns :

TRUE if collapsing edge e to vertex v would create faces making an angle the cosine squared of which would be larger than max, FALSE otherwise.


gts_edge_is_duplicate ()

GtsEdge *           gts_edge_is_duplicate               (GtsEdge *e);

e :

a GtsEdge.

Returns :

the first GtsEdge different from e which shares the same endpoints or NULL if there is none.


gts_edges_merge ()

GList *             gts_edges_merge                     (GList *edges);

For each edge in edges check if it is duplicated (as returned by gts_edge_is_duplicate()). If it is replace it by its duplicate, destroy it and remove it from the list.

edges :

a list of GtsEdge.

Returns :

the updated edges list.


gts_edge_belongs_to_tetrahedron ()

gboolean            gts_edge_belongs_to_tetrahedron     (GtsEdge *e);

e :

a GtsEdge.

Returns :

TRUE if e is used by faces forming a tetrahedron, FALSE otherwise.


gts_edge_is_contact ()

guint               gts_edge_is_contact                 (GtsEdge *e);

e :

a GtsEdge.

Returns :

the number of sets of connected triangles sharing e as a contact edge.


gts_edge_swap ()

void                gts_edge_swap                       (GtsEdge *e,
                                                         GtsSurface *s);

Performs an "edge swap" on the two triangles sharing e and belonging to s.

e :

a GtsEdge.

s :

a GtsSurface.


gts_edge_manifold_faces ()

gboolean            gts_edge_manifold_faces             (GtsEdge *e,
                                                         GtsSurface *s,
                                                         GtsFace **f1,
                                                         GtsFace **f2);

If e is a manifold edge of surface s, fills f1 and f2 with the faces belonging to s and sharing e.

e :

a GtsEdge.

s :

a GtsSurface.

f1 :

pointer for first face.

f2 :

pointer for second face.

Returns :

TRUE if e is a manifold edge, FALSE otherwise.


GTS_IS_TRIANGLE()

#define             GTS_IS_TRIANGLE(obj)

obj :


GTS_TRIANGLE()

#define             GTS_TRIANGLE(obj)

obj :


GTS_TRIANGLE_CLASS()

#define             GTS_TRIANGLE_CLASS(klass)

klass :


GtsTriangle

typedef struct {
  GtsObject object;

  GtsEdge * e1;
  GtsEdge * e2;
  GtsEdge * e3;
} GtsTriangle;


gts_triangle_class ()

GtsTriangleClass *  gts_triangle_class                  (void);

Returns :

the GtsTriangleClass.


gts_triangle_set ()

void                gts_triangle_set                    (GtsTriangle *triangle,
                                                         GtsEdge *e1,
                                                         GtsEdge *e2,
                                                         GtsEdge *e3);

Sets the edge of triangle to e1, e2 and e3 while checking that they define a valid triangle.

triangle :

a GtsTriangle.

e1 :

a GtsEdge.

e2 :

another GtsEdge touching e1.

e3 :

another GtsEdge touching both e1 and e2.


gts_triangle_new ()

GtsTriangle *       gts_triangle_new                    (GtsTriangleClass *klass,
                                                         GtsEdge *e1,
                                                         GtsEdge *e2,
                                                         GtsEdge *e3);

klass :

a GtsTriangleClass.

e1 :

a GtsEdge.

e2 :

another GtsEdge touching e1.

e3 :

another GtsEdge touching both e1 and e2.

Returns :

a new GtsTriangle having e1, e2 and e3 as edges.


gts_triangle_vertex()

#define             gts_triangle_vertex(t)

t :


gts_triangle_vertex_opposite ()

GtsVertex *         gts_triangle_vertex_opposite        (GtsTriangle *t,
                                                         GtsEdge *e);

This function fails if e is not an edge of t.

t :

a GtsTriangle.

e :

a GtsEdge used by t.

Returns :

a GtsVertex, vertex of t which does not belong to e.


gts_triangle_edge_opposite ()

GtsEdge *           gts_triangle_edge_opposite          (GtsTriangle *t,
                                                         GtsVertex *v);

t :

a GtsTriangle.

v :

a GtsVertex of t.

Returns :

the edge of t opposite v or NULL if v is not a vertice of t.


gts_triangles_angle ()

gdouble             gts_triangles_angle                 (GtsTriangle *t1,
                                                         GtsTriangle *t2);

t1 :

a GtsTriangle.

t2 :

a GtsTriangle.

Returns :

the value (in radians) of the angle between t1 and t2.


gts_triangles_are_compatible ()

gboolean            gts_triangles_are_compatible        (GtsTriangle *t1,
                                                         GtsTriangle *t2,
                                                         GtsEdge *e);

Checks if t1 and t2 have compatible orientations i.e. if t1 and t2 can be part of the same surface without conflict in the surface normal orientation.

t1 :

a GtsTriangle.

t2 :

a GtsTriangle.

e :

a GtsEdge used by both t1 and t2.

Returns :

TRUE if t1 and t2 are compatible, FALSE otherwise.


gts_triangle_area ()

gdouble             gts_triangle_area                   (GtsTriangle *t);

t :

a GtsTriangle.

Returns :

the area of the triangle t.


gts_triangle_perimeter ()

gdouble             gts_triangle_perimeter              (GtsTriangle *t);

t :

a GtsTriangle.

Returns :

the perimeter of the triangle t.


gts_triangle_quality ()

gdouble             gts_triangle_quality                (GtsTriangle *t);

The quality of a triangle is defined as the ratio of the square root of its surface area to its perimeter relative to this same ratio for an equilateral triangle with the same area. The quality is then one for an equilateral triangle and tends to zero for a very stretched triangle.

t :

a GtsTriangle.

Returns :

the quality of the triangle t.


gts_triangle_normal ()

void                gts_triangle_normal                 (GtsTriangle *t,
                                                         gdouble *x,
                                                         gdouble *y,
                                                         gdouble *z);

Computes the coordinates of the oriented normal of t as the cross-product of two edges, using the left-hand rule. The normal is not normalized. If this triangle is part of a closed and oriented surface, the normal points to the outside of the surface.

t :

a GtsTriangle.

x :

the x coordinate of the normal.

y :

the y coordinate of the normal.

z :

the z coordinate of the normal.


gts_triangle_orientation ()

gdouble             gts_triangle_orientation            (GtsTriangle *t);

Checks for the orientation of the plane (x,y) projection of a triangle. See gts_point_orientation() for details. This function is geometrically robust.

t :

a GtsTriangle.

Returns :

a number depending on the orientation of the vertices of t.


gts_triangle_revert ()

void                gts_triangle_revert                 (GtsTriangle *t);

Changes the orientation of triangle t, turning it inside out.

t :

a GtsTriangle.


gts_triangles_from_edges ()

GSList *            gts_triangles_from_edges            (GSList *edges);

Builds a list of unique triangles which have one of their edges in edges.

edges :

a list of GtsEdge.

Returns :

the list of triangles.


gts_triangle_vertices_edges ()

void                gts_triangle_vertices_edges         (GtsTriangle *t,
                                                         GtsEdge *e,
                                                         GtsVertex **v1,
                                                         GtsVertex **v2,
                                                         GtsVertex **v3,
                                                         GtsEdge **e1,
                                                         GtsEdge **e2,
                                                         GtsEdge **e3);

Given t and e, returns v1, v2, v3, e1, e2 and e3. e1 has v1 and v2 as vertices, e2 has v2 and v3 as vertices and e3 has v3 and v1 as vertices. v1, v2 and v3 respects the orientation of t. If e is not NULL, e1 and e are identical.

t :

a GtsTriangle.

e :

a GtsEdge belonging to the edges of t or NULL.

v1 :

a GtsVertex used by t.

v2 :

a GtsVertex used by t.

v3 :

a GtsVertex used by t.

e1 :

a GtsEdge used by t.

e2 :

a GtsEdge used by t.

e3 :

a GtsEdge used by t.


gts_triangle_enclosing ()

GtsTriangle *       gts_triangle_enclosing              (GtsTriangleClass *klass,
                                                         GSList *points,
                                                         gdouble scale);

Builds a new triangle (including new vertices and edges) enclosing the plane projection of all the points in points. This triangle is equilateral and encloses a rectangle defined by the maximum and minimum x and y coordinates of the points. scale is an homothetic scaling factor. If equal to one, the triangle encloses exactly the enclosing rectangle.

klass :

the class of the new triangle.

points :

a list of GtsPoint.

scale :

a scaling factor (must be larger than one).

Returns :

a new GtsTriangle.


gts_triangle_neighbor_number ()

guint               gts_triangle_neighbor_number        (GtsTriangle *t);

t :

a GtsTriangle.

Returns :

the number of triangles neighbors of t.


gts_triangle_neighbors ()

GSList *            gts_triangle_neighbors              (GtsTriangle *t);

t :

a GtsTriangle.

Returns :

a list of GtsTriangle neighbors of t.


gts_triangles_common_edge ()

GtsEdge *           gts_triangles_common_edge           (GtsTriangle *t1,
                                                         GtsTriangle *t2);

t1 :

a GtsTriangle.

t2 :

a GtsTriangle.

Returns :

a GtsEdge common to both t1 and t2 or NULL if t1 and t2 do not share any edge.


gts_triangle_is_duplicate ()

GtsTriangle *       gts_triangle_is_duplicate           (GtsTriangle *t);

t :

a GtsTriangle.

Returns :

a GtsTriangle different from t but sharing all its edges with t or NULL if there is none.


gts_triangle_use_edges ()

GtsTriangle *       gts_triangle_use_edges              (GtsEdge *e1,
                                                         GtsEdge *e2,
                                                         GtsEdge *e3);

e1 :

a GtsEdge.

e2 :

a GtsEdge.

e3 :

a GtsEdge.

Returns :

a GtsTriangle having e1, e2 and e3 as edges or NULL if e1, e2 and e3 are not part of any triangle.


gts_triangle_is_ok ()

gboolean            gts_triangle_is_ok                  (GtsTriangle *t);

t :

a GtsTriangle.

Returns :

TRUE if t is a non-degenerate, non-duplicate triangle, FALSE otherwise.


gts_triangle_vertices ()

void                gts_triangle_vertices               (GtsTriangle *t,
                                                         GtsVertex **v1,
                                                         GtsVertex **v2,
                                                         GtsVertex **v3);

Fills v1, v2 and v3 with the oriented set of vertices, summits of t.

t :

a GtsTriangle.

v1 :

a pointer on a GtsVertex.

v2 :

a pointer on a GtsVertex.

v3 :

a pointer on a GtsVertex.


gts_triangle_circumcircle_center ()

GtsPoint *          gts_triangle_circumcircle_center    (GtsTriangle *t,
                                                         GtsPointClass *point_class);

t :

a GtsTriangle.

point_class :

a GtsPointClass.

Returns :

a new GtsPoint, center of the circumscribing circle of t or NULL if the circumscribing circle is not defined.


gts_triangles_are_folded ()

gboolean            gts_triangles_are_folded            (GSList *triangles,
                                                         GtsVertex *A,
                                                         GtsVertex *B,
                                                         gdouble max);

Given a list of triangles sharing A and B as vertices, checks if any two triangles in the list make an angle larger than a given value defined by max.

triangles :

a list of GtsTriangle.

A :

a GtsVertex.

B :

another GtsVertex.

max :

the maximum value of the square of the cosine of the angle between two triangles.

Returns :

TRUE if any pair of triangles in triangles makes an angle larger than the maximum value, FALSE otherwise.


gts_triangle_is_stabbed ()

GtsObject *         gts_triangle_is_stabbed             (GtsTriangle *t,
                                                         GtsPoint *p,
                                                         gdouble *orientation);

t :

a GtsTriangle.

p :

a GtsPoint.

orientation :

a pointer or NULL.

Returns :

one of the vertices of t, one of the edges of t or t if any of these are stabbed by the ray starting at p (included) and ending at (p->x, p->y, +infty), NULL otherwise. If the ray is contained in the plane of the triangle NULL is also returned. If orientation is not NULL, it is set to the value of the orientation of p relative to t (as given by gts_point_orientation_3d()).


gts_triangle_interpolate_height ()

void                gts_triangle_interpolate_height     (GtsTriangle *t,
                                                         GtsPoint *p);

Fills the z-coordinate of point p belonging to the plane projection of triangle t with the linearly interpolated value of the z-coordinates of the vertices of t.

t :

a GtsTriangle.

p :

a GtsPoint.


GTS_IS_FACE()

#define             GTS_IS_FACE(obj)

obj :


GTS_FACE()

#define             GTS_FACE(obj)

obj :


GTS_FACE_CLASS()

#define             GTS_FACE_CLASS(klass)

klass :


GtsFace

typedef struct {
  GtsTriangle triangle;

  GSList * surfaces;
} GtsFace;


gts_face_class ()

GtsFaceClass *      gts_face_class                      (void);

Returns :

the GtsFaceClass.


gts_face_new ()

GtsFace *           gts_face_new                        (GtsFaceClass *klass,
                                                         GtsEdge *e1,
                                                         GtsEdge *e2,
                                                         GtsEdge *e3);

klass :

a GtsFaceClass.

e1 :

a GtsEdge.

e2 :

a GtsEdge.

e3 :

a GtsEdge.

Returns :

a new GtsFace using e1, e2 and e3 as edges.


gts_face_has_parent_surface ()

gboolean            gts_face_has_parent_surface         (GtsFace *f,
                                                         GtsSurface *s);

f :

a GtsFace.

s :

a GtsSurface.

Returns :

TRUE if f belongs to s, FALSE otherwise.


gts_faces_from_edges ()

GSList *            gts_faces_from_edges                (GSList *edges,
                                                         GtsSurface *s);

Builds a list of unique faces which belong to s and have one of their edges in edges.

edges :

a list of GtsEdge.

s :

a GtsSurface or NULL.

Returns :

the list of faces.


gts_face_neighbor_number ()

guint               gts_face_neighbor_number            (GtsFace *f,
                                                         GtsSurface *s);

f :

a GtsFace.

s :

a GtsSurface or NULL.

Returns :

the number of faces neighbors of f and belonging to s.


gts_face_neighbors ()

GSList *            gts_face_neighbors                  (GtsFace *f,
                                                         GtsSurface *s);

f :

a GtsFace.

s :

a GtsSurface or NULL.

Returns :

a list of unique GtsFace neighbors of f and belonging to s.


gts_face_foreach_neighbor ()

void                gts_face_foreach_neighbor           (GtsFace *f,
                                                         GtsSurface *s,
                                                         GtsFunc func,
                                                         gpointer data);

Calls func for each neighbor of f belonging to s (if not NULL).

f :

a GtsFace.

s :

a GtsSurface or NULL.

func :

a GtsFunc.

data :

user data to pass to func.


gts_face_is_compatible ()

gboolean            gts_face_is_compatible              (GtsFace *f,
                                                         GtsSurface *s);

f :

a GtsFace.

s :

a GtsSurface.

Returns :

TRUE if f is compatible with all its neighbors belonging to s, FALSE otherwise.


gts_vector_cross()

#define             gts_vector_cross(C,A,B)

C :

A :

B :


gts_vector_init()

#define             gts_vector_init(v, p1, p2)

v :

p1 :

p2 :


gts_vector_scalar()

#define             gts_vector_scalar(v1, v2)

v1 :

v2 :


gts_vector_norm()

#define             gts_vector_norm(v)

v :


gts_vector_normalize()

#define             gts_vector_normalize(v)

v :


gts_matrix_new ()

GtsMatrix *         gts_matrix_new                      (gdouble a00,
                                                         gdouble a01,
                                                         gdouble a02,
                                                         gdouble a03,
                                                         gdouble a10,
                                                         gdouble a11,
                                                         gdouble a12,
                                                         gdouble a13,
                                                         gdouble a20,
                                                         gdouble a21,
                                                         gdouble a22,
                                                         gdouble a23,
                                                         gdouble a30,
                                                         gdouble a31,
                                                         gdouble a32,
                                                         gdouble a33);

Allocates memory and initializes a new GtsMatrix.

a00 :

element [0][0].

a01 :

element [0][1].

a02 :

element [0][2].

a03 :

element [0][3].

a10 :

element [1][0].

a11 :

element [1][1].

a12 :

element [1][2].

a13 :

element [1][3].

a20 :

element [2][0].

a21 :

element [2][1].

a22 :

element [2][2].

a23 :

element [2][3].

a30 :

element [3][0].

a31 :

element [3][1].

a32 :

element [3][2].

a33 :

element [3][3].

Returns :

a pointer to the newly created GtsMatrix.


gts_matrix_assign ()

void                gts_matrix_assign                   (GtsMatrix *m,
                                                         gdouble a00,
                                                         gdouble a01,
                                                         gdouble a02,
                                                         gdouble a03,
                                                         gdouble a10,
                                                         gdouble a11,
                                                         gdouble a12,
                                                         gdouble a13,
                                                         gdouble a20,
                                                         gdouble a21,
                                                         gdouble a22,
                                                         gdouble a23,
                                                         gdouble a30,
                                                         gdouble a31,
                                                         gdouble a32,
                                                         gdouble a33);

Set values of matrix elements.

m :

a GtsMatrix.

a00 :

element [0][0].

a01 :

element [0][1].

a02 :

element [0][2].

a03 :

element [0][3].

a10 :

element [1][0].

a11 :

element [1][1].

a12 :

element [1][2].

a13 :

element [1][3].

a20 :

element [2][0].

a21 :

element [2][1].

a22 :

element [2][2].

a23 :

element [2][3].

a30 :

element [3][0].

a31 :

element [3][1].

a32 :

element [3][2].

a33 :

element [3][3].


gts_matrix_projection ()

GtsMatrix *         gts_matrix_projection               (GtsTriangle *t);

Creates a new GtsMatrix representing the projection onto a plane of normal given by t.

t :

a GtsTriangle.

Returns :

a pointer to the newly created GtsMatrix.


gts_matrix_transpose ()

GtsMatrix *         gts_matrix_transpose                (GtsMatrix *m);

m :

a GtsMatrix.

Returns :

a pointer to a newly created GtsMatrix transposed of m.


gts_matrix_determinant ()

gdouble             gts_matrix_determinant              (GtsMatrix *m);

m :

a GtsMatrix.

Returns :

the value of det(m).


gts_matrix_inverse ()

GtsMatrix *         gts_matrix_inverse                  (GtsMatrix *m);

m :

a GtsMatrix.

Returns :

a pointer to a newly created GtsMatrix inverse of m or NULL if m is not invertible.


gts_matrix3_inverse ()

GtsMatrix *         gts_matrix3_inverse                 (GtsMatrix *m);

m :

a 3x3 GtsMatrix.

Returns :

a pointer to a newly created 3x3 GtsMatrix inverse of m or NULL if m is not invertible.


gts_matrix_print ()

void                gts_matrix_print                    (GtsMatrix *m,
                                                         FILE *fptr);

Print m to file fptr.

m :

a GtsMatrix.

fptr :

a file descriptor.


gts_matrix_compatible_row ()

guint               gts_matrix_compatible_row           (GtsMatrix *A,
                                                         GtsVector b,
                                                         guint n,
                                                         GtsVector A1,
                                                         gdouble b1);

Given a system of n constraints A.x=b adds to it the compatible constraints defined by A1.x=b1. The compatibility is determined by insuring that the resulting system is well-conditioned (see Lindstrom and Turk (1998, 1999)).

A :

a GtsMatrix.

b :

a GtsVector.

n :

the number of previous constraints of A.x=b.

A1 :

a GtsMatrix.

b1 :

a GtsVector.

Returns :

the number of constraints of the resulting system.


gts_matrix_quadratic_optimization ()

guint               gts_matrix_quadratic_optimization   (GtsMatrix *A,
                                                         GtsVector b,
                                                         guint n,
                                                         GtsMatrix *H,
                                                         GtsVector c);

Solve a quadratic optimization problem: Given a quadratic objective function f which can be written as: f(x) = x^t.H.x + c^t.x + k, where H is the symmetric positive definite Hessian of f and k is a constant, find the minimum of f subject to the set of n prior linear constraints, defined by the first n rows of A and b (A.x = b). The new constraints given by the minimization are added to A and b only if they are linearly independent as determined by gts_matrix_compatible_row().

A :

a GtsMatrix.

b :

a GtsVector.

n :

the number of constraints (must be smaller than 3).

H :

a symmetric positive definite Hessian.

c :

a GtsVector.

Returns :

the new number of constraints defined by A and b.


gts_matrix_product ()

GtsMatrix *         gts_matrix_product                  (GtsMatrix *m1,
                                                         GtsMatrix *m2);

m1 :

a GtsMatrix.

m2 :

another GtsMatrix.

Returns :

a new GtsMatrix, product of m1 and m2.


gts_matrix_zero ()

GtsMatrix *         gts_matrix_zero                     (GtsMatrix *m);

Initializes m to zeros. Allocates a matrix if m is NULL.

m :

a GtsMatrix or $NULL.

Returns :

the zero'ed matrix.


gts_matrix_identity ()

GtsMatrix *         gts_matrix_identity                 (GtsMatrix *m);

Initializes m to an identity matrix. Allocates a matrix if m is NULL.

m :

a GtsMatrix or NULL.

Returns :

the identity matrix.


gts_matrix_scale ()

GtsMatrix *         gts_matrix_scale                    (GtsMatrix *m,
                                                         GtsVector s);

Initializes m to a scaling matrix for s. Allocates a matrix if m is NULL.

m :

a GtsMatrix or NULL.

s :

the scaling vector.

Returns :

the scaling matrix.


gts_matrix_translate ()

GtsMatrix *         gts_matrix_translate                (GtsMatrix *m,
                                                         GtsVector t);

Initializes m to a translation matrix for t. Allocates a new matrix if m is NULL.

m :

a GtsMatrix or NULL.

t :

the translation vector.

Returns :

the translation matix.


gts_matrix_rotate ()

GtsMatrix *         gts_matrix_rotate                   (GtsMatrix *m,
                                                         GtsVector r,
                                                         gdouble angle);

Initializes m to a rotation matrix around r by angle. Allocates a new matrix if m is NULL.

m :

a GtsMatrix or NULL.

r :

the rotation axis.

angle :

the angle (in radians) to rotate by.

Returns :

the rotation matrix.


gts_matrix_destroy ()

void                gts_matrix_destroy                  (GtsMatrix *m);

Free all the memory allocated for m.

m :

a GtsMatrix.


gts_vector_print ()

void                gts_vector_print                    (GtsVector v,
                                                         FILE *fptr);

Print s to file fptr.

v :

a GtsVector.

fptr :

a file descriptor.


gts_vector4_print ()

void                gts_vector4_print                   (GtsVector4 v,
                                                         FILE *fptr);

Print v to file fptr.

v :

a GtsVector4.

fptr :

a file descriptor.


gts_kdtree_destroy()

#define       gts_kdtree_destroy(tree)               g_node_destroy(tree)

tree :


gts_kdtree_new ()

GNode *             gts_kdtree_new                      (GPtrArray *points,
                                                         int (compareconst void *,const void *) ());

Note that the order of the points in array points is modified by this function.

points :

an array of GtsPoint.

compare :

always NULL.

Returns :

a new 3D tree for points.


gts_kdtree_range ()

GSList *            gts_kdtree_range                    (GNode *tree,
                                                         GtsBBox *bbox,
                                                         int (compareconst void *,const void *) ());

tree :

a 3D tree.

bbox :

a GtsBBox.

compare :

always NULL.

Returns :

a list of GtsPoint belonging to tree which are inside bbox.


GtsBBTreeTraverseFunc ()

void                (*GtsBBTreeTraverseFunc)            (GtsBBox *bb1,
                                                         GtsBBox *bb2,
                                                         gpointer data);

User function called for each pair of overlapping bounding boxes. See gts_bb_tree_traverse_overlapping().

bb1 :

a GtsBBox.

bb2 :

another GtsBBox.

data :

user data passed to the function.


GtsBBoxDistFunc ()

gdouble             (*GtsBBoxDistFunc)                  (GtsPoint *p,
                                                         gpointer bounded);

User function returning the (minimum) distance between the object defined by bounded and point p.

p :

a GtsPoint.

bounded :

an object bounded by a GtsBBox.

Returns :

the distance between p and bounded.


GtsBBoxClosestFunc ()

GtsPoint *          (*GtsBBoxClosestFunc)               (GtsPoint *p,
                                                         gpointer bounded);

User function returning a GtsPoint belonging to the object defined by bounded and closest to p.

p :

a GtsPoint.

bounded :

an object bounded by a GtsBBox.

Returns :

a GtsPoint.


GTS_IS_BBOX()

#define             GTS_IS_BBOX(obj)

Evaluates to TRUE if obj is a GtsBBox, FALSE otherwise.

obj :

a GtsObject.


GTS_BBOX()

#define             GTS_BBOX(obj)

Casts obj to GtsBBox.

obj :

a GtsObject.


GTS_BBOX_CLASS()

#define             GTS_BBOX_CLASS(klass)

Casts klass to GtsBBoxClass.

klass :

a descendant of GtsBBoxClass.


GtsBBox

typedef struct {
  GtsObject object;
  gpointer bounded;
  gdouble x1, y1, z1;
  gdouble x2, y2, z2;
} GtsBBox;


gts_bbox_class ()

GtsBBoxClass *      gts_bbox_class                      (void);

Returns :

the GtsBBoxClass.


gts_bbox_new ()

GtsBBox *           gts_bbox_new                        (GtsBBoxClass *klass,
                                                         gpointer bounded,
                                                         gdouble x1,
                                                         gdouble y1,
                                                         gdouble z1,
                                                         gdouble x2,
                                                         gdouble y2,
                                                         gdouble z2);

klass :

a GtsBBoxClass.

bounded :

the object to be bounded.

x1 :

x-coordinate of the lower left corner.

y1 :

y-coordinate of the lower left corner.

z1 :

z-coordinate of the lower left corner.

x2 :

x-coordinate of the upper right corner.

y2 :

y-coordinate of the upper right corner.

z2 :

z-coordinate of the upper right corner.

Returns :

a new GtsBBox.


gts_bbox_set ()

void                gts_bbox_set                        (GtsBBox *bbox,
                                                         gpointer bounded,
                                                         gdouble x1,
                                                         gdouble y1,
                                                         gdouble z1,
                                                         gdouble x2,
                                                         gdouble y2,
                                                         gdouble z2);

Sets fields of bbox.

bbox :

a GtsBBox.

bounded :

the object to be bounded.

x1 :

x-coordinate of the lower left corner.

y1 :

y-coordinate of the lower left corner.

z1 :

z-coordinate of the lower left corner.

x2 :

x-coordinate of the upper right corner.

y2 :

y-coordinate of the upper right corner.

z2 :

z-coordinate of the upper right corner.


gts_bbox_segment ()

GtsBBox *           gts_bbox_segment                    (GtsBBoxClass *klass,
                                                         GtsSegment *s);

klass :

a GtsBBoxClass.

s :

a GtsSegment.

Returns :

a new GtsBBox bounding box of s.


gts_bbox_triangle ()

GtsBBox *           gts_bbox_triangle                   (GtsBBoxClass *klass,
                                                         GtsTriangle *t);

klass :

a GtsBBoxClass.

t :

a GtsTriangle.

Returns :

a new GtsBBox bounding box of t.


gts_bbox_surface ()

GtsBBox *           gts_bbox_surface                    (GtsBBoxClass *klass,
                                                         GtsSurface *surface);

klass :

a GtsBBoxClass.

surface :

a GtsSurface.

Returns :

a new GtsBBox bounding box of surface.


gts_bbox_bboxes ()

GtsBBox *           gts_bbox_bboxes                     (GtsBBoxClass *klass,
                                                         GSList *bboxes);

klass :

a GtsBBoxClass.

bboxes :

a list of GtsBBox.

Returns :

a new GtsBBox bounding box of all the bounding boxes in bboxes.


gts_bbox_points ()

GtsBBox *           gts_bbox_points                     (GtsBBoxClass *klass,
                                                         GSList *points);

klass :

a GtsBBoxClass.

points :

a list of GtsPoint.

Returns :

a new GtsBBox bounding box of points.


gts_bbox_point_is_inside()

#define             gts_bbox_point_is_inside(bbox, p)

Evaluates to TRUE if p is inside (or on the boundary) of bbox, FALSE otherwise.

bbox :

a GtsBBox.

p :

a GtsPoint.


gts_bboxes_are_overlapping ()

gboolean            gts_bboxes_are_overlapping          (GtsBBox *bb1,
                                                         GtsBBox *bb2);

bb1 :

a GtsBBox.

bb2 :

a GtsBBox.

Returns :

TRUE if the bounding boxes bb1 and bb2 are overlapping (including just touching), FALSE otherwise.


gts_bbox_draw ()

void                gts_bbox_draw                       (GtsBBox *bb,
                                                         FILE *fptr);

Writes in file fptr an OOGL (Geomview) description of bb.

bb :

a GtsBBox.

fptr :

a file pointer.


gts_bbox_diagonal2 ()

gdouble             gts_bbox_diagonal2                  (GtsBBox *bb);

bb :

a GtsBBox.

Returns :

the squared length of the diagonal of bb.


gts_bbox_point_distance2 ()

void                gts_bbox_point_distance2            (GtsBBox *bb,
                                                         GtsPoint *p,
                                                         gdouble *min,
                                                         gdouble *max);

Sets min and max to lower and upper bounds for the square of the Euclidean distance between the object contained in bb and p. For these bounds to make any sense the bounding box must be "tight" i.e. each of the 6 faces of the box must at least be touched by one point of the bounded object.

bb :

a GtsBBox.

p :

a GtsPoint.

min :

a pointer on a gdouble.

max :

a pointer on a gdouble.


gts_bbox_is_stabbed ()

gboolean            gts_bbox_is_stabbed                 (GtsBBox *bb,
                                                         GtsPoint *p);

bb :

a GtsBBox.

p :

a GtsPoint.

Returns :

TRUE if the ray starting at p and ending at (+infty, p->y, p->z) intersects with bb, FALSE otherwise.


gts_bbox_overlaps_triangle ()

gboolean            gts_bbox_overlaps_triangle          (GtsBBox *bb,
                                                         GtsTriangle *t);

This is a wrapper around the fast overlap test of Tomas Akenine-Moller (http://www.cs.lth.se/home/Tomas_Akenine_Moller/).

bb :

a GtsBBox.

t :

a GtsTriangle.

Returns :

TRUE if bb overlaps with t, FALSE otherwise.


gts_bbox_overlaps_segment ()

gboolean            gts_bbox_overlaps_segment           (GtsBBox *bb,
                                                         GtsSegment *s);

This functions uses gts_bbox_overlaps_triangle() with a degenerate triangle.

bb :

a GtsBBox.

s :

a GtsSegment.

Returns :

TRUE if bb overlaps with s, FALSE otherwise.


gts_bb_tree_new ()

GNode *             gts_bb_tree_new                     (GSList *bboxes);

Builds a new hierarchy of bounding boxes for bboxes. At each level, the GNode->data field contains a GtsBBox bounding box of all the children. The tree is binary and is built by repeatedly cutting in two approximately equal halves the bounding boxes at each level until a leaf node (i.e. a bounding box given in bboxes) is reached. In order to minimize the depth of the tree, the cutting direction is always chosen as perpendicular to the longest dimension of the bounding box.

bboxes :

a list of GtsBBox.

Returns :

a new hierarchy of bounding boxes.


gts_bb_tree_surface ()

GNode *             gts_bb_tree_surface                 (GtsSurface *s);

s :

a GtsSurface.

Returns :

a new hierarchy of bounding boxes bounding the faces of s.


gts_bb_tree_stabbed ()

GSList *            gts_bb_tree_stabbed                 (GNode *tree,
                                                         GtsPoint *p);

tree :

a bounding box tree.

p :

a GtsPoint.

Returns :

a list of bounding boxes, leaves of tree which are stabbed by the ray defined by p (see gts_bbox_is_stabbed()).


gts_bb_tree_overlap ()

GSList *            gts_bb_tree_overlap                 (GNode *tree,
                                                         GtsBBox *bbox);

tree :

a bounding box tree.

bbox :

a GtsBBox.

Returns :

a list of bounding boxes, leaves of tree which overlap bbox.


gts_bb_tree_is_overlapping ()

gboolean            gts_bb_tree_is_overlapping          (GNode *tree,
                                                         GtsBBox *bbox);

tree :

a bounding box tree.

bbox :

a GtsBBox.

Returns :

TRUE if any leaf of tree overlaps bbox, FALSE otherwise.


gts_bb_tree_traverse_overlapping ()

void                gts_bb_tree_traverse_overlapping    (GNode *tree1,
                                                         GNode *tree2,
                                                         GtsBBTreeTraverseFunc func,
                                                         gpointer data);

Calls func for each overlapping pair of leaves of tree1 and tree2.

tree1 :

a bounding box tree.

tree2 :

a bounding box tree.

func :

a GtsBBTreeTraverseFunc.

data :

user data to be passed to func.


gts_bb_tree_draw ()

void                gts_bb_tree_draw                    (GNode *tree,
                                                         guint depth,
                                                         FILE *fptr);

Write in fptr an OOGL (Geomview) description of tree for the depth specified by depth.

tree :

a bounding box tree.

depth :

a specified depth.

fptr :

a file pointer.


gts_bb_tree_point_closest_bboxes ()

GSList *            gts_bb_tree_point_closest_bboxes    (GNode *tree,
                                                         GtsPoint *p);

tree :

a bounding box tree.

p :

a GtsPoint.

Returns :

a list of GtsBBox. One of the bounding boxes is assured to contain the object of tree closest to p.


gts_bb_tree_point_distance ()

gdouble             gts_bb_tree_point_distance          (GNode *tree,
                                                         GtsPoint *p,
                                                         GtsBBoxDistFunc distance,
                                                         GtsBBox **bbox);

tree :

a bounding box tree.

p :

a GtsPoint.

distance :

a GtsBBoxDistFunc.

bbox :

if not NULL is set to the bounding box containing the closest object.

Returns :

the distance as evaluated by distance between p and the closest object in tree.


gts_bb_tree_point_closest ()

GtsPoint *          gts_bb_tree_point_closest           (GNode *tree,
                                                         GtsPoint *p,
                                                         GtsBBoxClosestFunc closest,
                                                         gdouble *distance);

tree :

a bounding box tree.

p :

a GtsPoint.

closest :

a GtsBBoxClosestFunc.

distance :

if not NULL is set to the distance between p and the new GtsPoint.

Returns :

a new GtsPoint, closest point to p and belonging to an object of tree.


gts_bb_tree_segment_distance ()

void                gts_bb_tree_segment_distance        (GNode *tree,
                                                         GtsSegment *s,
                                                         GtsBBoxDistFunc distance,
                                                         gdouble delta,
                                                         GtsRange *range);

Given a segment s, points are sampled regularly on its length using delta as increment. The distance from each of these points to the closest object of tree is computed using distance and the gts_bb_tree_point_distance() function. The fields of range are filled with the number of points sampled, the minimum, average and maximum value and the standard deviation.

tree :

a bounding box tree.

s :

a GtsSegment.

distance :

a GtsBBoxDistFunc.

delta :

spatial scale of the sampling to be used.

range :

a GtsRange to be filled with the results.


gts_bb_tree_triangle_distance ()

void                gts_bb_tree_triangle_distance       (GNode *tree,
                                                         GtsTriangle *t,
                                                         GtsBBoxDistFunc distance,
                                                         gdouble delta,
                                                         GtsRange *range);

Given a triangle t, points are sampled regularly on its surface using delta as increment. The distance from each of these points to the closest object of tree is computed using distance and the gts_bb_tree_point_distance() function. The fields of range are filled with the number of points sampled, the minimum, average and maximum value and the standard deviation.

tree :

a bounding box tree.

t :

a GtsTriangle.

distance :

a GtsBBoxDistFunc.

delta :

spatial scale of the sampling to be used.

range :

a GtsRange to be filled with the results.


gts_bb_tree_surface_distance ()

void                gts_bb_tree_surface_distance        (GNode *tree,
                                                         GtsSurface *s,
                                                         GtsBBoxDistFunc distance,
                                                         gdouble delta,
                                                         GtsRange *range);

Calls gts_bb_tree_triangle_distance() for each face of s. The fields of range are filled with the minimum, maximum and average distance. The average distance is defined as the sum of the average distances for each triangle weighthed by their area and divided by the total area of the surface. The standard deviation is defined accordingly. The n field of range is filled with the number of sampled points used.

tree :

a bounding box tree.

s :

a GtsSurface.

distance :

a GtsBBoxDistFunc.

delta :

a sampling increment defined as the percentage of the diagonal of the root bounding box of tree.

range :

a GtsRange to be filled with the results.


gts_bb_tree_surface_boundary_distance ()

void                gts_bb_tree_surface_boundary_distance
                                                        (GNode *tree,
                                                         GtsSurface *s,
                                                         GtsBBoxDistFunc distance,
                                                         gdouble delta,
                                                         GtsRange *range);

Calls gts_bb_tree_segment_distance() for each edge boundary of s. The fields of range are filled with the minimum, maximum and average distance. The average distance is defined as the sum of the average distances for each boundary edge weighthed by their length and divided by the total length of the boundaries. The standard deviation is defined accordingly. The n field of range is filled with the number of sampled points used.

tree :

a bounding box tree.

s :

a GtsSurface.

distance :

a GtsBBoxDistFunc.

delta :

a sampling increment defined as the percentage of the diagonal of the root bounding box of tree.

range :

a GtsRange to be filled with the results.


gts_bb_tree_destroy ()

void                gts_bb_tree_destroy                 (GNode *tree,
                                                         gboolean free_leaves);

Destroys all the bounding boxes created by tree and destroys the tree itself. If free_leaves is set to TRUE, destroys boxes given by the user when creating the tree (i.e. leaves of the tree).

tree :

a bounding box tree.

free_leaves :

if TRUE the bounding boxes given by the user are freed.


GtsSurfaceStats

typedef struct {
  guint n_faces;
  guint n_incompatible_faces;
  guint n_duplicate_faces;
  guint n_duplicate_edges;
  guint n_boundary_edges;
  guint n_non_manifold_edges;
  GtsRange edges_per_vertex, faces_per_edge;
  GtsSurface * parent;
} GtsSurfaceStats;


GtsSurfaceQualityStats

typedef struct {
  GtsRange face_quality;
  GtsRange face_area;
  GtsRange edge_length;
  GtsRange edge_angle;
  GtsSurface * parent;
} GtsSurfaceQualityStats;


GtsRefineFunc ()

GtsVertex *         (*GtsRefineFunc)                    (GtsEdge *e,
                                                         GtsVertexClass *klass,
                                                         gpointer data);

e :

klass :

data :

Returns :


GtsCoarsenFunc ()

GtsVertex *         (*GtsCoarsenFunc)                   (GtsEdge *e,
                                                         GtsVertexClass *klass,
                                                         gpointer data);

e :

klass :

data :

Returns :


GtsStopFunc ()

gboolean            (*GtsStopFunc)                      (gdouble cost,
                                                         guint nedge,
                                                         gpointer data);

cost :

nedge :

data :

Returns :


GtsSurface

typedef struct {
  GtsObject object;

#ifdef USE_SURFACE_BTREE
  GTree * faces;
#else /* not USE_SURFACE_BTREE */
  GHashTable * faces;
#endif /* not USE_SURFACE_BTREE */
  GtsFaceClass * face_class;
  GtsEdgeClass * edge_class;
  GtsVertexClass * vertex_class;
  gboolean keep_faces;
} GtsSurface;


GTS_IS_SURFACE()

#define             GTS_IS_SURFACE(obj)

obj :


GTS_SURFACE()

#define             GTS_SURFACE(obj)

obj :


GTS_SURFACE_CLASS()

#define             GTS_SURFACE_CLASS(klass)

klass :


gts_surface_class ()

GtsSurfaceClass *   gts_surface_class                   (void);

Returns :

the GtsSurfaceClass.


gts_surface_new ()

GtsSurface *        gts_surface_new                     (GtsSurfaceClass *klass,
                                                         GtsFaceClass *face_class,
                                                         GtsEdgeClass *edge_class,
                                                         GtsVertexClass *vertex_class);

klass :

a GtsSurfaceClass.

face_class :

a GtsFaceClass.

edge_class :

a GtsEdgeClass.

vertex_class :

a GtsVertexClass.

Returns :

a new empty GtsSurface.


gts_surface_add_face ()

void                gts_surface_add_face                (GtsSurface *s,
                                                         GtsFace *f);

Adds face f to surface s.

s :

a GtsSurface.

f :

a GtsFace.


gts_surface_remove_face ()

void                gts_surface_remove_face             (GtsSurface *s,
                                                         GtsFace *f);

Removes face f from surface s.

s :

a GtsSurface.

f :

a GtsFace.


gts_surface_read ()

guint               gts_surface_read                    (GtsSurface *surface,
                                                         GtsFile *f);

Add to surface the data read from f. The format of the file pointed to by f is as described in gts_surface_write().

surface :

a GtsSurface.

f :

a GtsFile.

Returns :

0 if successful or the line number at which the parsing stopped in case of error (in which case the error field of f is set to a description of the error which occured).


gts_surface_area ()

gdouble             gts_surface_area                    (GtsSurface *s);

s :

a GtsSurface.

Returns :

the area of s obtained as the sum of the signed areas of its faces.


gts_surface_stats ()

void                gts_surface_stats                   (GtsSurface *s,
                                                         GtsSurfaceStats *stats);

Fills stats with the statistics relevant to surface s.

s :

a GtsSurface.

stats :

a GtsSurfaceStats.


gts_surface_quality_stats ()

void                gts_surface_quality_stats           (GtsSurface *s,
                                                         GtsSurfaceQualityStats *stats);

Fills stats with quality statistics relevant to surface s.

s :

a GtsSurface.

stats :

a GtsSurfaceQualityStats.


gts_surface_print_stats ()

void                gts_surface_print_stats             (GtsSurface *s,
                                                         FILE *fptr);

Writes in the file pointed to by fptr the statistics for surface s.

s :

a GtsSurface.

fptr :

a file pointer.


gts_surface_write ()

void                gts_surface_write                   (GtsSurface *s,
                                                         FILE *fptr);

Writes in the file fptr an ASCII representation of s. The file format is as follows.

All the lines beginning with GTS_COMMENTS are ignored. The first line contains three unsigned integers separated by spaces. The first integer is the number of vertices, nv, the second is the number of edges, ne and the third is the number of faces, nf.

Follows nv lines containing the x, y and z coordinates of the vertices. Follows ne lines containing the two indices (starting from one) of the vertices of each edge. Follows nf lines containing the three ordered indices (also starting from one) of the edges of each face.

The format described above is the least common denominator to all GTS files. Consistent with an object-oriented approach, the GTS file format is extensible. Each of the lines of the file can be extended with user-specific attributes accessible through the read() and write() virtual methods of each of the objects written (surface, vertices, edges or faces). When read with different object classes, these extra attributes are just ignored.

s :

a GtsSurface.

fptr :

a file pointer.


gts_surface_write_oogl ()

void                gts_surface_write_oogl              (GtsSurface *s,
                                                         FILE *fptr);

Writes in the file fptr an OOGL (Geomview) representation of s.

s :

a GtsSurface.

fptr :

a file pointer.


gts_surface_write_vtk ()

void                gts_surface_write_vtk               (GtsSurface *s,
                                                         FILE *fptr);

Writes in the file fptr a VTK representation of s.

s :

a GtsSurface.

fptr :

a file pointer.


gts_surface_write_oogl_boundary ()

void                gts_surface_write_oogl_boundary     (GtsSurface *s,
                                                         FILE *fptr);

Writes in the file fptr an OOGL (Geomview) representation of the boundary of s.

s :

a GtsSurface.

fptr :

a file pointer.


gts_surface_foreach_vertex ()

void                gts_surface_foreach_vertex          (GtsSurface *s,
                                                         GtsFunc func,
                                                         gpointer data);

Calls func once for each vertex of s.

s :

a GtsSurface.

func :

a GtsFunc.

data :

user data to be passed to func.


gts_surface_foreach_edge ()

void                gts_surface_foreach_edge            (GtsSurface *s,
                                                         GtsFunc func,
                                                         gpointer data);

Calls func once for each edge of s.

s :

a GtsSurface.

func :

a GtsFunc.

data :

user data to be passed to func.


gts_surface_foreach_face ()

void                gts_surface_foreach_face            (GtsSurface *s,
                                                         GtsFunc func,
                                                         gpointer data);

Calls func once for each face of s.

s :

a GtsSurface.

func :

a GtsFunc.

data :

user data to be passed to func.


gts_surface_foreach_face_remove ()

guint               gts_surface_foreach_face_remove     (GtsSurface *s,
                                                         GtsFunc func,
                                                         gpointer data);

Calls func once for each face of s. If func returns TRUE the corresponding face is removed from s (and destroyed if it does not belong to any other surface and gts_allow_floating_faces is set to FALSE).

s :

a GtsSurface.

func :

a GtsFunc.

data :

user data to be passed to func.

Returns :

the number of faces removed from s.


GtsSurfaceTraverse

typedef struct _GtsSurfaceTraverse GtsSurfaceTraverse;


gts_surface_traverse_new ()

GtsSurfaceTraverse * gts_surface_traverse_new           (GtsSurface *s,
                                                         GtsFace *f);

s :

a GtsSurface.

f :

a GtsFace belonging to s.

Returns :

a new GtsSurfaceTraverse, initialized to start traversing from face f of surface s.


gts_surface_traverse_next ()

GtsFace *           gts_surface_traverse_next           (GtsSurfaceTraverse *t,
                                                         guint *level);

t :

a GtsSurfaceTraverse.

level :

a pointer to a guint or NULL.

Returns :

the next face of the traversal in breadth-first order or NULL if no faces are left. If level if not NULL, it is filled with the level of the returned face (0 for the initial face, 1 for its neighbors and so on).


gts_surface_traverse_destroy ()

void                gts_surface_traverse_destroy        (GtsSurfaceTraverse *t);

Frees all the memory allocated for t.

t :

a GtsSurfaceTraverse.


gts_surface_refine ()

void                gts_surface_refine                  (GtsSurface *surface,
                                                         GtsKeyFunc cost_func,
                                                         gpointer cost_data,
                                                         GtsRefineFunc refine_func,
                                                         gpointer refine_data,
                                                         GtsStopFunc stop_func,
                                                         gpointer stop_data);

Refine surface using a midvertex insertion technique. All the edges of surface are ordered according to cost_func. The edges are then processed in order until stop_func returns TRUE. Each edge is split in two and new edges and faces are created.

If cost_func is set to NULL, the edges are sorted according to their length squared (the longest is on top).

If refine_func is set to NULL gts_segment_midvertex() is used.

surface :

a GtsSurface.

cost_func :

a function returning the cost for a given edge.

cost_data :

user data to be passed to cost_func.

refine_func :

a GtsRefineFunc.

refine_data :

user data to be passed to refine_func.

stop_func :

a GtsStopFunc.

stop_data :

user data to be passed to stop_func.


gts_surface_coarsen ()

void                gts_surface_coarsen                 (GtsSurface *surface,
                                                         GtsKeyFunc cost_func,
                                                         gpointer cost_data,
                                                         GtsCoarsenFunc coarsen_func,
                                                         gpointer coarsen_data,
                                                         GtsStopFunc stop_func,
                                                         gpointer stop_data,
                                                         gdouble minangle);

The edges of surface are sorted according to cost_func to create a priority heap (a GtsEHeap). The edges are extracted in turn from the top of the heap and collapsed (i.e. the vertices are replaced by the vertex returned by the coarsen_func function) until the stop_func functions returns TRUE.

If cost_func is set to NULL, the edges are sorted according to their length squared (the shortest is on top).

If coarsen_func is set to NULL gts_segment_midvertex() is used.

The minimum angle is used to avoid introducing faces which would be folded.

surface :

a GtsSurface.

cost_func :

a function returning the cost for a given edge.

cost_data :

user data to be passed to cost_func.

coarsen_func :

a GtsCoarsenVertexFunc.

coarsen_data :

user data to be passed to coarsen_func.

stop_func :

a GtsStopFunc.

stop_data :

user data to be passed to stop_func.

minangle :

minimum angle between two neighboring triangles.


gts_coarsen_stop_number ()

gboolean            gts_coarsen_stop_number             (gdouble cost,
                                                         guint nedge,
                                                         guint *min_number);

This function is to be used as the stop_func argument of gts_surface_coarsen() or gts_psurface_new().

cost :

the cost of the edge collapse considered.

nedge :

the current number of edges of the surface being simplified.

min_number :

a pointer to the minimum number of edges desired for the surface being simplified.

Returns :

TRUE if the edge collapse would create a surface with a smaller number of edges than given by min_number, FALSE otherwise.


gts_coarsen_stop_cost ()

gboolean            gts_coarsen_stop_cost               (gdouble cost,
                                                         guint nedge,
                                                         gdouble *max_cost);

This function is to be used as the stop_func argument of gts_surface_coarsen() or gts_psurface_new().

cost :

the cost of the edge collapse considered.

nedge :

the current number of edges of the surface being simplified.

max_cost :

a pointer to the maximum cost allowed for an edge collapse.

Returns :

TRUE if the cost of the edge collapse considered is larger than given by max_cost, FALSE otherwise.


gts_surface_tessellate ()

void                gts_surface_tessellate              (GtsSurface *s,
                                                         GtsRefineFunc refine_func,
                                                         gpointer refine_data);

Tessellate each triangle of s with 4 triangles: the number of triangles is increased by a factor of 4. http://mathworld.wolfram.com/GeodesicDome.html

If refine_func is set to NULL a mid arc function is used: if the surface is a polyhedron with the unit sphere as circum sphere, then gts_surface_tessellate() corresponds to a geodesation step (see gts_surface_generate_sphere()).

s :

a GtsSurface.

refine_func :

a GtsRefineFunc.

refine_data :

user data to be passed to refine_func.


gts_surface_generate_sphere ()

GtsSurface *        gts_surface_generate_sphere         (GtsSurface *s,
                                                         guint geodesation_order);

Add a triangulated unit sphere generated by recursive subdivision to s. First approximation is an isocahedron; each level of refinement (geodesation_order) increases the number of triangles by a factor of 4. http://mathworld.wolfram.com/GeodesicDome.html

s :

a GtsSurface.

geodesation_order :

a guint.

Returns :

s.


gts_surface_copy ()

GtsSurface *        gts_surface_copy                    (GtsSurface *s1,
                                                         GtsSurface *s2);

Add a copy of all the faces, edges and vertices of s2 to s1.

s1 :

a GtsSurface.

s2 :

a GtsSurface.

Returns :

s1.


gts_surface_merge ()

void                gts_surface_merge                   (GtsSurface *s,
                                                         GtsSurface *with);

Adds all the faces of with which do not already belong to s to s.

s :

a GtsSurface.

with :

another GtsSurface.


gts_surface_is_manifold ()

gboolean            gts_surface_is_manifold             (GtsSurface *s);

s :

a GtsSurface.

Returns :

TRUE if the surface is a manifold, FALSE otherwise.


gts_surface_is_closed ()

gboolean            gts_surface_is_closed               (GtsSurface *s);

s :

a GtsSurface.

Returns :

TRUE if s is a closed surface, FALSE otherwise. Note that a closed surface is also a manifold.


gts_surface_is_orientable ()

gboolean            gts_surface_is_orientable           (GtsSurface *s);

s :

a GtsSurface.

Returns :

TRUE if all the faces of s have compatible orientation as checked by gts_faces_are_compatible(), FALSE otherwise. Note that an orientable surface is also a manifold.


gts_surface_volume ()

gdouble             gts_surface_volume                  (GtsSurface *s);

s :

a GtsSurface.

Returns :

the signed volume of the domain bounded by the surface s. It makes sense only if s is a closed and orientable manifold.


gts_surface_center_of_mass ()

gdouble             gts_surface_center_of_mass          (GtsSurface *s,
                                                         GtsVector cm);

Fills cm with the coordinates of the center of mass of s.

s :

a GtsSurface.

cm :

a GtsVector.

Returns :

the signed volume of the domain bounded by the surface s.


gts_surface_center_of_area ()

gdouble             gts_surface_center_of_area          (GtsSurface *s,
                                                         GtsVector cm);

Fills cm with the coordinates of the center of area of s.

s :

a GtsSurface.

cm :

a GtsVector.

Returns :

the area of surface s.


gts_surface_vertex_number ()

guint               gts_surface_vertex_number           (GtsSurface *s);

s :

a GtsSurface.

Returns :

the number of vertices of s.


gts_surface_edge_number ()

guint               gts_surface_edge_number             (GtsSurface *s);

s :

a GtsSurface.

Returns :

the number of edges of s.


gts_surface_face_number ()

guint               gts_surface_face_number             (GtsSurface *s);

s :

a GtsSurface.

Returns :

the number of faces of s


gts_surface_distance ()

void                gts_surface_distance                (GtsSurface *s1,
                                                         GtsSurface *s2,
                                                         gdouble delta,
                                                         GtsRange *face_range,
                                                         GtsRange *boundary_range);

Using the gts_bb_tree_surface_distance() and gts_bb_tree_surface_boundary_distance() functions fills face_range and boundary_range with the min, max and average Euclidean (minimum) distances between the faces of s1 and the faces of s2 and between the boundary edges of s1 and s2.

s1 :

a GtsSurface.

s2 :

a GtsSurface.

delta :

a spatial increment defined as the percentage of the diagonal of the bounding box of s2.

face_range :

a GtsRange.

boundary_range :

a GtsRange.


gts_surface_boundary ()

GSList *            gts_surface_boundary                (GtsSurface *surface);

surface :

a GtsSurface.

Returns :

a list of GtsEdge boundary of surface.


gts_surface_split ()

GSList *            gts_surface_split                   (GtsSurface *s);

Splits a surface into connected and manifold components.

s :

a GtsSurface.

Returns :

a list of new GtsSurface.


gts_vertex_mean_curvature_normal ()

gboolean            gts_vertex_mean_curvature_normal    (GtsVertex *v,
                                                         GtsSurface *s,
                                                         GtsVector Kh);

Computes the Discrete Mean Curvature Normal approximation at v. The mean curvature at v is half the magnitude of the vector Kh.

Note: the normal computed is not unit length, and may point either into or out of the surface, depending on the curvature at v. It is the responsibility of the caller of the function to use the mean curvature normal appropriately.

This approximation is from the paper: Discrete Differential-Geometry Operators for Triangulated 2-Manifolds Mark Meyer, Mathieu Desbrun, Peter Schroder, Alan H. Barr VisMath '02, Berlin (Germany) http://www-grail.usc.edu/pubs.html

v :

a GtsVertex.

s :

a GtsSurface.

Kh :

the Mean Curvature Normal at v.

Returns :

TRUE if the operator could be evaluated, FALSE if the evaluation failed for some reason (v is boundary or is the endpoint of a non-manifold edge.)


gts_vertex_gaussian_curvature ()

gboolean            gts_vertex_gaussian_curvature       (GtsVertex *v,
                                                         GtsSurface *s,
                                                         gdouble *Kg);

Computes the Discrete Gaussian Curvature approximation at v.

This approximation is from the paper: Discrete Differential-Geometry Operators for Triangulated 2-Manifolds Mark Meyer, Mathieu Desbrun, Peter Schroder, Alan H. Barr VisMath '02, Berlin (Germany) http://www-grail.usc.edu/pubs.html

v :

a GtsVertex.

s :

a GtsSurface.

Kg :

the Discrete Gaussian Curvature approximation at v.

Returns :

TRUE if the operator could be evaluated, FALSE if the evaluation failed for some reason (v is boundary or is the endpoint of a non-manifold edge.)


gts_vertex_principal_curvatures ()

void                gts_vertex_principal_curvatures     (gdouble Kh,
                                                         gdouble Kg,
                                                         gdouble *K1,
                                                         gdouble *K2);

Computes the principal curvatures at a point given the mean and Gaussian curvatures at that point.

The mean curvature can be computed as one-half the magnitude of the vector computed by gts_vertex_mean_curvature_normal().

The Gaussian curvature can be computed with gts_vertex_gaussian_curvature().

Kh :

mean curvature.

Kg :

Gaussian curvature.

K1 :

first principal curvature.

K2 :

second principal curvature.


gts_vertex_principal_directions ()

void                gts_vertex_principal_directions     (GtsVertex *v,
                                                         GtsSurface *s,
                                                         GtsVector Kh,
                                                         gdouble Kg,
                                                         GtsVector e1,
                                                         GtsVector e2);

Computes the principal curvature directions at a point given Kh and Kg, the mean curvature normal and Gaussian curvatures at that point, computed with gts_vertex_mean_curvature_normal() and gts_vertex_gaussian_curvature(), respectively.

Note that this computation is very approximate and tends to be unstable. Smoothing of the surface or the principal directions may be necessary to achieve reasonable results.

v :

a GtsVertex.

s :

a GtsSurface.

Kh :

mean curvature normal (a GtsVector).

Kg :

Gaussian curvature (a gdouble).

e1 :

first principal curvature direction (direction of largest curvature).

e2 :

second principal curvature direction.


GtsVolumeOptimizedParams

typedef struct {
  gdouble volume_weight;
  gdouble boundary_weight;
  gdouble shape_weight;
} GtsVolumeOptimizedParams;


gts_volume_optimized_vertex ()

GtsVertex *         gts_volume_optimized_vertex         (GtsEdge *edge,
                                                         GtsVertexClass *klass,
                                                         GtsVolumeOptimizedParams *params);

edge :

a GtsEdge.

klass :

a GtsVertexClass to be used for the new vertex.

params :

a GtsVolumeOptimizedParms.

Returns :

a GtsVertex which can be used to replace edge for an edge collapse operation. The position of the vertex is optimized in order to minimize the changes in area and volume for the surface using edge. The volume enclosed by the surface is locally preserved. For more details see "Fast and memory efficient polygonal simplification" (1998) and "Evaluation of memoryless simplification" (1999) by Lindstrom and Turk.


gts_volume_optimized_cost ()

gdouble             gts_volume_optimized_cost           (GtsEdge *e,
                                                         GtsVolumeOptimizedParams *params);

e :

a GtsEdge.

params :

a GtsVolumeOptimizedParams.

Returns :

the cost for the collapse of e as minimized by the function gts_volume_optimized_vertex().


gts_surface_intersection ()

GSList *            gts_surface_intersection            (GtsSurface *s1,
                                                         GtsSurface *s2,
                                                         GNode *faces_tree1,
                                                         GNode *faces_tree2);

s1 :

a GtsSurface.

s2 :

a GtsSurface.

faces_tree1 :

a bounding box tree (see gts_bb_tree_new()) for the faces of s1.

faces_tree2 :

a bounding box tree for the faces of s2.

Returns :

a list of GtsEdge defining the curve intersection of the two surfaces.


enum GtsBooleanOperation

typedef enum { GTS_1_OUT_2, 
	       GTS_1_IN_2, 
	       GTS_2_OUT_1, 
	       GTS_2_IN_1 }             GtsBooleanOperation;

GTS_1_OUT_2

identifies the part of the first surface which lies outside the second surface.

GTS_1_IN_2

identifies the part of the first surface which lies inside the second surface.

GTS_2_OUT_1

identifies the part of the second surface which lies outside the first surface.

GTS_2_IN_1

identifies the part of the second surface which lies inside the first surface.


GTS_IS_SURFACE_INTER()

#define             GTS_IS_SURFACE_INTER(obj)

Evaluates to TRUE if obj is a GtsSurfaceInter, FALSE otherwise.

obj :

a GtsObject.


GTS_SURFACE_INTER()

#define             GTS_SURFACE_INTER(obj)

Casts obj to GtsSurfaceInter.

obj :

a descendant of GtsSurfaceInter.


GTS_SURFACE_INTER_CLASS()

#define             GTS_SURFACE_INTER_CLASS(klass)

Casts klass to GtsSurfaceInterClass.

klass :

a descendant of GtsSurfaceInterClass.


GtsSurfaceInter

typedef struct {
  GtsObject object;

  GtsSurface * s1;
  GtsSurface * s2;
  GSList * edges;
} GtsSurfaceInter;


gts_surface_inter_class ()

GtsSurfaceInterClass * gts_surface_inter_class          (void);

Returns :

the GtsSurfaceInterClass.


gts_surface_inter_new ()

GtsSurfaceInter *   gts_surface_inter_new               (GtsSurfaceInterClass *klass,
                                                         GtsSurface *s1,
                                                         GtsSurface *s2,
                                                         GNode *faces_tree1,
                                                         GNode *faces_tree2,
                                                         gboolean is_open1,
                                                         gboolean is_open2);

When triangulating the cut faces, the new faces inherit the attributes of these original faces through their attributes() method.

klass :

a GtsSurfaceInterClass.

s1 :

a GtsSurface.

s2 :

a GtsSurface.

faces_tree1 :

a bounding box tree (see gts_bb_tree_new()) for the faces of s1.

faces_tree2 :

a bounding box tree for the faces of s2.

is_open1 :

whether s1 is an "open" surface.

is_open2 :

whether s2 is an "open" surface.

Returns :

a new GtsSurfaceInter describing the intersection of s1 and s2.


gts_surface_inter_check ()

gboolean            gts_surface_inter_check             (GtsSurfaceInter *si,
                                                         gboolean *closed);

si :

a GtsSurfaceInter.

closed :

is set to TRUE if si->edges is a closed curve, FALSE otherwise.

Returns :

TRUE if the curve described by si is an orientable manifold, FALSE otherwise.


gts_surface_inter_boolean ()

void                gts_surface_inter_boolean           (GtsSurfaceInter *si,
                                                         GtsSurface *surface,
                                                         GtsBooleanOperation op);

Adds to surface the part of the surface described by si and op.

si :

a GtsSurfaceInter.

surface :

a GtsSurface.

op :

a GtsBooleanOperation.


gts_surface_foreach_intersecting_face ()

gboolean            gts_surface_foreach_intersecting_face
                                                        (GtsSurface *s,
                                                         GtsBBTreeTraverseFunc func,
                                                         gpointer data);

Calls func for each intersecting pair of faces of s.

s :

a GtsSurface.

func :

a GtsBBTreeTraverseFunc.

data :

user data to pass to func.

Returns :

TRUE if func was called at least once, FALSE otherwise.


gts_surface_is_self_intersecting ()

GtsSurface *        gts_surface_is_self_intersecting    (GtsSurface *s);

s :

a GtsSurface.

Returns :

a new GtsSurface containing the faces of s which are self-intersecting or NULL if no faces of s are self-intersecting.


GtsHeap

typedef struct _GtsHeap GtsHeap;


gts_heap_new ()

GtsHeap *           gts_heap_new                        (GCompareFunc compare_func);

compare_func :

a GCompareFunc.

Returns :

a new GtsHeap using compare_func as a sorting function.


gts_heap_insert ()

void                gts_heap_insert                     (GtsHeap *heap,
                                                         gpointer p);

Inserts a new element p in the heap.

heap :

a GtsHeap.

p :

a pointer to add to the heap.


gts_heap_remove_top ()

gpointer            gts_heap_remove_top                 (GtsHeap *heap);

Removes the element at the top of the heap.

heap :

a GtsHeap.

Returns :

the element at the top of the heap.


gts_heap_top ()

gpointer            gts_heap_top                        (GtsHeap *heap);

heap :

a GtsHeap.

Returns :

the element at the top of the heap.


gts_heap_thaw ()

void                gts_heap_thaw                       (GtsHeap *heap);

If heap has been frozen previously using gts_heap_freeze(), reorder it in O(n) time and unfreeze it.

heap :

a GtsHeap.


gts_heap_foreach ()

void                gts_heap_foreach                    (GtsHeap *heap,
                                                         GFunc func,
                                                         gpointer user_data);

heap :

a GtsHeap.

func :

the function to call for each element in the heap.

user_data :

to pass to func.


gts_heap_freeze ()

void                gts_heap_freeze                     (GtsHeap *heap);

Freezes the heap. Any subsequent operation will not preserve the heap property. Used in conjunction with gts_heap_insert() and gts_heap_thaw() to create a heap in O(n) time.

heap :

a GtsHeap.


gts_heap_size ()

guint               gts_heap_size                       (GtsHeap *heap);

heap :

a GtsHeap.

Returns :

the number of items in heap.


gts_heap_destroy ()

void                gts_heap_destroy                    (GtsHeap *heap);

Free all the memory allocated for heap.

heap :

a GtsHeap.


GtsEHeap

typedef struct _GtsEHeap GtsEHeap;


GtsEHeapPair

typedef struct {
  gpointer data;
  gdouble key;
  guint pos;
} GtsEHeapPair;


gts_eheap_new ()

GtsEHeap *          gts_eheap_new                       (GtsKeyFunc key_func,
                                                         gpointer data);

key_func :

a GtsKeyFunc or NULL.

data :

user data to be passed to key_func.

Returns :

a new GtsEHeap using key_func as key.


gts_eheap_insert ()

GtsEHeapPair *      gts_eheap_insert                    (GtsEHeap *heap,
                                                         gpointer p);

Inserts a new element p in the heap.

heap :

a GtsEHeap.

p :

a pointer to add to the heap.

Returns :

a GtsEHeapPair describing the position of the element in the heap. This pointer is necessary for gts_eheap_remove() and gts_eheap_decrease_key().


gts_eheap_insert_with_key ()

GtsEHeapPair *      gts_eheap_insert_with_key           (GtsEHeap *heap,
                                                         gpointer p,
                                                         gdouble key);

Inserts a new element p in the heap.

heap :

a GtsEHeap.

p :

a pointer to add to the heap.

key :

the value of the key associated to p.

Returns :

a GtsEHeapPair describing the position of the element in the heap. This pointer is necessary for gts_eheap_remove() and gts_eheap_decrease_key().


gts_eheap_remove_top ()

gpointer            gts_eheap_remove_top                (GtsEHeap *heap,
                                                         gdouble *key);

Removes the element at the top of the heap and optionally (if key is not NULL) returns the value of its key.

heap :

a GtsEHeap.

key :

a pointer on a gdouble or NULL.

Returns :

the element at the top of the heap.


gts_eheap_top ()

gpointer            gts_eheap_top                       (GtsEHeap *heap,
                                                         gdouble *key);

heap :

a GtsEHeap.

key :

a pointer on a gdouble or NULL.

Returns :

the element at the top of the heap and optionally (if key is not NULL) its key.


gts_eheap_thaw ()

void                gts_eheap_thaw                      (GtsEHeap *heap);

If heap has been frozen previously using gts_eheap_freeze(), reorder it in O(n) time and unfreeze it.

heap :

a GtsEHeap.


gts_eheap_foreach ()

void                gts_eheap_foreach                   (GtsEHeap *heap,
                                                         GFunc func,
                                                         gpointer data);

heap :

a GtsEHeap.

func :

the function to call for each element in the heap.

data :

to pass to func.


gts_eheap_remove ()

gpointer            gts_eheap_remove                    (GtsEHeap *heap,
                                                         GtsEHeapPair *p);

Removes element corresponding to p from heap in O(log n).

heap :

a GtsEHeap.

p :

a GtsEHeapPair.

Returns :

the element just removed from heap.


gts_eheap_decrease_key ()

void                gts_eheap_decrease_key              (GtsEHeap *heap,
                                                         GtsEHeapPair *p,
                                                         gdouble new_key);

Decreases the value of the key of the element at position p.

heap :

a GtsEHeap.

p :

a GtsEHeapPair.

new_key :

the new value of the key for this element. Must be smaller than the current key.


gts_eheap_freeze ()

void                gts_eheap_freeze                    (GtsEHeap *heap);

Freezes the heap. Any subsequent operation will not preserve the heap property. Used in conjunction with gts_eheap_insert() and gts_eheap_thaw() to create a heap in O(n) time.

heap :

a GtsEHeap.


gts_eheap_size ()

guint               gts_eheap_size                      (GtsEHeap *heap);

heap :

a GtsEHeap.

Returns :

the number of items in heap.


gts_eheap_update ()

void                gts_eheap_update                    (GtsEHeap *heap);

Updates the key of each element of heap and reorders it.

heap :

a GtsEHeap.


gts_eheap_key ()

gdouble             gts_eheap_key                       (GtsEHeap *heap,
                                                         gpointer p);

heap :

a GtsEHeap.

p :

a pointer to be tested;

Returns :

the value of the key for pointer p.


gts_eheap_randomized ()

void                gts_eheap_randomized                (GtsEHeap *heap,
                                                         gboolean randomized);

heap :

a GtsEHeap.

randomized :

whether heap should be randomized.


gts_eheap_destroy ()

void                gts_eheap_destroy                   (GtsEHeap *heap);

Free all the memory allocated for heap.

heap :

a GtsEHeap.


GtsFifo

typedef struct _GtsFifo GtsFifo;


gts_fifo_new ()

GtsFifo *           gts_fifo_new                        (void);

Returns :

a new GtsFifo.


gts_fifo_write ()

void                gts_fifo_write                      (GtsFifo *fifo,
                                                         FILE *fp);

Writes the content of fifo in fp.

fifo :

a GtsFifo.

fp :

a file pointer.


gts_fifo_push ()

void                gts_fifo_push                       (GtsFifo *fifo,
                                                         gpointer data);

Push data into fifo.

fifo :

a GtsFifo.

data :

data to add to fifo.


gts_fifo_pop ()

gpointer            gts_fifo_pop                        (GtsFifo *fifo);

Removes the first element from fifo.

fifo :

a GtsFifo.

Returns :

the first element in fifo or NULL if fifo is empty.


gts_fifo_top ()

gpointer            gts_fifo_top                        (GtsFifo *fifo);

fifo :

a GtsFifo.

Returns :

the first element in fifo or NULL if fifo is empty.


gts_fifo_size ()

guint               gts_fifo_size                       (GtsFifo *fifo);

fifo :

a GtsFifo.

Returns :

the number of elements in fifo.


gts_fifo_is_empty ()

gboolean            gts_fifo_is_empty                   (GtsFifo *fifo);

fifo :

a GtsFifo.

Returns :

TRUE if fifo is empty, FALSE otherwise.


gts_fifo_foreach ()

void                gts_fifo_foreach                    (GtsFifo *fifo,
                                                         GtsFunc func,
                                                         gpointer data);

Calls func in order for each item in fifo, passing data.

fifo :

a GtsFifo.

func :

a GtsFunc.

data :

user data to be passed to func.


gts_fifo_reverse ()

void                gts_fifo_reverse                    (GtsFifo *fifo);

Reverses the order of elements in fifo.

fifo :

a GtsFifo.


gts_fifo_destroy ()

void                gts_fifo_destroy                    (GtsFifo *fifo);

Frees all the memory allocated for fifo.

fifo :

a GtsFifo.


GtsSplitCFace

typedef struct _GtsSplitCFace GtsSplitCFace;


GtsSplit

typedef struct {
  GtsObject object;

  GtsVertex * v;
  GtsObject * v1;
  GtsObject * v2;
  GtsSplitCFace * cfaces;
  guint ncf;
} GtsSplit;


GTS_IS_SPLIT()

#define             GTS_IS_SPLIT(obj)

obj :


GTS_SPLIT()

#define             GTS_SPLIT(obj)

obj :


GTS_SPLIT_CLASS()

#define             GTS_SPLIT_CLASS(klass)

klass :


GTS_SPLIT_V1()

#define             GTS_SPLIT_V1(vs)

vs :


GTS_SPLIT_V2()

#define             GTS_SPLIT_V2(vs)

vs :


gts_split_class ()

GtsSplitClass *     gts_split_class                     (void);

Returns :

the GtsSplitClass.


gts_split_new ()

GtsSplit *          gts_split_new                       (GtsSplitClass *klass,
                                                         GtsVertex *v,
                                                         GtsObject *o1,
                                                         GtsObject *o2);

Creates a new GtsSplit which would collapse o1 and o2 into v. The collapse itself is not performed.

klass :

a GtsSplitClass.

v :

a GtsVertex.

o1 :

either a GtsVertex or a GtsSplit.

o2 :

either a GtsVertex or a GtsSplit.

Returns :

the new GtsSplit.


gts_split_collapse ()

void                gts_split_collapse                  (GtsSplit *vs,
                                                         GtsEdgeClass *klass,
                                                         GtsEHeap *heap);

Collapses the vertex split vs. Any new edge created during the process will be of class klass. If heap is not NULL, the new edges will be inserted into it and the destroyed edges will be removed from it.

vs :

a GtsSplit.

klass :

a GtsEdgeClass.

heap :

a GtsEHeap or NULL.


gts_split_expand ()

void                gts_split_expand                    (GtsSplit *vs,
                                                         GtsSurface *s,
                                                         GtsEdgeClass *klass);

Expands the vertex split vs adding the newly created faces to s. Any new edge will be of class klass.

vs :

a GtsSplit.

s :

a GtsSurface.

klass :

a GtsEdgeClass.


GtsSplitTraverseFunc ()

gboolean            (*GtsSplitTraverseFunc)             (GtsSplit *vs,
                                                         gpointer data);

vs :

data :

Returns :


gts_split_traverse ()

void                gts_split_traverse                  (GtsSplit *root,
                                                         GTraverseType order,
                                                         gint depth,
                                                         GtsSplitTraverseFunc func,
                                                         gpointer data);

Traverses the GtsSplit tree having root as root. Calls func for each GtsSplit of the tree in the order specified by order. If order is set to G_PRE_ORDER func is called for the GtsSplit then its children, if order is set to G_POST_ORDER func is called for the children and then for the GtsSplit.

root :

the GtsSplit to start the traversal from.

order :

the order in which nodes are visited - G_PRE_ORDER or G_POST_ORDER.

depth :

the maximum depth of the traversal. Nodes below this depth will not be visited. If depth is -1 all nodes in the tree are visited. If depth is 1, only the root is visited. If depth is 2, the root and its children are visited. And so on.

func :

the function to call for each visited GtsHSplit.

data :

user data to pass to the function.


gts_split_height ()

guint               gts_split_height                    (GtsSplit *root);

root :

a GtsSplit.

Returns :

the maximum height of the vertex split tree having root as root.


GtsPSurface

typedef struct {
  GtsObject object;

  GtsSurface * s;
  GPtrArray * split;
  GtsSplitClass * split_class;
  guint pos, min;

  GPtrArray * vertices;
  GPtrArray * faces;
} GtsPSurface;


GTS_IS_PSURFACE()

#define             GTS_IS_PSURFACE(obj)

obj :


GTS_PSURFACE()

#define             GTS_PSURFACE(obj)

obj :


GTS_PSURFACE_CLASS()

#define             GTS_PSURFACE_CLASS(klass)

klass :


GTS_PSURFACE_IS_CLOSED()

#define GTS_PSURFACE_IS_CLOSED(ps)  (!(ps)->vertices)

ps :


gts_psurface_class ()

GtsPSurfaceClass *  gts_psurface_class                  (void);

Returns :

the GtsPSurfaceClass.


gts_psurface_new ()

GtsPSurface *       gts_psurface_new                    (GtsPSurfaceClass *klass,
                                                         GtsSurface *surface,
                                                         GtsSplitClass *split_class,
                                                         GtsKeyFunc cost_func,
                                                         gpointer cost_data,
                                                         GtsCoarsenFunc coarsen_func,
                                                         gpointer coarsen_data,
                                                         GtsStopFunc stop_func,
                                                         gpointer stop_data,
                                                         gdouble minangle);

This function works in exactly the same way as the gts_surface_coarsen() function, except that the history of edge collapse is saved in an array of GtsSplit objects. This allows for dynamic continuous multiresolution control of the input surface.

klass :

a GtsPSurfaceClass.

surface :

a GtsSurface.

split_class :

a GtsSplitClass to use for the new progressive surface.

cost_func :

cost function for the edge collapse algorithm.

cost_data :

data to pass to cost_func.

coarsen_func :

the function returning the vertex replacement for the edge collapse.

coarsen_data :

data to pass to coarsen_func.

stop_func :

the function to call to decide whether to stop the coarsening process.

stop_data :

data to pass to stop_func.

minangle :

the minimum angle allowable between two neighboring triangles. This is used to avoid introducing folds in the mesh during simplification.

Returns :

a new progressive surface.


gts_psurface_add_vertex ()

GtsSplit *          gts_psurface_add_vertex             (GtsPSurface *ps);

Adds a vertex to the progressive surface ps by expanding the next available GtsSplit.

ps :

a GtsPSurface.

Returns :

the expanded GtsSplit or NULL if all the GtsSplit have already been expanded.


gts_psurface_remove_vertex ()

GtsSplit *          gts_psurface_remove_vertex          (GtsPSurface *ps);

Removes one vertex from the progressive surface ps by collapsing the first available GtsSplit.

ps :

a GtsPSurface.

Returns :

the collapsed GtsSplit or NULL if all the GtsSplit have already been collapsed.


gts_psurface_max_vertex_number ()

guint               gts_psurface_max_vertex_number      (GtsPSurface *ps);

ps :

a GtsPSurface.

Returns :

the maximum number of vertices of ps i.e. the number of vertices if all the GtsSplit were expanded.


gts_psurface_min_vertex_number ()

guint               gts_psurface_min_vertex_number      (GtsPSurface *ps);

ps :

a GtsPSurface.

Returns :

the minimum number of vertices of ps i.e. the number of vertices if all the GtsSplit were collapsed.


gts_psurface_set_vertex_number ()

void                gts_psurface_set_vertex_number      (GtsPSurface *ps,
                                                         guint n);

Performs the required number of collapses or expansions to set the number of vertices of ps to n.

ps :

a GtsPSurface.

n :

a number of vertices.


gts_psurface_get_vertex_number ()

guint               gts_psurface_get_vertex_number      (GtsPSurface *ps);

ps :

a GtsPSurface.

Returns :

the current number of vertices of ps.


gts_psurface_write ()

void                gts_psurface_write                  (GtsPSurface *ps,
                                                         FILE *fptr);

Writes to fptr a GTS progressive surface description.

ps :

a GtsPSurface.

fptr :

a file pointer.


gts_psurface_open ()

GtsPSurface *       gts_psurface_open                   (GtsPSurfaceClass *klass,
                                                         GtsSurface *s,
                                                         GtsSplitClass *split_class,
                                                         GtsFile *f);

Creates a new GtsPSurface prepared for input from the file f containing a valid GTS representation of a progressive surface. The initial shape of the progressive surface is loaded into s.

Before being usable as such this progressive surface must be closed using gts_psurface_close(). While open however, the functions gts_psurface_get_vertex_number(), gts_psurface_min_vertex_number() and gts_psurface_max_vertex_number() can still be used.

klass :

a GtsPSurfaceClass.

s :

a GtsSurface.

split_class :

a GtsSplitClass to use for the GtsSplit.

f :

a GtsFile.

Returns :

a new GtsPSurface or NULL if there was a format error while reading the file, in which case f contains information about the error.


gts_psurface_read_vertex ()

GtsSplit *          gts_psurface_read_vertex            (GtsPSurface *ps,
                                                         GtsFile *fp);

Reads in one vertex split operation from fp and performs the expansion.

If an error occurs while reading the file, the error field of fp is set.

ps :

a GtsPSurface prealably created with gts_psurface_open().

fp :

a GtsFile.

Returns :

the newly created GtsSplit or NULL if no vertex split could be read from fp.


gts_psurface_close ()

void                gts_psurface_close                  (GtsPSurface *ps);

Closes a progressive surface.

ps :

a GtsPSurface prealably created with gts_psurface_open().


gts_psurface_foreach_vertex ()

void                gts_psurface_foreach_vertex         (GtsPSurface *ps,
                                                         GtsFunc func,
                                                         gpointer data);

Calls func for each (potential) vertex of ps, whether actually used or not. The vertices are called in the order they were created during the edge collapse operation.

ps :

a GtsPSurface.

func :

a function to call for each vertex of ps.

data :

data to be passed to func.


GtsHSplit

typedef struct {
  GtsSplit split;

  GtsEHeapPair * index;
  GtsHSplit * parent;
  guint nchild;
} GtsHSplit;


GTS_IS_HSPLIT()

#define             GTS_IS_HSPLIT(obj)

obj :


GTS_HSPLIT()

#define             GTS_HSPLIT(obj)

obj :


GTS_HSPLIT_CLASS()

#define             GTS_HSPLIT_CLASS(klass)

klass :


gts_hsplit_class ()

GtsHSplitClass *    gts_hsplit_class                    (void);

Returns :

the GtsHSplitClass.


gts_hsplit_new ()

GtsHSplit *         gts_hsplit_new                      (GtsHSplitClass *klass,
                                                         GtsSplit *vs);

klass :

a GtsHSplitClass.

vs :

a GtsSplit.

Returns :

a new GtsHSplit, hierarchical extension of vs.


gts_hsplit_collapse ()

void                gts_hsplit_collapse                 (GtsHSplit *hs,
                                                         GtsHSurface *hsurface);

Collapses the GtsSplit defined by hs, updates the expandable and collapsable priority heaps of hsurface.

hs :

a GtsHSplit.

hsurface :

a GtsHSurface.


gts_hsplit_expand ()

void                gts_hsplit_expand                   (GtsHSplit *hs,
                                                         GtsHSurface *hsurface);

Expands the GtsSplit defined by hs (which must be expandable) and updates the priority heaps of hsurface.

hs :

a GtsHSplit.

hsurface :

a GtsHSurface.


gts_hsplit_force_expand ()

void                gts_hsplit_force_expand             (GtsHSplit *hs,
                                                         GtsHSurface *hsurface);

Forces the expansion of hs by first expanding all its dependencies not already expanded.

hs :

a GtsHSplit.

hsurface :

a GtsHSurface.


GtsHSurface

typedef struct {
  GtsObject object;

  GtsSurface * s;
  GSList * roots;
  GtsEHeap * expandable;
  GtsEHeap * collapsable;
  GPtrArray * split;
  guint nvertex;
} GtsHSurface;


GTS_IS_HSURFACE()

#define             GTS_IS_HSURFACE(obj)

obj :


GTS_HSURFACE()

#define             GTS_HSURFACE(obj)

obj :


GTS_HSURFACE_CLASS()

#define             GTS_HSURFACE_CLASS(klass)

klass :


gts_hsurface_class ()

GtsHSurfaceClass *  gts_hsurface_class                  (void);

Returns :

the GtsHSurfaceClass.


gts_hsurface_new ()

GtsHSurface *       gts_hsurface_new                    (GtsHSurfaceClass *klass,
                                                         GtsHSplitClass *hsplit_class,
                                                         GtsPSurface *psurface,
                                                         GtsKeyFunc expand_key,
                                                         gpointer expand_data,
                                                         GtsKeyFunc collapse_key,
                                                         gpointer collapse_data);

klass :

a GtsHSurfaceClass.

hsplit_class :

a GtsHSplitClass.

psurface :

a GtsPSurface.

expand_key :

a GtsKeyFunc used to order the priority heap of expandable GtsHSplit.

expand_data :

data to be passed to expand_key.

collapse_key :

a GtsKeyFunc used to order the priority heap of collapsable GtsHSplit.

collapse_data :

data to be passed to collapsed_key.

Returns :

a new GtsHSurface, hierarchical extension of psurface and using GtsHSplit of class hsplit_class. Note that psurface is destroyed in the process.


gts_hsurface_traverse ()

void                gts_hsurface_traverse               (GtsHSurface *hsurface,
                                                         GTraverseType order,
                                                         gint depth,
                                                         GtsSplitTraverseFunc func,
                                                         gpointer data);

Traverses a hierarchical surface starting from its roots. It calls the given function for each GtsHSplit visited. See also gts_split_traverse().

hsurface :

a GtsHSurface.

order :

the order in which nodes are visited - G_PRE_ORDER or G_POST_ORDER.

depth :

the maximum depth of the traversal. Nodes below this depth will not be visited. If max_depth is -1 all nodes in the tree are visited. If depth is 1, only the root is visited. If depth is 2, the root and its children are visited. And so on.

func :

the function to call for each visited GtsHSplit.

data :

user data to pass to the function.


gts_hsurface_foreach ()

void                gts_hsurface_foreach                (GtsHSurface *hsurface,
                                                         GTraverseType order,
                                                         GtsFunc func,
                                                         gpointer data);

Starts by expanding all the GtsHSplit of hsurface. If order is G_PRE_ORDER, calls func for each GtsHSplit and collapses it. If order is G_POST_ORDER, collapses each GtsHSplit first and then calls func. The traversal can be halted at any point by returning TRUE from func.

hsurface :

a GtsHSurface.

order :

the order in which GtsHSplit are visited - G_PRE_ORDER or G_POST_ORDER.

func :

the function to call for each visited GtsHSplit.

data :

user data to pass to the function.


gts_hsurface_height ()

guint               gts_hsurface_height                 (GtsHSurface *hsurface);

hsurface :

a GtsHSurface.

Returns :

the maximum height of the tree described by hsurface.


GTS_IS_CONSTRAINT()

#define             GTS_IS_CONSTRAINT(obj)

Evaluates to TRUE if obj is a GtsConstraint, FALSE otherwise.

obj :

a GtsObject.


GTS_CONSTRAINT()

#define             GTS_CONSTRAINT(obj)

Casts obj to GtsConstraint.

obj :

a descendant of GtsConstraint.


GTS_CONSTRAINT_CLASS()

#define             GTS_CONSTRAINT_CLASS(klass)

Casts klass to GtsConstraintClass.

klass :

a desscendant of GtsConstraintClass.


GtsConstraint

typedef struct _GtsConstraint GtsConstraint;


GtsConstraintClass

typedef struct _GtsConstraintClass GtsConstraintClass;


gts_constraint_class ()

GtsConstraintClass * gts_constraint_class               (void);

Returns :

the GtsConstraintClass.


gts_point_locate ()

GtsFace *           gts_point_locate                    (GtsPoint *p,
                                                         GtsSurface *surface,
                                                         GtsFace *guess);

Locates the face of the planar projection of surface containing p. The planar projection of surface must define a connected set of triangles without holes and bounded by a convex boundary. The algorithm is randomized and performs in O(n^1/3) expected time where n is the number of triangles of surface.

If a good guess is given the point location can be significantly faster.

p :

a GtsPoint.

surface :

a GtsSurface.

guess :

NULL or a face of surface close to p.

Returns :

a GtsFace of surface containing p or NULL if p is not contained within the boundary of surface.


gts_delaunay_add_vertex_to_face ()

GtsVertex *         gts_delaunay_add_vertex_to_face     (GtsSurface *surface,
                                                         GtsVertex *v,
                                                         GtsFace *f);

Adds vertex v to the face f of the Delaunay triangulation defined by surface.

surface :

a GtsSurface.

v :

a GtsVertex.

f :

a GtsFace belonging to surface.

Returns :

NULL is v has been successfully added to surface or was already contained in surface or a GtsVertex having the same x and y coordinates as v.


gts_delaunay_add_vertex ()

GtsVertex *         gts_delaunay_add_vertex             (GtsSurface *surface,
                                                         GtsVertex *v,
                                                         GtsFace *guess);

Adds vertex v to the Delaunay triangulation defined by surface. If v is not contained in the convex hull bounding surface, v is not added to the triangulation.

surface :

a GtsSurface.

v :

a GtsVertex.

guess :

NULL or a GtsFace belonging to surface to be used as an initial guess for point location.

Returns :

NULL is v has been successfully added to surface or was already contained in surface, v if v is not contained in the convex hull bounding surface or a GtsVertex having the same x and y coordinates as v.


gts_delaunay_remove_vertex ()

void                gts_delaunay_remove_vertex          (GtsSurface *surface,
                                                         GtsVertex *v);

Removes v from the Delaunay triangulation defined by surface and restores the Delaunay property. Vertex v must not be used by any constrained edge otherwise the triangulation is not guaranteed to be Delaunay.

surface :

a GtsSurface.

v :

a GtsVertex.


gts_delaunay_check ()

GtsFace *           gts_delaunay_check                  (GtsSurface *surface);

surface :

a GtsSurface.

Returns :

NULL if the planar projection of surface is a Delaunay triangulation (unconstrained), a GtsFace violating the Delaunay property otherwise.


gts_delaunay_add_constraint ()

GSList *            gts_delaunay_add_constraint         (GtsSurface *surface,
                                                         GtsConstraint *c);

Add constraint c to the constrained Delaunay triangulation defined by surface.

surface :

a GtsSurface.

c :

a GtsConstraint.

Returns :

a list of GtsConstraint conflicting (i.e. intersecting) with c which were removed from surface (NULL if there was none).


gts_delaunay_remove_hull ()

void                gts_delaunay_remove_hull            (GtsSurface *surface);

Removes all the edges of the boundary of surface which are not constraints.

surface :

a GtsSurface.


GtsListFace

typedef struct {
  GSList * points;
} GtsListFace;


GTS_LIST_FACE()

#define             GTS_LIST_FACE(obj)

obj :


GTS_IS_LIST_FACE()

#define             GTS_IS_LIST_FACE(obj)

obj :


gts_list_face_class ()

GtsFaceClass *      gts_list_face_class                 (void);

Returns :


GtsEncroachFunc ()

gboolean            (*GtsEncroachFunc)                  (GtsVertex *v,
                                                         GtsEdge *e,
                                                         GtsSurface *s,
                                                         gpointer data);

v :

e :

s :

data :

Returns :


gts_vertex_encroaches_edge ()

gboolean            gts_vertex_encroaches_edge          (GtsVertex *v,
                                                         GtsEdge *e);

v :

a GtsVertex.

e :

a GtsEdge.

Returns :

TRUE if v is strictly contained in the diametral circle of e, FALSE otherwise.


gts_edge_is_encroached ()

GtsVertex *         gts_edge_is_encroached              (GtsEdge *e,
                                                         GtsSurface *s,
                                                         GtsEncroachFunc encroaches,
                                                         gpointer data);

e :

a GtsEdge.

s :

a GtsSurface describing a (constrained) Delaunay triangulation.

encroaches :

a GtsEncroachFunc.

data :

user data to be passed to encroaches.

Returns :

a GtsVertex belonging to s and encroaching upon e (as defined by encroaches) or NULL if there is none.


gts_delaunay_conform ()

guint               gts_delaunay_conform                (GtsSurface *surface,
                                                         gint steiner_max,
                                                         GtsEncroachFunc encroaches,
                                                         gpointer data);

Recursively split constraints of surface which are encroached by vertices of surface (see Shewchuk 96 for details). The split constraints are destroyed and replaced by a set of new constraints of the same class. If gts_vertex_encroaches_edge() is used for encroaches, the resulting surface will be Delaunay conforming.

If steiner_max is positive or nul, the recursive splitting procedure will stop when this maximum number of Steiner points is reached. In that case the resulting surface will not necessarily be Delaunay conforming.

surface :

a GtsSurface describing a constrained Delaunay triangulation.

steiner_max :

maximum number of Steiner points.

encroaches :

a GtsEncroachFunc.

data :

user-data to pass to encroaches.

Returns :

the number of remaining encroached edges. If steiner_max is set to a negative value and gts_vertex_encroaches_edge() is used for encroaches this should always be zero.


gts_delaunay_refine ()

guint               gts_delaunay_refine                 (GtsSurface *surface,
                                                         gint steiner_max,
                                                         GtsEncroachFunc encroaches,
                                                         gpointer encroach_data,
                                                         GtsKeyFunc cost,
                                                         gpointer cost_data);

An implementation of the refinement algorithm described in Ruppert (1995) and Shewchuk (1996).

surface :

a GtsSurface describing a conforming Delaunay triangulation.

steiner_max :

maximum number of Steiner points.

encroaches :

a GtsEncroachFunc.

encroach_data :

user-data to pass to encroaches.

cost :

a GtsKeyFunc used to sort the faces during refinement.

cost_data :

user-data to pass to cost.

Returns :

the number of unrefined faces of surface left. Should be zero if steiner_max is set to a negative value.


GtsGridPlane

typedef struct {
  GtsPoint ** p;
  guint nx, ny;
} GtsGridPlane;


GtsIsoSlice

typedef struct _GtsIsoSlice GtsIsoSlice;


GtsCartesianGrid

typedef struct {
  guint nx, ny, nz;
  gdouble x, dx, y, dy, z, dz;
} GtsCartesianGrid;


GtsIsoCartesianFunc ()

void                (*GtsIsoCartesianFunc)              (gdouble **a,
                                                         GtsCartesianGrid g,
                                                         guint i,
                                                         gpointer data);

a :

g :

i :

data :


gts_grid_plane_new ()

GtsGridPlane *      gts_grid_plane_new                  (guint nx,
                                                         guint ny);

nx :

ny :

Returns :


gts_grid_plane_destroy ()

void                gts_grid_plane_destroy              (GtsGridPlane *g);

g :


gts_iso_slice_new ()

GtsIsoSlice *       gts_iso_slice_new                   (guint nx,
                                                         guint ny);

nx :

number of vertices in the x direction.

ny :

number of vertices in the y direction.

Returns :

a new GtsIsoSlice.


gts_iso_slice_fill ()

void                gts_iso_slice_fill                  (GtsIsoSlice *slice,
                                                         GtsGridPlane *plane1,
                                                         GtsGridPlane *plane2,
                                                         gdouble **f1,
                                                         gdouble **f2,
                                                         gdouble iso,
                                                         GtsVertexClass *klass);

Fill slice with the coordinates of the vertices defined by f1 (x,y,z) = iso and f2 (x, y, z) = iso.

slice :

a GtsIsoSlice.

plane1 :

a GtsGridPlane.

plane2 :

another GtsGridPlane.

f1 :

values of the function corresponding to plane1.

f2 :

values of the function corresponding to plane2.

iso :

isosurface value.

klass :

a GtsVertexClass or one of its descendant to be used for the new vertices.


gts_iso_slice_fill_cartesian ()

void                gts_iso_slice_fill_cartesian        (GtsIsoSlice *slice,
                                                         GtsCartesianGrid g,
                                                         gdouble **f1,
                                                         gdouble **f2,
                                                         gdouble iso,
                                                         GtsVertexClass *klass);

Fill slice with the coordinates of the vertices defined by f1 (x,y,z) = iso and f2 (x, y, z) = iso.

slice :

a GtsIsoSlice.

g :

a GtsCartesianGrid.

f1 :

values of the function for plane z = g.z.

f2 :

values of the function for plane z = g.z + g.dz.

iso :

isosurface value.

klass :

a GtsVertexClass.


gts_iso_slice_destroy ()

void                gts_iso_slice_destroy               (GtsIsoSlice *slice);

Free all memory allocated for slice.

slice :

a GtsIsoSlice.


gts_isosurface_slice ()

void                gts_isosurface_slice                (GtsIsoSlice *slice1,
                                                         GtsIsoSlice *slice2,
                                                         GtsSurface *surface);

Given two successive slices slice1 and slice2 link their vertices with segments and triangles which are added to surface.

slice1 :

a GtsIsoSlice.

slice2 :

another GtsIsoSlice.

surface :

a GtsSurface.


gts_isosurface_cartesian ()

void                gts_isosurface_cartesian            (GtsSurface *surface,
                                                         GtsCartesianGrid g,
                                                         GtsIsoCartesianFunc f,
                                                         gpointer data,
                                                         gdouble iso);

Adds to surface new faces defining the isosurface f(x,y,z) = iso. By convention, the normals to the surface are pointing toward the positive values of f(x,y,z) - iso.

The user function f is called successively for each value of the z coordinate defined by g. It must fill the corresponding (x,y) plane with the values of the function for which the isosurface is to be computed.

surface :

a GtsSurface.

g :

a GtsCartesianGrid.

f :

a GtsIsoCartesianFunc.

data :

user data to be passed to f.

iso :

isosurface value.


gts_isosurface_tetra ()

void                gts_isosurface_tetra                (GtsSurface *surface,
                                                         GtsCartesianGrid g,
                                                         GtsIsoCartesianFunc f,
                                                         gpointer data,
                                                         gdouble iso);

Adds to surface new faces defining the isosurface f(x,y,z) = iso. By convention, the normals to the surface are pointing toward the positive values of f(x,y,z) - iso.

The user function f is called successively for each value of the z coordinate defined by g. It must fill the corresponding (x,y) plane with the values of the function for which the isosurface is to be computed.

surface :

a GtsSurface.

g :

a GtsCartesianGrid.

f :

a GtsIsoCartesianFunc.

data :

user data to be passed to f.

iso :

isosurface value.


gts_isosurface_tetra_bcl ()

void                gts_isosurface_tetra_bcl            (GtsSurface *surface,
                                                         GtsCartesianGrid g,
                                                         GtsIsoCartesianFunc f,
                                                         gpointer data,
                                                         gdouble iso);

Adds to surface new faces defining the isosurface f(x,y,z) = iso. By convention, the normals to the surface are pointing toward the positive values of f(x,y,z) - iso.

The user function f is called successively for each value of the z coordinate defined by g. It must fill the corresponding (x,y) plane with the values of the function for which the isosurface is to be computed.

This version produces the dual "body-centered" faces relative to the faces produced by gts_isosurface_tetra().

surface :

a GtsSurface.

g :

a GtsCartesianGrid.

f :

a GtsIsoCartesianFunc.

data :

user data to be passed to f.

iso :

isosurface value.


gts_isosurface_tetra_bounded ()

void                gts_isosurface_tetra_bounded        (GtsSurface *surface,
                                                         GtsCartesianGrid g,
                                                         GtsIsoCartesianFunc f,
                                                         gpointer data,
                                                         gdouble iso);

Adds to surface new faces defining the isosurface f(x,y,z) = iso. By convention, the normals to the surface are pointing toward the positive values of f(x,y,z) - iso. To ensure a closed object, a boundary of G_MINDOUBLE is added around the domain

The user function f is called successively for each value of the z coordinate defined by g. It must fill the corresponding (x,y) plane with the values of the function for which the isosurface is to be computed.

surface :

a GtsSurface.

g :

a GtsCartesianGrid.

f :

a GtsIsoCartesianFunc.

data :

user data to be passed to f.

iso :

isosurface value.


GTS_NAME_LENGTH

#define GTS_NAME_LENGTH             40


GTS_NVERTEX()

#define             GTS_NVERTEX(obj)

obj :


GTS_NVERTEX_CLASS()

#define             GTS_NVERTEX_CLASS(klass)

klass :


GTS_IS_NVERTEX()

#define             GTS_IS_NVERTEX(obj)

obj :


GtsNVertex

typedef struct {
  GtsVertex parent;
  char name[GTS_NAME_LENGTH];
} GtsNVertex;


gts_nvertex_class ()

GtsNVertexClass *   gts_nvertex_class                   (void);

Returns :

the GtsNVertexClass.


GTS_NEDGE()

#define             GTS_NEDGE(obj)

obj :


GTS_NEDGE_CLASS()

#define             GTS_NEDGE_CLASS(klass)

klass :


GTS_IS_NEDGE()

#define             GTS_IS_NEDGE(obj)

obj :


GtsNEdge

typedef struct {
  GtsEdge parent;
  char name[GTS_NAME_LENGTH];
} GtsNEdge;


gts_nedge_class ()

GtsNEdgeClass *     gts_nedge_class                     (void);

Returns :

the GtsNEdgeClass.


GTS_NFACE()

#define             GTS_NFACE(obj)

obj :


GTS_NFACE_CLASS()

#define             GTS_NFACE_CLASS(klass)

klass :


GTS_IS_NFACE()

#define             GTS_IS_NFACE(obj)

obj :


GtsNFace

typedef struct {
  GtsFace parent;
  char name[GTS_NAME_LENGTH];
} GtsNFace;


gts_nface_class ()

GtsNFaceClass *     gts_nface_class                     (void);

Returns :

the GtsNFaceClass.


GTS_CLUSTER()

#define             GTS_CLUSTER(obj)

obj :


GTS_CLUSTER_CLASS()

#define             GTS_CLUSTER_CLASS(klass)

klass :


GTS_IS_CLUSTER()

#define             GTS_IS_CLUSTER(obj)

obj :


GtsClusterId

typedef struct {
  guint x, y, z;
} GtsClusterId;


GtsCluster

typedef struct {
  GtsObject parent;

  GtsClusterId id;
  GtsVertex * v;
  guint n;
} GtsCluster;


gts_cluster_class ()

GtsClusterClass *   gts_cluster_class                   (void);

Returns :

the GtsClusterClass.


gts_cluster_new ()

GtsCluster *        gts_cluster_new                     (GtsClusterClass *klass,
                                                         GtsClusterId id,
                                                         GtsVertexClass *vklass);

klass :

a GtsClusterClass.

id :

the id of the new cluster.

vklass :

a GtsVertexClass for the representative vertex of the cluster.

Returns :

a new GtsCluster.


gts_cluster_add ()

void                gts_cluster_add                     (GtsCluster *c,
                                                         GtsPoint *p,
                                                         gpointer data);

Adds point p to cluster c.

c :

a GtsCluster.

p :

a GtsPoint.

data :

data to pass to the add() virtual method of GtsClusterClass.


gts_cluster_update ()

void                gts_cluster_update                  (GtsCluster *c);

Updates the position of the vertex representative of all the vertices added to c.

c :

a GtsCluster.


GTS_CLUSTER_GRID()

#define             GTS_CLUSTER_GRID(obj)

obj :


GTS_CLUSTER_GRID_CLASS()

#define             GTS_CLUSTER_GRID_CLASS(klass)

klass :


GTS_IS_CLUSTER_GRID()

#define             GTS_IS_CLUSTER_GRID(obj)

obj :


GtsClusterGrid

typedef struct {
  GtsObject parent;

  GtsSurface * surface;
  GtsBBox * bbox;
  GtsVector size;

  GtsClusterClass * cluster_class;
  GHashTable * clusters;
} GtsClusterGrid;


gts_cluster_grid_class ()

GtsClusterGridClass * gts_cluster_grid_class            (void);

Returns :

the GtsClusterGridClass.


gts_cluster_grid_new ()

GtsClusterGrid *    gts_cluster_grid_new                (GtsClusterGridClass *klass,
                                                         GtsClusterClass *cluster_class,
                                                         GtsSurface *s,
                                                         GtsBBox *bbox,
                                                         gdouble delta);

klass :

a GtsClusterGridClass.

cluster_class :

the klass to be used for the vertex clusters.

s :

the simplified surface.

bbox :

bounding box of the surface to be simplified.

delta :

the size of one grid cell of the simplification grid.

Returns :

a new GtsClusterGrid.


gts_cluster_grid_add_triangle ()

void                gts_cluster_grid_add_triangle       (GtsClusterGrid *cluster_grid,
                                                         GtsPoint *p1,
                                                         GtsPoint *p2,
                                                         GtsPoint *p3,
                                                         gpointer data);

Adds the triangle defined by p1, p2 and p3 to the respective clusters of cluster_grid.

cluster_grid :

a GtsClusterGrid.

p1 :

a GtsPoint.

p2 :

a GtsPoint.

p3 :

a GtsPoint.

data :

user data to pass to the cluster add() method.


gts_cluster_grid_update ()

GtsRange            gts_cluster_grid_update             (GtsClusterGrid *cluster_grid);

Updates the representative vertices of all the clusters of cluster_grid.

cluster_grid :

a GtsClusterGrid.

Returns :

a GtsRange describing the statistics for the number of vertices added to each cluster of cluster_grid.


gts_surface_strip ()

GSList *            gts_surface_strip                   (GtsSurface *s);

Decompose s into triangle strips for fast-rendering.

s :

a GtsSurface.

Returns :

a list of triangle strips containing all the triangles of s. A triangle strip is itself a list of successive triangles having one edge in common.


GtsContainee

typedef struct {
  GtsObject object;
} GtsContainee;


GTS_CONTAINEE()

#define             GTS_CONTAINEE(obj)

obj :


GTS_CONTAINEE_CLASS()

#define             GTS_CONTAINEE_CLASS(klass)

klass :


GTS_IS_CONTAINEE()

#define             GTS_IS_CONTAINEE(obj)

obj :


gts_containee_class ()

GtsContaineeClass * gts_containee_class                 (void);

Returns :


gts_containee_new ()

GtsContainee *      gts_containee_new                   (GtsContaineeClass *klass);

klass :

Returns :


gts_containee_is_contained ()

gboolean            gts_containee_is_contained          (GtsContainee *item,
                                                         GtsContainer *c);

item :

c :

Returns :


gts_containee_replace ()

void                gts_containee_replace               (GtsContainee *item,
                                                         GtsContainee *with);

item :

with :


GtsSListContainee

typedef struct {
  GtsContainee containee;

  GSList * containers;
} GtsSListContainee;


GTS_SLIST_CONTAINEE()

#define             GTS_SLIST_CONTAINEE(obj)

obj :


GTS_SLIST_CONTAINEE_CLASS()

#define             GTS_SLIST_CONTAINEE_CLASS(klass)

klass :


GTS_IS_SLIST_CONTAINEE()

#define             GTS_IS_SLIST_CONTAINEE(obj)

obj :


gts_slist_containee_class ()

GtsSListContaineeClass * gts_slist_containee_class      (void);

Returns :


GtsContainer

typedef struct {
  GtsSListContainee object;
} GtsContainer;


GTS_CONTAINER()

#define             GTS_CONTAINER(obj)

obj :


GTS_CONTAINER_CLASS()

#define             GTS_CONTAINER_CLASS(klass)

klass :


GTS_IS_CONTAINER()

#define             GTS_IS_CONTAINER(obj)

obj :


gts_container_class ()

GtsContainerClass * gts_container_class                 (void);

Returns :


gts_container_new ()

GtsContainer *      gts_container_new                   (GtsContainerClass *klass);

klass :

Returns :


gts_container_add ()

void                gts_container_add                   (GtsContainer *c,
                                                         GtsContainee *item);

c :

item :


gts_container_remove ()

void                gts_container_remove                (GtsContainer *c,
                                                         GtsContainee *item);

c :

item :


gts_container_foreach ()

void                gts_container_foreach               (GtsContainer *c,
                                                         GtsFunc func,
                                                         gpointer data);

c :

func :

data :


gts_container_size ()

guint               gts_container_size                  (GtsContainer *c);

c :

Returns :


GtsHashContainer

typedef struct {
  GtsContainer c;

  GHashTable * items;
  gboolean frozen;
} GtsHashContainer;


GTS_HASH_CONTAINER()

#define             GTS_HASH_CONTAINER(obj)

obj :


GTS_HASH_CONTAINER_CLASS()

#define             GTS_HASH_CONTAINER_CLASS(klass)

klass :


GTS_IS_HASH_CONTAINER()

#define             GTS_IS_HASH_CONTAINER(obj)

obj :


gts_hash_container_class ()

GtsHashContainerClass * gts_hash_container_class        (void);

Returns :


GtsSListContainer

typedef struct {
  GtsContainer c;

  GSList * items;
  gboolean frozen;
} GtsSListContainer;


GTS_SLIST_CONTAINER()

#define             GTS_SLIST_CONTAINER(obj)

obj :


GTS_SLIST_CONTAINER_CLASS()

#define             GTS_SLIST_CONTAINER_CLASS(klass)

klass :


GTS_IS_SLIST_CONTAINER()

#define             GTS_IS_SLIST_CONTAINER(obj)

obj :


gts_slist_container_class ()

GtsSListContainerClass * gts_slist_container_class      (void);

Returns :


GtsGNode

typedef struct {
  GtsSListContainer container;

  guint level;
} GtsGNode;


GTS_GNODE()

#define             GTS_GNODE(obj)

obj :


GTS_GNODE_CLASS()

#define             GTS_GNODE_CLASS(klass)

klass :


GTS_IS_GNODE()

#define             GTS_IS_GNODE(obj)

obj :


GTS_GNODE_NEIGHBOR()

#define GTS_GNODE_NEIGHBOR(n,e)   (GTS_GEDGE (e)->n1 == n ? GTS_GEDGE (e)->n2 : GTS_GEDGE (e)->n2 == n ? GTS_GEDGE (e)->n1 : NULL)

n :

e :


gts_gnode_class ()

GtsGNodeClass *     gts_gnode_class                     (void);

Returns :

the GtsGNodeClass.


gts_gnode_new ()

GtsGNode *          gts_gnode_new                       (GtsGNodeClass *klass);

klass :

a GtsGNodeClass.

Returns :

a new GtsGNode.


gts_gnode_foreach_neighbor ()

void                gts_gnode_foreach_neighbor          (GtsGNode *n,
                                                         GtsGraph *g,
                                                         GtsFunc func,
                                                         gpointer data);

Calls func for each neighbor GtsGNode of n (belonging to g if g is not NULL.

n :

a GtsGNode.

g :

a GtsGraph or NULL.

func :

a GtsFunc.

data :

user data to be passed to func.


gts_gnode_foreach_edge ()

void                gts_gnode_foreach_edge              (GtsGNode *n,
                                                         GtsGraph *g,
                                                         GtsFunc func,
                                                         gpointer data);

Calls func for each GtsGEdge connecting n to another GtsGNode (belonging to g if g is not NULL.

n :

a GtsGNode.

g :

a GtsGraph or NULL.

func :

a GtsFunc.

data :

user data to be passed to func.


gts_gnode_degree ()

guint               gts_gnode_degree                    (GtsGNode *n,
                                                         GtsGraph *g);

n :

a GtsGNode.

g :

a GtsGraph or NULL.

Returns :

the number of neighbors of n (belonging to g if g is not NULL).


gts_gnode_move_cost ()

gfloat              gts_gnode_move_cost                 (GtsGNode *n,
                                                         GtsGraph *src,
                                                         GtsGraph *dst);

n :

a GtsGNode.

src :

a GtsGraph containing n.

dst :

another GtsGraph.

Returns :

the cost (increase in the sum of the weights of the edges cut) of moving n from src to dst.


gts_gnode_weight ()

gfloat              gts_gnode_weight                    (GtsGNode *n);

n :

a GtsGNode.

Returns :

the weight of n as defined by the weight() method of the GtsGNodeClass.


GtsNGNode

typedef struct {
  GtsGNode node;

  guint id;
} GtsNGNode;


GTS_NGNODE()

#define             GTS_NGNODE(obj)

obj :


GTS_NGNODE_CLASS()

#define             GTS_NGNODE_CLASS(klass)

klass :


GTS_IS_NGNODE()

#define             GTS_IS_NGNODE(obj)

obj :


gts_ngnode_class ()

GtsNGNodeClass *    gts_ngnode_class                    (void);

Returns :

the GtsNGNodeClass.


gts_ngnode_new ()

GtsNGNode *         gts_ngnode_new                      (GtsNGNodeClass *klass,
                                                         guint id);

klass :

a GtsNGNodeClass.

id :

Returns :

a new GtsNGNode with identity id.


GtsWGNode

typedef struct {
  GtsGNode node;
  
  gfloat weight;
} GtsWGNode;


GTS_WGNODE()

#define             GTS_WGNODE(obj)

obj :


GTS_WGNODE_CLASS()

#define             GTS_WGNODE_CLASS(klass)

klass :


GTS_IS_WGNODE()

#define             GTS_IS_WGNODE(obj)

obj :


gts_wgnode_class ()

GtsWGNodeClass *    gts_wgnode_class                    (void);

Returns :

the GtsWGNodeClass.


gts_wgnode_new ()

GtsWGNode *         gts_wgnode_new                      (GtsWGNodeClass *klass,
                                                         gfloat weight);

klass :

a GtsWGNodeClass.

weight :

the weight of the GtsWGNode to create.

Returns :

a new GtsWGNode of weight weight.


GtsPNode

typedef struct {
  GtsGNode node;

  gpointer data;
} GtsPNode;


GTS_PNODE()

#define             GTS_PNODE(obj)

obj :


GTS_PNODE_CLASS()

#define             GTS_PNODE_CLASS(klass)

klass :


GTS_IS_PNODE()

#define             GTS_IS_PNODE(obj)

obj :


gts_pnode_class ()

GtsPNodeClass *     gts_pnode_class                     (void);

Returns :

the GtsPNodeClass.


gts_pnode_new ()

GtsPNode *          gts_pnode_new                       (GtsPNodeClass *klass,
                                                         gpointer data);

klass :

a GtsPNodeClass.

data :

user data.

Returns :

a new GtsPNode associated with data.


GtsFNode

typedef struct {
  GtsGNode node;

  GtsFace * f;
} GtsFNode;


GTS_FNODE()

#define             GTS_FNODE(obj)

obj :


GTS_FNODE_CLASS()

#define             GTS_FNODE_CLASS(klass)

klass :


GTS_IS_FNODE()

#define             GTS_IS_FNODE(obj)

obj :


gts_fnode_class ()

GtsFNodeClass *     gts_fnode_class                     (void);

Returns :

the GtsFNodeClass.


gts_fnode_new ()

GtsFNode *          gts_fnode_new                       (GtsFNodeClass *klass,
                                                         GtsFace *f);

klass :

a GtsFNodeClass.

f :

a GtsFace.

Returns :

a new GtsFNode associated with face f.


GtsGEdge

typedef struct {
  GtsContainee containee;

  GtsGNode * n1;
  GtsGNode * n2;
} GtsGEdge;


GTS_GEDGE()

#define             GTS_GEDGE(obj)

obj :


GTS_GEDGE_CLASS()

#define             GTS_GEDGE_CLASS(klass)

klass :


GTS_IS_GEDGE()

#define             GTS_IS_GEDGE(obj)

obj :


gts_gedge_class ()

GtsGEdgeClass *     gts_gedge_class                     (void);

Returns :

the GtsGEdgeClass.


gts_gedge_new ()

GtsGEdge *          gts_gedge_new                       (GtsGEdgeClass *klass,
                                                         GtsGNode *n1,
                                                         GtsGNode *n2);

klass :

a GtsGEdgeClass.

n1 :

a GtsGNode.

n2 :

another GtsGNode.

Returns :

a new GtsGEdge linking n1 and n2.


gts_gedge_weight ()

gfloat              gts_gedge_weight                    (GtsGEdge *e);

e :

a GtsGEdge.

Returns :

the weight of edge e as defined by the weight() method of GtsGEdgeClass.


gts_gedge_connects()

#define             gts_gedge_connects(e, a1, a2)

e :

a1 :

a2 :


GtsPGEdge

typedef struct {
  GtsGEdge gedge;

  gpointer data;
} GtsPGEdge;


GTS_PGEDGE()

#define             GTS_PGEDGE(obj)

obj :


GTS_PGEDGE_CLASS()

#define             GTS_PGEDGE_CLASS(klass)

klass :


GTS_IS_PGEDGE()

#define             GTS_IS_PGEDGE(obj)

obj :


gts_pgedge_class ()

GtsPGEdgeClass *    gts_pgedge_class                    (void);

Returns :

the GtsPGEdgeClass.


gts_pgedge_new ()

GtsPGEdge *         gts_pgedge_new                      (GtsPGEdgeClass *klass,
                                                         GtsGNode *n1,
                                                         GtsGNode *n2,
                                                         gpointer data);

klass :

a GtsPGEdgeClass.

n1 :

a GtsGNode.

n2 :

another GtsGNode.

data :

user data.

Returns :

a new GtsPGEdge associated with data linking n1 and n2.


GtsWGEdge

typedef struct {
  GtsGEdge gedge;

  gfloat weight;
} GtsWGEdge;


GTS_WGEDGE()

#define             GTS_WGEDGE(obj)

obj :


GTS_WGEDGE_CLASS()

#define             GTS_WGEDGE_CLASS(klass)

klass :


GTS_IS_WGEDGE()

#define             GTS_IS_WGEDGE(obj)

obj :


gts_wgedge_class ()

GtsWGEdgeClass *    gts_wgedge_class                    (void);

Returns :

the GtsWGEdgeClass.


gts_wgedge_new ()

GtsWGEdge *         gts_wgedge_new                      (GtsWGEdgeClass *klass,
                                                         GtsGNode *n1,
                                                         GtsGNode *n2,
                                                         gfloat weight);

klass :

a GtsWGEdgeClass.

n1 :

a GtsGNode.

n2 :

another GtsGNode.

weight :

the weight of the new edge.

Returns :

a new GtsWGEdge of weight weight linking n1 and n2.


GtsGraph

typedef struct {
  GtsHashContainer object;

  GtsGraphClass * graph_class;
  GtsGNodeClass * node_class;
  GtsGEdgeClass * edge_class;
} GtsGraph;


GTS_GRAPH()

#define             GTS_GRAPH(obj)

obj :


GTS_GRAPH_CLASS()

#define             GTS_GRAPH_CLASS(klass)

klass :


GTS_IS_GRAPH()

#define             GTS_IS_GRAPH(obj)

obj :


gts_graph_class ()

GtsGraphClass *     gts_graph_class                     (void);

Returns :

the GtsGraphClass.


gts_graph_new ()

GtsGraph *          gts_graph_new                       (GtsGraphClass *klass,
                                                         GtsGNodeClass *node_class,
                                                         GtsGEdgeClass *edge_class);

klass :

a GtsGraphClass.

node_class :

a GtsGNodeClass.

edge_class :

a GtsGEdgeClass.

Returns :

a new GtsGraph using node_class and edge_class as node types.


gts_graph_print_stats ()

void                gts_graph_print_stats               (GtsGraph *g,
                                                         FILE *fp);

Writes to fp a summary of the properties of g.

g :

a GtsGraph.

fp :

a file pointer.


GtsGraphTraverse

typedef struct _GtsGraphTraverse GtsGraphTraverse;


enum GtsTraverseType

typedef enum   { GTS_BREADTH_FIRST
               }   GtsTraverseType;


gts_graph_traverse_new ()

GtsGraphTraverse *  gts_graph_traverse_new              (GtsGraph *g,
                                                         GtsGNode *n,
                                                         GtsTraverseType type,
                                                         gboolean reinit);

g :

a GtsGraph.

n :

a GtsGNode belonging to g.

type :

the type of traversal.

reinit :

if TRUE, the traversal is reinitialized.

Returns :

a new GtsGraphTraverse initialized for the traversal of g of type type, starting from n.


gts_graph_traverse_next ()

GtsGNode *          gts_graph_traverse_next             (GtsGraphTraverse *t);

t :

a GtsGraphTraverse.

Returns :

the next GtsGNode of the traversal defined by t or NULL if the traversal is complete.


gts_graph_traverse_what_next ()

GtsGNode *          gts_graph_traverse_what_next        (GtsGraphTraverse *t);

t :

a GtsGraphTraverse.

Returns :

the next GtsGNode of the traversal defined by t or NULL if the traversal is complete but without advancing the traversal.


gts_graph_traverse_destroy ()

void                gts_graph_traverse_destroy          (GtsGraphTraverse *t);

Frees all the memory allocated for t.

t :

a GtsGraphTraverse.


gts_graph_foreach_edge ()

void                gts_graph_foreach_edge              (GtsGraph *g,
                                                         GtsFunc func,
                                                         gpointer data);

Calls func for each GtsEdge of g.

g :

a GtsGraph.

func :

a GtsFunc.

data :

user data to be passed to func.


gts_graph_weight ()

gfloat              gts_graph_weight                    (GtsGraph *g);

g :

a GtsGraph.

Returns :

the weight of graph g as defined by the weight() method of GtsGraphClass.


gts_graph_distance_sum ()

guint               gts_graph_distance_sum              (GtsGraph *g,
                                                         GtsGNode *center);

g :

a GtsGraph.

center :

a GtsGNode of g.

Returns :

the sum of the distances between all the other GtsGNode of g and center.


gts_graph_farthest ()

GtsGNode *          gts_graph_farthest                  (GtsGraph *g,
                                                         GSList *gnodes);

g :

a GtsGraph.

gnodes :

a list of GtsGNode belonging to g.

Returns :

the GtsGNode belonging to g and farthest from all the nodes in gnodes (hmmm, definition of "farthest"?).


gts_graph_edges_cut ()

guint               gts_graph_edges_cut                 (GtsGraph *g);

g :

a GtsGraph.

Returns :

the number of edges of g connecting nodes belonging to g to nodes not belonging to g.


gts_graph_edges_cut_weight ()

gfloat              gts_graph_edges_cut_weight          (GtsGraph *g);

g :

a GtsGraph.

Returns :

the sum of the weights of the edges of g connecting nodes belonging to g to nodes not belonging to g.


gts_graph_write ()

void                gts_graph_write                     (GtsGraph *g,
                                                         FILE *fp);

Writes in the file fp an ASCII representation of g. The file format is as follows.

All the lines beginning with GTS_COMMENTS are ignored. The first line contains two unsigned integers separated by spaces. The first integer is the number of nodes, nn, the second is the number of edges, ne.

Follows nn lines containing node description. Follows ne lines containing the two indices (starting from one) of the nodes of each edge.

The format described above is the least common denominator to all GTS files. Consistent with an object-oriented approach, the GTS file format is extensible. Each of the lines of the file can be extended with user-specific attributes accessible through the read() and write() virtual methods of each of the objects written (graph, nodes or edges). When read with different object classes, these extra attributes are just ignored.

g :

a GtsGraph.

fp :

a file pointer.


gts_graph_write_dot ()

void                gts_graph_write_dot                 (GtsGraph *g,
                                                         FILE *fp);

Writes in the file fp an ASCII representation of g in the dot format of AT&T Bell Labs.

g :

a GtsGraph.

fp :

a file pointer.


gts_graph_read ()

GtsGraph *          gts_graph_read                      (GtsFile *fp);

Reads a graph from a file.

fp :

a GtsFile.

Returns :

the new GtsGraph or NULL if an error occured (in which case the error field of fp is set).


gts_graph_read_jostle ()

guint               gts_graph_read_jostle               (GtsGraph *g,
                                                         GtsFile *fp);

Adds to g the nodes and edges defined in the file pointed to by fp. This file must use the Jostle "graph" ASCII format. The nodes created are of type GtsNGNode and their identities are the line number at which they appear in fp.

g :

a GtsGraph.

fp :

a GtsFile.

Returns :

0 if the lecture was successful, the line number at which an error occured otherwise (in which case the error field of fp is set).


GtsWGraph

typedef struct {
  GtsGraph graph;

  gfloat weight;
} GtsWGraph;


GTS_WGRAPH()

#define             GTS_WGRAPH(obj)

obj :


GTS_WGRAPH_CLASS()

#define             GTS_WGRAPH_CLASS(klass)

klass :


GTS_IS_WGRAPH()

#define             GTS_IS_WGRAPH(obj)

obj :


gts_wgraph_class ()

GtsWGraphClass *    gts_wgraph_class                    (void);

Returns :

the GtsWGraphClass.


gts_wgraph_weight_max ()

gfloat              gts_wgraph_weight_max               (GtsWGraph *wg);

wg :

a GtsWGraph.

Returns :

the maximum weight of any vertices belonging to g.


gts_surface_graph_new ()

GtsGraph *          gts_surface_graph_new               (GtsGraphClass *klass,
                                                         GtsSurface *s);

klass :

a GtsGraphClass.

s :

a GtsSurface.

Returns :

a new GtsGraph representing the connectivity of the faces of s. This graph uses GtsFGNode as nodes which allows to store the dependencies between nodes and faces of s.


gts_surface_graph_surface ()

GtsSurface *        gts_surface_graph_surface           (GtsGraph *surface_graph,
                                                         GtsSurface *s);

surface_graph :

a GtsGraph using GtsFGNode as nodes.

s :

a GtsSurface.

Returns :

a new GtsSurface using the same classes as s and composed of the faces defined by surface_graph.


gts_segments_graph_new ()

GtsGraph *          gts_segments_graph_new              (GtsGraphClass *klass,
                                                         GSList *segments);

klass :

a GtsGraphClass.

segments :

a list of GtsSegment.

Returns :

a new GtsGraph representing the connectivity of the segments in segments.


GtsGNodeSplit

typedef struct {
  GtsObject object;

  GtsGNode * n;
  GtsObject * n1;
  GtsObject * n2;
} GtsGNodeSplit;


GTS_GNODE_SPLIT()

#define             GTS_GNODE_SPLIT(obj)

obj :


GTS_GNODE_SPLIT_CLASS()

#define             GTS_GNODE_SPLIT_CLASS(klass)

klass :


GTS_IS_GNODE_SPLIT()

#define             GTS_IS_GNODE_SPLIT(obj)

obj :


GTS_GNODE_SPLIT_N1()

#define GTS_GNODE_SPLIT_N1(ns) (GTS_IS_GNODE_SPLIT ((ns)->n1) ? GTS_GNODE_SPLIT ((ns)->n1)->n : GTS_GNODE ((ns)->n1))

ns :


GTS_GNODE_SPLIT_N2()

#define GTS_GNODE_SPLIT_N2(ns) (GTS_IS_GNODE_SPLIT ((ns)->n2) ? GTS_GNODE_SPLIT ((ns)->n2)->n : GTS_GNODE ((ns)->n2))

ns :


gts_gnode_split_class ()

GtsGNodeSplitClass * gts_gnode_split_class              (void);

Returns :

the GtsGNodeSplitClass.


gts_gnode_split_new ()

GtsGNodeSplit *     gts_gnode_split_new                 (GtsGNodeSplitClass *klass,
                                                         GtsGNode *n,
                                                         GtsObject *n1,
                                                         GtsObject *n2);

Creates a new GtsGNodeSplit which would collapse n1 and n2 into n. The collapse itself is not performed.

klass :

a GtsGNodeSplitClass.

n :

a GtsGNode.

n1 :

a GtsGNodeSplit or GtsGNode.

n2 :

a GtsGNodeSplit or GtsGNode.

Returns :

the new GtsGNodeSplit.


gts_gnode_split_collapse ()

void                gts_gnode_split_collapse            (GtsGNodeSplit *ns,
                                                         GtsGraph *g,
                                                         GtsWGEdgeClass *klass);

Collapses the node split ns. Any new edge created during the process will be of class klass.

ns :

a GtsGNodeSplit.

g :

a GtsGraph.

klass :

a GtsWGEdgeClass.


gts_gnode_split_expand ()

void                gts_gnode_split_expand              (GtsGNodeSplit *ns,
                                                         GtsGraph *g);

Expands the node split ns adding the new nodes to g.

ns :

a GtsGNodeSplit.

g :

a GtsGraph.


GtsPGraph

typedef struct {
  GtsObject object;

  GtsGraph * g;
  GPtrArray * split;
  GArray * levels;
  GtsGNodeSplitClass * split_class;
  GtsWGEdgeClass * edge_class;
  guint pos, min, level;
} GtsPGraph;


GTS_PGRAPH()

#define             GTS_PGRAPH(obj)

obj :


GTS_PGRAPH_CLASS()

#define             GTS_PGRAPH_CLASS(klass)

klass :


GTS_IS_PGRAPH()

#define             GTS_IS_PGRAPH(obj)

obj :


gts_pgraph_class ()

GtsPGraphClass *    gts_pgraph_class                    (void);

Returns :

the GtsPGraphClass.


gts_pgraph_new ()

GtsPGraph *         gts_pgraph_new                      (GtsPGraphClass *klass,
                                                         GtsGraph *g,
                                                         GtsGNodeSplitClass *split_class,
                                                         GtsWGNodeClass *node_class,
                                                         GtsWGEdgeClass *edge_class,
                                                         guint min);

Creates a new multilevel approximation of graph g. At each level a maximal matching is created using the Heavy Edge Matching (HEM) technique of Karypis and Kumar (1997). The newly created nodes are of type node_class and their weight is set to the sum of the weights of their children. The newly created edges are of type edge_class and their weight is set to the sum of the weight of the collapsed edges. The last level is reached when the maximal matching obtained would lead to a graph with less than min nodes.

klass :

a GtsPGraphClass.

g :

a GtsGraph.

split_class :

a GtsGNodeSplitClass.

node_class :

a GtsWGNodeClass.

edge_class :

a GtsWGEdgeClass.

min :

the minimum number of nodes.

Returns :

the new GtsPGraph containing the multilevel representation of g.


gts_pgraph_add_node ()

GtsGNodeSplit *     gts_pgraph_add_node                 (GtsPGraph *pg);

Adds one node to the multilevel graph pg by expanding the next available GtsGNodeSplit.

pg :

a GtsPGraph.

Returns :

the expanded GtsGNodeSplit or NULL if all the GtsGNodeSplit have already been expanded.


gts_pgraph_remove_node ()

GtsGNodeSplit *     gts_pgraph_remove_node              (GtsPGraph *pg);

Removes one node from the multilevel graph pg by collapsing the first available GtsGNodeSplit.

pg :

a GtsPGraph.

Returns :

the collapsed GtsGNodeSplit or NULL if all the GtsGNodeSplit have already been collapsed.


gts_pgraph_set_node_number ()

void                gts_pgraph_set_node_number          (GtsPGraph *pg,
                                                         guint n);

Performs the required number of collapses or expansions to set the number of nodes of pg to n.

pg :

a GtsPGraph.

n :

a number of nodes.


gts_pgraph_get_node_number ()

guint               gts_pgraph_get_node_number          (GtsPGraph *pg);

pg :

a GtsPGraph.

Returns :

the current number of nodes of pg.


gts_pgraph_min_node_number ()

guint               gts_pgraph_min_node_number          (GtsPGraph *pg);

pg :

a GtsPGraph.

Returns :

the minimum number of nodes of pg i.e. the number of nodes if all the GtsGNodeSplit were collapsed.


gts_pgraph_max_node_number ()

guint               gts_pgraph_max_node_number          (GtsPGraph *pg);

pg :

a GtsPGraph.

Returns :

the maximum number of nodes of pg i.e. the number of nodes if all the GtsGNodeSplit were expanded.


gts_pgraph_foreach_node ()

void                gts_pgraph_foreach_node             (GtsPGraph *pg,
                                                         GtsFunc func,
                                                         gpointer data);

pg :

func :

data :


gts_pgraph_down ()

gboolean            gts_pgraph_down                     (GtsPGraph *pg,
                                                         GtsFunc func,
                                                         gpointer data);

Performs the required number of expansions to go from the current level to the level immediately below.

If func is not NULL, it is called after each GtsGNodeSplit has been expanded.

pg :

a GtsPGraph.

func :

a GtsFunc or NULL.

data :

user data to pass to func.

Returns :

FALSE if it is not possible to go down one level, TRUE otherwise.


gts_graph_bubble_partition ()

GSList *            gts_graph_bubble_partition          (GtsGraph *g,
                                                         guint np,
                                                         guint niter,
                                                         GtsFunc step_info,
                                                         gpointer data);

An implementation of the "bubble partitioning algorithm" of Diekmann, Preis, Schlimbach and Walshaw (2000). The maximum number of iteration on the positions of the graph growing seeds is controlled by niter.

If not NULL step_info is called after each iteration on the seeds positions passing the partition (a GSList) as argument.

g :

a GtsGraph.

np :

number of partitions.

niter :

the maximum number of iterations.

step_info :

a GtsFunc or NULL.

data :

user data to pass to step_info.

Returns :

a list of np new GtsGraph representing the partition.


gts_graph_partition_edges_cut ()

guint               gts_graph_partition_edges_cut       (GSList *partition);

partition :

a list of GtsGraph representing a partition.

Returns :

the number of edges cut by the partition.


gts_graph_partition_edges_cut_weight ()

gfloat              gts_graph_partition_edges_cut_weight
                                                        (GSList *partition);

partition :

a list of GtsGraph representing a partition.

Returns :

the total weight of the edges cut by the partition.


gts_graph_partition_print_stats ()

void                gts_graph_partition_print_stats     (GSList *partition,
                                                         FILE *fp);

Writes to fp a summary of the properties of partition.

partition :

a list of GtsGraph representing a partition.

fp :

a file pointer.


gts_graph_partition_balance ()

gfloat              gts_graph_partition_balance         (GSList *partition);

partition :

a list of GtsGraph representing a partition.

Returns :

the difference between the maximum and the minimum weight of the graphs in partition.


gts_graph_partition_clone ()

GSList *            gts_graph_partition_clone           (GSList *partition);

partition :

a list of GtsGraph representing a partition.

Returns :

a new partition clone of partition (i.e. a list of new graphs clones of the graphs in partition).


gts_graph_recursive_bisection ()

GSList *            gts_graph_recursive_bisection       (GtsWGraph *wg,
                                                         guint n,
                                                         guint ntry,
                                                         guint mmax,
                                                         guint nmin,
                                                         gfloat imbalance);

Calls gts_graph_bisection_new() recursively in order to obtain a 2^n partition of wg.

wg :

a GtsWGraph.

n :

the number of bisection levels.

ntry :

the number of tries for the graph growing algorithm.

mmax :

the number of unsucessful moves for the refinement algorithm.

nmin :

the minimum number of nodes of the coarsest graph.

imbalance :

the maximum relative imbalance allowed between the weights of both halves of the partition.

Returns :

a list of 2^n new GtsGraph representing the partition.


gts_graph_partition_destroy ()

void                gts_graph_partition_destroy         (GSList *partition);

Destroys all the graphs in partition and frees partition.

partition :

a list of GtsGraph representing a partition.


GtsGraphBisection

typedef struct {
  GtsGraph * g;
  GtsGraph * g1;
  GtsGraph * g2;
  GHashTable * bg1;
  GHashTable * bg2;
} GtsGraphBisection;


gts_graph_bisection_check ()

gboolean            gts_graph_bisection_check           (GtsGraphBisection *bg);

Checks that the boundary of bg is correctly defined (used for debugging purposes).

bg :

a GtsGraphBisection.

Returns :

TRUE if bg is ok, FALSE otherwise.


gts_graph_ggg_bisection ()

GtsGraphBisection * gts_graph_ggg_bisection             (GtsGraph *g,
                                                         guint ntry);

An implementation of the "Greedy Graph Growing" algorithm of Karypis and Kumar (1997).

ntry randomly chosen seeds are used and the best partition is retained.

g :

a GtsGraph.

ntry :

the number of randomly selected initial seeds.

Returns :

a new GtsGraphBisection of g.


gts_graph_bfgg_bisection ()

GtsGraphBisection * gts_graph_bfgg_bisection            (GtsGraph *g,
                                                         guint ntry);

An implementation of a "Breadth-First Graph Growing" algorithm.

ntry randomly chosen seeds are used and the best partition is retained.

g :

a GtsGraph.

ntry :

the number of randomly selected initial seeds.

Returns :

a new GtsGraphBisection of g.


gts_graph_bisection_kl_refine ()

gdouble             gts_graph_bisection_kl_refine       (GtsGraphBisection *bg,
                                                         guint mmax);

An implementation of the simplified Kernighan-Lin algorithm for graph bisection refinement as described in Karypis and Kumar (1997).

The algorithm stops if mmax consecutive modes do not lead to a decrease in the number of edges cut. This last mmax moves are undone.

bg :

a GtsGraphBisection.

mmax :

the maximum number of unsuccessful successive moves.

Returns :

the decrease in the weight of the edges cut by the bisection.


gts_graph_bisection_bkl_refine ()

gdouble             gts_graph_bisection_bkl_refine      (GtsGraphBisection *bg,
                                                         guint mmax,
                                                         gfloat imbalance);

An implementation of the simplified boundary Kernighan-Lin algorithm for graph bisection refinement as described in Karypis and Kumar (1997).

The algorithm stops if mmax consecutive modes do not lead to a decrease in the number of edges cut. This last mmax moves are undone.

bg :

a GtsGraphBisection.

mmax :

the maximum number of unsuccessful successive moves.

imbalance :

the maximum relative imbalance allowed between the weights of both halves of the partition.

Returns :

the decrease in the weight of the edges cut by the bisection.


gts_graph_bisection_new ()

GtsGraphBisection * gts_graph_bisection_new             (GtsWGraph *wg,
                                                         guint ntry,
                                                         guint mmax,
                                                         guint nmin,
                                                         gfloat imbalance);

An implementation of a multilevel bisection algorithm as presented in Karypis and Kumar (1997). A multilevel hierarchy of graphs is created using the GtsPGraph object. The bisection of the coarsest graph is created using the gts_graph_ggg_bisection() function. The graph is then uncoarsened using gts_pgraph_down() and at each level the bisection is refined using gts_graph_bisection_bkl_refine().

wg :

a GtsWGraph.

ntry :

the number of tries for the graph growing algorithm.

mmax :

the number of unsucessful moves for the refinement algorithm.

nmin :

the minimum number of nodes of the coarsest graph.

imbalance :

the maximum relative imbalance allowed between the weights of both halves of the partition.

Returns :

a new GtsGraphBisection of wg.


gts_graph_bisection_destroy ()

void                gts_graph_bisection_destroy         (GtsGraphBisection *bg,
                                                         gboolean destroy_graphs);

Frees all the memory allocated for bg. If destroy_graphs is TRUE the graphs created by bg are destroyed.

bg :

a GtsGraphBisection.

destroy_graphs :

controls graph destruction.