point.c File Reference

#include <math.h>
#include <stdlib.h>
#include "gts.h"
#include "gts-private.h"
#include "predicates.h"

Include dependency graph for point.c:

Go to the source code of this file.

Defines
#define	SIGN(x)   ((x) > 0. ? 1 : -1)
#define	ORIENT1D(a, b)   ((a) > (b) ? 1 : (a) < (b) ? -1 : 0)
Functions
static void	point_read (GtsObject **o, GtsFile *f)
static void	point_write (GtsObject *o, FILE *fptr)
static void	point_class_init (GtsObjectClass *klass)
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)
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)
GtsIntersect	gts_point_is_in_triangle (GtsPoint *p, GtsTriangle *t)
gdouble	gts_point_in_triangle_circle (GtsPoint *p, GtsTriangle *t)
gdouble	gts_point_in_circle (GtsPoint *p, GtsPoint *p1, GtsPoint *p2, GtsPoint *p3)
gdouble	gts_point_in_sphere (GtsPoint *p, GtsPoint *p1, GtsPoint *p2, GtsPoint *p3, GtsPoint *p4)
gdouble	gts_point_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)
GtsPoint *	gts_segment_triangle_intersection (GtsSegment *s, GtsTriangle *t, gboolean boundary, GtsPointClass *klass)
void	gts_point_transform (GtsPoint *p, GtsMatrix *m)
gdouble	gts_point_orientation (GtsPoint *p1, GtsPoint *p2, GtsPoint *p3)
static gboolean	ray_intersects_triangle (GtsPoint *D, GtsPoint *E, GtsTriangle *t)
gboolean	gts_point_is_inside_surface (GtsPoint *p, GNode *tree, gboolean is_open)
static gint	sortp (gpointer *p, guint n)
gint	gts_point_orientation_3d_sos (GtsPoint *p1, GtsPoint *p2, GtsPoint *p3, GtsPoint *p4)
gint	gts_point_orientation_sos (GtsPoint *p1, GtsPoint *p2, GtsPoint *p3)

---

Define Documentation

#define ORIENT1D	(		a,
			b
	)		((a) > (b) ? 1 : (a) < (b) ? -1 : 0)

Definition at line 778 of file point.c.

Referenced by gts_point_orientation_3d_sos(), and gts_point_orientation_sos().

#define SIGN

(

x

)

((x) > 0. ? 1 : -1)

Definition at line 777 of file point.c.

Referenced by gts_point_orientation_3d_sos(), and gts_point_orientation_sos().

---

Function Documentation

GtsPointClass* gts_point_class

(

void

)

gts_point_class:

Returns: the GtsPointClass.

Definition at line 93 of file point.c.

References gts_object_class(), gts_object_class_new(), and point_class_init().

Referenced by cluster_find(), gts_bb_tree_segment_distance(), gts_bb_tree_triangle_distance(), gts_point_is_inside_surface(), gts_point_locate(), gts_point_triangle_closest(), gts_vertex_class(), midpoint(), self_intersecting(), toporouter_bbox_locate(), and triangulate_face().

Here is the call graph for this function:

gdouble gts_point_distance	(	GtsPoint *	p1,
		GtsPoint *	p2
	)

gts_point_distance: : a GtsPoint. : another GtsPoint.

Returns: the Euclidean distance between and .

Definition at line 161 of file point.c.

References _GtsPoint::x, _GtsPoint::y, and _GtsPoint::z.

Referenced by calculate_arc_to_arc(), calculate_term_to_arc(), candidate_vertices(), edge_capacity(), edge_min_spacing(), gts_triangle_perimeter(), oproute_calculate_tof(), path_score(), pathvertex_arcing_through_constraint(), quality_foreach_edge(), simple_h_cost(), space_edge(), spread_edge(), surface_distance_foreach_boundary(), triangle_candidate_points_from_edge(), and triangle_candidate_points_from_vertex().

