#include <math.h>
#include "gts.h"

Include dependency graph for triangle.c:

Defines
#define	GOLDEN_PERIMETER 4.5590141139
#define	SQRT3 1.73205080757
#define	AREA_RATIO_MAX2 1e8
Functions
static void	triangle_destroy (GtsObject *object)
static void	triangle_class_init (GtsObjectClass *klass)
static void	triangle_init (GtsTriangle *triangle)
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)
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)
static gboolean	points_are_folded (GtsPoint A, GtsPoint B, GtsPoint C, GtsPoint D, gdouble max)
static GtsVertex *	triangle_use_vertices (GtsTriangle t, GtsVertex A, GtsVertex *B)
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 Documentation

#define AREA_RATIO_MAX2 1e8

Definition at line 884 of file triangle.c.

Referenced by points_are_folded().

#define GOLDEN_PERIMETER 4.5590141139

Definition at line 327 of file triangle.c.

Referenced by gts_triangle_quality().

#define SQRT3 1.73205080757

Definition at line 576 of file triangle.c.

Referenced by gts_triangle_enclosing().

Function Documentation

gdouble gts_triangle_area ( GtsTriangle * t )

gts_triangle_area: : a GtsTriangle.

Returns: the area of the triangle .

Definition at line 293 of file triangle.c.

References gts_triangle_normal(), x, and y.

Referenced by center_of_area_foreach_face(), gts_triangle_quality(), gts_vertex_principal_directions(), quality_foreach_face(), region_area(), sum_area(), surface_distance_foreach_triangle(), and triangle_cost().

Here is the call graph for this function:

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

gts_triangle_circumcircle_center: : a GtsTriangle. : a GtsPointClass.

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

Definition at line 853 of file triangle.c.

References det(), GTS_POINT, gts_point_new(), and gts_triangle_vertices().

Referenced by gts_delaunay_refine().

Here is the call graph for this function:

GtsTriangleClass* gts_triangle_class ( void )

gts_triangle_class:

Returns: the GtsTriangleClass.

Definition at line 63 of file triangle.c.

References gts_object_class(), gts_object_class_new(), triangle_class_init(), and triangle_init().

Referenced by build_cdt(), delaunay_create_from_vertices(), gts_face_class(), gts_triangle_enclosing(), and triangle_destroy().

Here is the call graph for this function:

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

gts_triangle_edge_opposite: : a GtsTriangle. : a GtsVertex of .

Returns: the edge of opposite or NULL if is not a vertice of .

Definition at line 197 of file triangle.c.

References _GtsTriangle::e1, _GtsTriangle::e2, _GtsTriangle::e3, GTS_SEGMENT, _GtsSegment::v1, and _GtsSegment::v2.

Referenced by angle_obtuse(), flow_from_edge_to_edge(), gts_edge_collapse_creates_fold(), region_area(), remove_intersected_vertex(), triangle_all_candidate_points_from_vertex(), triangle_candidate_points_from_vertex(), triangle_interior_capacity(), triangle_obtuse(), and vertex_encroaches().

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

gts_triangle_enclosing: : the class of the new triangle. : a list of GtsPoint. : a scaling factor (must be larger than one).

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

Returns: a new GtsTriangle.

Definition at line 593 of file triangle.c.

References gts_edge_class(), gts_edge_new(), GTS_POINT, gts_triangle_class(), gts_triangle_new(), gts_vertex_class(), gts_vertex_new(), scale, SQRT3, _GtsPoint::x, and _GtsPoint::y.

Referenced by build_cdt(), and delaunay_create_from_vertices().

Here is the call graph for this function:

void gts_triangle_interpolate_height	(	GtsTriangle *	t,
		GtsPoint *	p
	)

gts_triangle_interpolate_height: : a GtsTriangle. : a GtsPoint.

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

Definition at line 1067 of file triangle.c.

References det(), _GtsTriangle::e1, GTS_POINT, GTS_SEGMENT, gts_triangle_vertex, x, _GtsPoint::x, y, _GtsPoint::y, and _GtsPoint::z.

Here is the call graph for this function:

GtsTriangle* gts_triangle_is_duplicate ( GtsTriangle * t )

gts_triangle_is_duplicate: : a GtsTriangle.

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

Definition at line 714 of file triangle.c.

References _GtsTriangle::e1, _GtsTriangle::e2, _GtsTriangle::e3, and _GtsEdge::triangles.

