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        (const gchar *s);
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 klass);
gpointer    gts_object_class_is_from_class  (gpointer klass,
                                             gpointer from);
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_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 (*check) (GtsVertex *, 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 (*compare) (const void *,const void *));
GSList*     gts_kdtree_range                (GNode *tree,
                                             GtsBBox *bbox,
                                             int (*compare) (const 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;
  gchar * s, * s1;
  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;
} 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
} 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        (const gchar *s);

s :

a string.

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,
                                             gpointer klass);

object :

a GtsObject.

klass :

a GtsObjectClass.

Returns :

object if object is of class klass or of a class derived from klass, NULL otherwise.


gts_object_class_is_from_class ()

gpointer    gts_object_class_is_from_class  (gpointer klass,
                                             gpointer from);

klass :

a GtsObjectClass.

from :

a GtsObjectClass.

Returns :

klass if klass is equal to from or if klass is derived from from, NULL otherwise.


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_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 (*check) (GtsVertex *, 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 (*compare) (const 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 (*compare) (const 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.