gdouble gts_point_distance2	(	GtsPoint *	p1,
		GtsPoint *	p2
	)

gts_point_distance2: : a GtsPoint. : another GtsPoint.

Returns: the square of the Euclidean distance between and .

Definition at line 177 of file point.c.

References _GtsPoint::x, _GtsPoint::y, and _GtsPoint::z.

Referenced by edge_closest_vertex(), edge_length2(), edge_length2_inverse(), edge_min_spacing(), edge_shape_cost(), gts_bb_tree_point_closest(), gts_point_segment_closest(), gts_point_segment_distance2(), gts_point_triangle_closest(), gts_volume_optimized_cost(), gts_volume_optimized_vertex(), region_area(), routing_edge_insert(), and triangle_interior_capacity().

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

gts_point_in_circle: : a GtsPoint. : a GtsPoint. : a GtsPoint. : a GtsPoint.

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

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

Definition at line 297 of file point.c.

References incircle(), and _GtsPoint::x.

Referenced by delaunay_check(), polygon_in_circle(), and swap_if_in_circle().

Here is the call graph for this function:

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

gts_point_in_sphere: : a GtsPoint. : a GtsPoint. : a GtsPoint. : a GtsPoint. : a GtsPoint.

Tests if is inside or outside the sphere defined by , , and .

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

Definition at line 324 of file point.c.

References insphere(), and _GtsPoint::x.

Here is the call graph for this function:

gdouble gts_point_in_triangle_circle	(	GtsPoint *	p,
		GtsTriangle *	t
	)

gts_point_in_triangle_circle: : a GtsPoint. : a GtsTriangle.

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

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

Definition at line 266 of file point.c.

References gts_triangle_vertices(), incircle(), and _GtsPoint::x.

Here is the call graph for this function:

GtsIntersect gts_point_is_in_triangle	(	GtsPoint *	p,
		GtsTriangle *	t
	)

gts_point_is_in_triangle: : a GtsPoint. : a GtsTriangle.

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

Returns: GTS_IN if is inside , GTS_ON if is on the boundary of , GTS_OUT otherwise.

Definition at line 230 of file point.c.

References FALSE, GTS_IN, GTS_ON, GTS_OUT, GTS_POINT, gts_point_orientation(), and gts_triangle_vertices().

Here is the call graph for this function:

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

gts_point_is_inside_surface: : a GtsPoint. : a bounding box tree of the faces of a closed, orientable surface (see gts_bb_tree_surface()). : TRUE if the surface defined by is "open" i.e. its volume is negative, FALSE otherwise.

Returns: TRUE if is inside the surface defined by , FALSE otherwise.

Definition at line 749 of file point.c.

References FALSE, gts_bb_tree_stabbed(), GTS_BBOX, GTS_OBJECT, gts_object_destroy(), gts_point_class(), gts_point_new(), GTS_TRIANGLE, ray_intersects_triangle(), _GtsBBox::x2, _GtsPoint::y, and _GtsPoint::z.

Here is the call graph for this function:

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

gts_point_new: : a GtsPointClass. : the x-coordinate. : the y-coordinate. : the z-coordinate.

Returns: a new GtsPoint.

Definition at line 123 of file point.c.

References GTS_OBJECT_CLASS, gts_object_new(), GTS_POINT, x, _GtsPoint::x, y, _GtsPoint::y, and _GtsPoint::z.

Referenced by cluster_find(), gts_point_is_inside_surface(), gts_triangle_circumcircle_center(), midpoint(), segment_triangle_intersection(), toporouter_bbox_locate(), and triangulate_face().

Here is the call graph for this function:

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

gts_point_orientation: : a GtsPoint. : a GtsPoint. : a GtsPoint.

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.

Returns: a positive value if , and appear in counterclockwise order, a negative value if they appear in clockwise order and zero if they are colinear.

Definition at line 696 of file point.c.

References orient2d(), and _GtsPoint::x.

Referenced by gts_delaunay_add_vertex_to_face(), gts_point_is_in_triangle(), gts_segments_are_intersecting(), gts_triangle_is_stabbed(), gts_triangle_orientation(), point_locate(), remove_intersected_edge(), remove_intersected_vertex(), split_list(), triangle_next_edge(), and triangulate_polygon().

Here is the call graph for this function:

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

gts_point_orientation_3d: : a GtsPoint. : a GtsPoint. : a GtsPoint. : a GtsPoint.

Checks if lies above, below or on the plane passing through the points , and . Below is defined so that , and 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.

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

Definition at line 205 of file point.c.

References orient3d(), and _GtsPoint::x.

Referenced by gts_segment_triangle_intersection(), gts_triangle_is_stabbed(), and segment_triangle_intersection().

Here is the call graph for this function:

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

gts_point_orientation_3d_sos: : a GtsPoint. : a GtsPoint. : a GtsPoint. : a GtsPoint.

Checks if lies above or below the plane passing through the points , and . Below is defined so that , and 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. lies on the plane defined by , and ).

Returns: +1 if lies below, -1 if lies above the plane.

Definition at line 816 of file point.c.

References c, ORIENT1D, orient2d(), orient3d(), sign, SIGN, sortp(), x, _GtsPoint::x, and y.

Referenced by add_edge_inter(), intersection_orientation(), ray_intersects_triangle(), segment_triangle_intersection(), triangle_point_orientation(), and triangle_triangle_orientation().

Here is the call graph for this function:

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

gts_point_orientation_sos: : a GtsPoint. : a GtsPoint. : a GtsPoint.

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. lies on the line defined by and ).

Returns: a positive value if , and appear in counterclockwise order or a negative value if they appear in clockwise order.

Definition at line 948 of file point.c.

References ORIENT1D, orient2d(), sign, SIGN, sortp(), x, _GtsPoint::x, and y.

Here is the call graph for this function:

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

gts_point_segment_closest: : a GtsPoint. : a GtsSegment. : a GtsPoint.

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

Definition at line 394 of file point.c.

References GTS_POINT, gts_point_distance2(), gts_point_set(), _GtsSegment::v1, _GtsSegment::v2, _GtsPoint::x, _GtsPoint::y, and _GtsPoint::z.

Referenced by gts_point_triangle_closest().

Here is the call graph for this function:

gdouble gts_point_segment_distance	(	GtsPoint *	p,
		GtsSegment *	s
	)

gts_point_segment_distance: : a GtsPoint. : a GtsSegment.

Returns: the minimun Euclidean distance between and .

Definition at line 377 of file point.c.

References gts_point_segment_distance2().

Referenced by gts_surface_distance().

Here is the call graph for this function:

gdouble gts_point_segment_distance2	(	GtsPoint *	p,
		GtsSegment *	s
	)

gts_point_segment_distance2: : a GtsPoint. : a GtsSegment.

Returns: the square of the minimun Euclidean distance between and .

Definition at line 344 of file point.c.

References GTS_POINT, gts_point_distance2(), _GtsSegment::v1, _GtsSegment::v2, _GtsPoint::x, x, _GtsPoint::y, y, and _GtsPoint::z.

Referenced by gts_point_segment_distance(), and gts_point_triangle_distance2().

Here is the call graph for this function:

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

gts_point_set: : a GtsPoint. : the x-coordinate. : the y-coordinate. : the z-coordinate.

Sets the coordinates of .

Definition at line 145 of file point.c.

References x, _GtsPoint::x, y, _GtsPoint::y, and _GtsPoint::z.

Referenced by gts_point_segment_closest(), gts_point_triangle_closest(), gts_segment_triangle_intersection(), and gts_vertex_new().

void gts_point_transform	(	GtsPoint *	p,
		GtsMatrix *	m
	)

gts_point_transform: : a GtsPoint. : the GtsMatrix representing the transformation to apply to the coordinates of .

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

Definition at line 670 of file point.c.

References _GtsPoint::x, x, _GtsPoint::y, y, and _GtsPoint::z.

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

gts_point_triangle_closest: : a GtsPoint. : a GtsTriangle. : a GtsPoint.

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

Definition at line 515 of file point.c.

References B, det(), GTS_OBJECT, GTS_OBJECT_CLASS, gts_object_destroy(), gts_object_new(), GTS_POINT, gts_point_class(), gts_point_distance2(), gts_point_segment_closest(), gts_point_set(), GTS_SEGMENT, gts_triangle_vertices_edges(), gts_vector_init, gts_vector_scalar, _GtsPoint::x, _GtsPoint::y, and _GtsPoint::z.

Here is the call graph for this function:

gdouble gts_point_triangle_distance	(	GtsPoint *	p,
		GtsTriangle *	t
	)

gts_point_triangle_distance: : a GtsPoint. : a GtsTriangle.

Returns: the minimun Euclidean distance between and .

Definition at line 498 of file point.c.

References gts_point_triangle_distance2().

Referenced by gts_surface_distance().

Here is the call graph for this function:

gdouble gts_point_triangle_distance2	(	GtsPoint *	p,
		GtsTriangle *	t
	)

gts_point_triangle_distance2: : a GtsPoint. : a GtsTriangle.

Returns: the square of the minimun Euclidean distance between and .

Definition at line 436 of file point.c.

References B, det(), gts_point_segment_distance2(), GTS_SEGMENT, gts_triangle_vertices_edges(), gts_vector_init, gts_vector_scalar, x, and y.

Referenced by gts_point_triangle_distance().

Here is the call graph for this function:

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

gts_segment_triangle_intersection: : a GtsSegment. : a GtsTriangle. : if TRUE, the boundary of is taken into account. : a GtsPointClass to be used for the new point.

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

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

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

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

Definition at line 597 of file point.c.

References B, c, _GtsTriangle::e1, GTS_OBJECT_CLASS, gts_object_new(), GTS_POINT, gts_point_orientation_3d(), gts_point_set(), GTS_SEGMENT, gts_triangle_vertex, _GtsSegment::v1, _GtsSegment::v2, _GtsPoint::x, _GtsPoint::y, and _GtsPoint::z.

Here is the call graph for this function:

static void point_class_init

(

GtsObjectClass *

klass

)

[static]

Definition at line 82 of file point.c.

References point_read(), point_write(), _GtsObjectClass::read, and _GtsObjectClass::write.

Referenced by gts_point_class().

Here is the call graph for this function:

static void point_read	(	GtsObject **	o,
		GtsFile *	f
	)		[static]

Definition at line 26 of file point.c.

References gts_file_error(), gts_file_next_token(), gts_file_read(), GTS_FLOAT, GTS_INT, GTS_POINT, GTS_POINT_CLASS, _GtsFile::token, _GtsFile::type, _GtsPoint::x, _GtsPoint::y, and _GtsPoint::z.

Referenced by point_class_init().

Here is the call graph for this function:

static void point_write	(	GtsObject *	o,
		FILE *	fptr
	)		[static]

Definition at line 69 of file point.c.

References GTS_POINT, GTS_POINT_CLASS, _GtsPoint::x, _GtsPoint::y, and _GtsPoint::z.

Referenced by point_class_init().

static gboolean ray_intersects_triangle	(	GtsPoint *	D,
		GtsPoint *	E,
		GtsTriangle *	t
	)		[static]

Definition at line 705 of file point.c.

References B, FALSE, gts_point_orientation_3d_sos(), gts_triangle_vertices(), and TRUE.

Referenced by gts_point_is_inside_surface().

Here is the call graph for this function:

static gint sortp	(	gpointer *	p,
		guint	n
	)		[static]

Definition at line 780 of file point.c.

References sign.

Referenced by gts_point_orientation_3d_sos(), and gts_point_orientation_sos().