Referenced by cface_new(), gts_edge_swap(), gts_split_collapse(), gts_triangle_is_ok(), and stats_foreach_face().

gboolean gts_triangle_is_ok ( GtsTriangle * t )

gts_triangle_is_ok: : a GtsTriangle.

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

Definition at line 775 of file triangle.c.

References _GtsTriangle::e1, _GtsTriangle::e2, _GtsTriangle::e3, FALSE, GTS_OBJECT, GTS_SEGMENT, gts_segments_touch, gts_triangle_is_duplicate(), and TRUE.

Here is the call graph for this function:

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

gts_triangle_is_stabbed: : a GtsTriangle. : a GtsPoint. : a pointer or NULL.

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

Definition at line 1002 of file triangle.c.

References GTS_OBJECT, GTS_POINT, gts_point_orientation(), gts_point_orientation_3d(), and gts_triangle_vertices_edges().

Here is the call graph for this function:

guint gts_triangle_neighbor_number ( GtsTriangle * t )

gts_triangle_neighbor_number: : a GtsTriangle.

Returns: the number of triangles neighbors of .

Definition at line 637 of file triangle.c.

References _GtsTriangle::e1, _GtsTriangle::e2, and _GtsTriangle::e3.

GSList* gts_triangle_neighbors ( GtsTriangle * t )

gts_triangle_neighbors: : a GtsTriangle.

Returns: a list of GtsTriangle neighbors of .

Definition at line 664 of file triangle.c.

References _GtsTriangle::e1, _GtsTriangle::e2, and _GtsTriangle::e3.

Referenced by tri_data_new().

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

gts_triangle_new: : a GtsTriangleClass. : a GtsEdge. : another GtsEdge touching . : another GtsEdge touching both and .

Returns: a new GtsTriangle having , and as edges.

Definition at line 141 of file triangle.c.

References GTS_OBJECT_CLASS, gts_object_new(), GTS_TRIANGLE, gts_triangle_set(), and opti_s::t.

Referenced by gts_triangle_enclosing().

Here is the call graph for this function:

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

gts_triangle_normal: : a GtsTriangle. : the x coordinate of the normal. : the y coordinate of the normal. : the z coordinate of the normal.

Computes the coordinates of the oriented normal of 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.

Definition at line 365 of file triangle.c.

References _GtsTriangle::e1, _GtsTriangle::e2, _GtsTriangle::e3, GTS_POINT, GTS_SEGMENT, _GtsPoint::x, _GtsPoint::y, and _GtsPoint::z.

Referenced by gts_triangle_area(), gts_triangles_angle(), gts_vertex_principal_directions(), and triangulate_face().

gdouble gts_triangle_orientation ( GtsTriangle * t )

gts_triangle_orientation: : a GtsTriangle.

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

Returns: a number depending on the orientation of the vertices of .

Definition at line 429 of file triangle.c.

References _GtsTriangle::e1, _GtsTriangle::e2, GTS_POINT, gts_point_orientation(), and GTS_SEGMENT.

Referenced by find_closest(), and gts_point_locate().

Here is the call graph for this function:

gdouble gts_triangle_perimeter ( GtsTriangle * t )

gts_triangle_perimeter: : a GtsTriangle.

Returns: the perimeter of the triangle .

Definition at line 310 of file triangle.c.

References _GtsTriangle::e1, GTS_POINT, gts_point_distance(), GTS_SEGMENT, and gts_triangle_vertex.

Referenced by gts_triangle_quality().

Here is the call graph for this function:

gdouble gts_triangle_quality ( GtsTriangle * t )

gts_triangle_quality: : a GtsTriangle.

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.

Returns: the quality of the triangle .

Definition at line 341 of file triangle.c.

References GOLDEN_PERIMETER, gts_triangle_area(), and gts_triangle_perimeter().

Referenced by quality_foreach_face(), and triangle_cost().

Here is the call graph for this function:

void gts_triangle_revert ( GtsTriangle * t )

gts_triangle_revert: : a GtsTriangle.

Changes the orientation of triangle , turning it inside out.

Definition at line 465 of file triangle.c.

References _GtsTriangle::e1, and _GtsTriangle::e2.

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

gts_triangle_set: : a GtsTriangle. : a GtsEdge. : another GtsEdge touching . : another GtsEdge touching both and .

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

Definition at line 94 of file triangle.c.

References _GtsTriangle::e1, _GtsTriangle::e2, _GtsTriangle::e3, GTS_SEGMENT, gts_segment_connect, and _GtsEdge::triangles.

Referenced by cface_expand(), gts_face_new(), and gts_triangle_new().

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

gts_triangle_use_edges: : a GtsEdge. : a GtsEdge. : a GtsEdge.

Returns: a GtsTriangle having , and as edges or NULL if , and are not part of any triangle.

Definition at line 745 of file triangle.c.

References _GtsTriangle::e1, _GtsTriangle::e2, _GtsTriangle::e3, opti_s::t, and _GtsEdge::triangles.

Referenced by check_speccut(), gts_cluster_grid_add_triangle(), gts_edge_belongs_to_tetrahedron(), and gts_edge_collapse_is_valid().

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

gts_triangle_vertex_opposite: : a GtsTriangle. : a GtsEdge used by .

This function fails if is not an edge of .

Returns: a GtsVertex, vertex of which does not belong to .

Definition at line 163 of file triangle.c.

References _GtsTriangle::e1, _GtsTriangle::e2, _GtsTriangle::e3, and GTS_SEGMENT.

Referenced by check_speccut(), compute_candidate_points(), gts_edge_is_encroached(), gts_vertex_principal_directions(), triangle_all_candidate_points_from_edge(), and triangle_candidate_points_from_edge().

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

gts_triangle_vertices: : a GtsTriangle. : a pointer on a GtsVertex. : a pointer on a GtsVertex. : a pointer on a GtsVertex.

Fills , and with the oriented set of vertices, summits of .

Definition at line 812 of file triangle.c.

References _GtsTriangle::e1, _GtsTriangle::e2, and GTS_SEGMENT.

Referenced by build_cdt(), center_of_area_foreach_face(), center_of_mass_foreach_face(), delaunay_check(), delaunay_create_from_vertices(), find_neighbor_backward(), find_neighbor_forward(), gts_bb_tree_triangle_distance(), gts_point_in_triangle_circle(), gts_point_is_in_triangle(), gts_surface_strip(), gts_triangle_circumcircle_center(), intersection_orientation(), ray_intersects_triangle(), remove_intersected_vertex(), vertex_normal_attributes(), volume_foreach_face(), write_face_oogl(), and write_face_vtk().

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

gts_triangle_vertices_edges: : a GtsTriangle. : a GtsEdge belonging to the edges of or NULL. : a GtsVertex used by . : a GtsVertex used by . : a GtsVertex used by . : a GtsEdge used by . : a GtsEdge used by . : a GtsEdge used by .

Given and , returns , , , , and . has and as vertices, has and as vertices and has and as vertices. , and respects the orientation of . If is not NULL, and are identical.

Definition at line 525 of file triangle.c.

References _GtsTriangle::e1, _GtsTriangle::e2, _GtsTriangle::e3, and GTS_SEGMENT.

Referenced by gts_delaunay_add_vertex_to_face(), gts_edge_swap(), gts_matrix_projection(), gts_point_triangle_closest(), gts_point_triangle_distance2(), gts_triangle_is_stabbed(), gts_vertex_fan_oriented(), intersection_orientation(), midvertex_insertion(), point_locate(), remove_intersected_edge(), remove_intersected_vertex(), segment_triangle_intersection(), and triangle_next_edge().

gdouble gts_triangles_angle	(	GtsTriangle *	t1,
		GtsTriangle *	t2
	)

gts_triangles_angle: : a GtsTriangle. : a GtsTriangle.

Returns: the value (in radians) of the angle between and .

Definition at line 226 of file triangle.c.

References gts_triangle_normal(), and M_PI.

Referenced by quality_foreach_edge().

Here is the call graph for this function:

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

gts_triangles_are_compatible: : a GtsTriangle. : a GtsTriangle. : a GtsEdge used by both and .

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

Returns: TRUE if and are compatible, FALSE otherwise.

Definition at line 259 of file triangle.c.

References _GtsTriangle::e1, _GtsTriangle::e2, _GtsTriangle::e3, FALSE, GTS_SEGMENT, and TRUE.

Referenced by next_compatible_face(), orientable_foreach_edge(), and triangle_is_incompatible().

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

gts_triangles_are_folded: : a list of GtsTriangle. : a GtsVertex. : another GtsVertex. : the maximum value of the square of the cosine of the angle between two triangles.

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

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

Definition at line 960 of file triangle.c.

References FALSE, GTS_POINT, points_are_folded(), triangle_use_vertices(), and TRUE.

Referenced by gts_edge_collapse_creates_fold().

Here is the call graph for this function: