vpred.h File Reference

Header file for the Geometric Predicates. More...

#include <maloc/maloc_base.h>

Include dependency graph for vpred.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Defines
#define	INEXACT
	Parameters and constants "INEXACT".
#define	REAL   double
	float or double
#define	REALPRINT   doubleprint
	Print the bit representation of a double.
#define	REALRAND   doublerand
	Generate a double with random 53-bit significand and a random exponent in [0, 511].
#define	NARROWRAND   narrowdoublerand
	Generate a double with random 53-bit significand and a random exponent in [0, 7].
#define	UNIFORMRAND   uniformdoublerand
	Generate a double with random 53-bit significand.
Functions
void	Vpred_exactinit (void)
	Initialize the variables used for exact arithmetic.
REAL	Vpred_orient2d (REAL *pa, REAL *pb, REAL *pc)
	Adaptive exact 2D orientation test. Robust.
REAL	Vpred_orient2dfast (REAL *pa, REAL *pb, REAL *pc)
	Approximate 2D orientation test. Nonrobust.
REAL	Vpred_orient2dexact (REAL *pa, REAL *pb, REAL *pc)
	Exact 2D orientation test. Robust.
REAL	Vpred_orient3d (REAL *pa, REAL *pb, REAL *pc, REAL *pd)
	Adaptive exact 3D orientation test. Robust.
REAL	Vpred_orient3dfast (REAL *pa, REAL *pb, REAL *pc, REAL *pd)
	Approximate 3D orientation test. Nonrobust.
REAL	Vpred_orient3dexact (REAL *pa, REAL *pb, REAL *pc, REAL *pd)
	Exact 3D orientation test. Robust.
REAL	Vpred_incircle (REAL *pa, REAL *pb, REAL *pc, REAL *pd)
	Adaptive exact 2D incircle test. Robust.
REAL	Vpred_incirclefast (REAL *pa, REAL *pb, REAL *pc, REAL *pd)
	Approximate 2D incircle test. Nonrobust.
REAL	Vpred_incircleexact (REAL *pa, REAL *pb, REAL *pc, REAL *pd)
	Exact 2D incircle test. Robust.
REAL	Vpred_insphere (REAL *pa, REAL *pb, REAL *pc, REAL *pd, REAL *pe)
	Adaptive exact 3D insphere test. Robust.
REAL	Vpred_inspherefast (REAL *pa, REAL *pb, REAL *pc, REAL *pd, REAL *pe)
	Approximate 3D insphere test. Nonrobust.
REAL	Vpred_insphereexact (REAL *pa, REAL *pb, REAL *pc, REAL *pd, REAL *pe)
	Exact 3D insphere test. Robust.

---

Detailed Description

Header file for the Geometric Predicates.

Version:

Id

vpred.h,v 1.3 2010/07/13 13:22:25 fetk Exp

Author:

Michael Holst

Attention:

 *
 * MALOC = < Minimal Abstraction Layer for Object-oriented C >
 * Copyright (C) 1994--2008 Michael Holst
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
 * 
 *  

---

Define Documentation

#define INEXACT

Parameters and constants "INEXACT".

#define NARROWRAND   narrowdoublerand

Generate a double with random 53-bit significand and a random exponent in [0, 7].

#define REAL   double

float or double

#define REALPRINT   doubleprint

Print the bit representation of a double.

#define REALRAND   doublerand

Generate a double with random 53-bit significand and a random exponent in [0, 511].

#define UNIFORMRAND   uniformdoublerand

Generate a double with random 53-bit significand.

---

Function Documentation

void Vpred_exactinit

(

void

)

Initialize the variables used for exact arithmetic.

Note:

`epsilon' is the largest power of two such that 1.0 + epsilon = 1.0 in floating-point arithmetic. `epsilon' bounds the relative roundoff error. It is used for floating-point error analysis. `splitter' is used to split floating-point numbers into two half- length significands for exact multiplication. I imagine that a highly optimizing compiler might be too smart for its own good, and somehow cause this routine to fail, if it pretends that floating-point arithmetic is too much like real arithmetic. Don't change this routine unless you fully understand it.

REAL Vpred_incircle	(	REAL *	pa,
		REAL *	pb,
		REAL *	pc,
		REAL *	pd
	)

Adaptive exact 2D incircle test. Robust.

Returns:

a positive value if the point pd lies inside the circle passing through pa, pb, and pc; a negative value if it lies outside; and zero if the four points are cocircular. The points pa, pb, and pc must be in counterclockwise order, or the sign of the result will be reversed.

Parameters:

	pa	Pointer to a real parameter
	pb	Pointer to a real parameter
	pc	Pointer to a real parameter
	pd	Pointer to a real parameter

REAL Vpred_incircleexact	(	REAL *	pa,
		REAL *	pb,
		REAL *	pc,
		REAL *	pd
	)

Exact 2D incircle test. Robust.

Returns:

a positive value if the point pd lies inside the circle passing through pa, pb, and pc; a negative value if it lies outside; and zero if the four points are cocircular. The points pa, pb, and pc must be in counterclockwise order, or the sign of the result will be reversed.

Parameters:

	pa	Pointer to a real parameter
	pb	Pointer to a real parameter
	pc	Pointer to a real parameter
	pd	Pointer to a real parameter

REAL Vpred_incirclefast	(	REAL *	pa,
		REAL *	pb,
		REAL *	pc,
		REAL *	pd
	)

Approximate 2D incircle test. Nonrobust.

Returns:

a positive value if the point pd lies inside the circle passing through pa, pb, and pc; a negative value if it lies outside; and zero if the four points are cocircular. The points pa, pb, and pc must be in counterclockwise order, or the sign of the result will be reversed.

Parameters:

	pa	Pointer to a real parameter
	pb	Pointer to a real parameter
	pc	Pointer to a real parameter
	pd	Pointer to a real parameter

REAL Vpred_insphere	(	REAL *	pa,
		REAL *	pb,
		REAL *	pc,
		REAL *	pd,
		REAL *	pe
	)

Adaptive exact 3D insphere test. Robust.

Returns:

a positive value if the point pe lies inside the sphere passing through pa, pb, pc, and pd; a negative value if it lies outside; and zero if the five points are cospherical. The points pa, pb, pc, and pd must be ordered so that they have a positive orientation (as defined by orient3d()), or the sign of the result will be reversed.

Parameters:

	pa	Pointer to a real parameter
	pb	Pointer to a real parameter
	pc	Pointer to a real parameter
	pd	Pointer to a real parameter
	pe	Pointer to a real parameter

REAL Vpred_insphereexact	(	REAL *	pa,
		REAL *	pb,
		REAL *	pc,
		REAL *	pd,
		REAL *	pe
	)

Exact 3D insphere test. Robust.

Returns:

a positive value if the point pe lies inside the sphere passing through pa, pb, pc, and pd; a negative value if it lies outside; and zero if the five points are cospherical. The points pa, pb, pc, and pd must be ordered so that they have a positive orientation (as defined by orient3d()), or the sign of the result will be reversed.

Parameters:

	pa	Pointer to a real parameter
	pb	Pointer to a real parameter
	pc	Pointer to a real parameter
	pd	Pointer to a real parameter
	pe	Pointer to a real parameter

REAL Vpred_inspherefast	(	REAL *	pa,
		REAL *	pb,
		REAL *	pc,
		REAL *	pd,
		REAL *	pe
	)

Approximate 3D insphere test. Nonrobust.

Returns:

a positive value if the point pe lies inside the sphere passing through pa, pb, pc, and pd; a negative value if it lies outside; and zero if the five points are cospherical. The points pa, pb, pc, and pd must be ordered so that they have a positive orientation (as defined by orient3d()), or the sign of the result will be reversed.

Parameters:

	pa	Pointer to a real parameter
	pb	Pointer to a real parameter
	pc	Pointer to a real parameter
	pd	Pointer to a real parameter
	pe	Pointer to a real parameter

REAL Vpred_orient2d	(	REAL *	pa,
		REAL *	pb,
		REAL *	pc
	)

Adaptive exact 2D orientation test. Robust.

Returns:

a positive value if the points pa, pb, and pc occur in counterclockwise order; a negative value if they occur in clockwise order; and zero if they are collinear. The result is also a rough approximation of twice the signed area of the triangle defined by the three points.

Parameters:

	pa	Pointer to a real parameter
	pb	Pointer to a real parameter
	pc	Pointer to a real parameter

REAL Vpred_orient2dexact	(	REAL *	pa,
		REAL *	pb,
		REAL *	pc
	)

Exact 2D orientation test. Robust.

Returns:

a positive value if the points pa, pb, and pc occur in counterclockwise order; a negative value if they occur in clockwise order; and zero if they are collinear. The result is also a rough approximation of twice the signed area of the triangle defined by the three points.

Parameters:

	pa	Pointer to a real parameter
	pb	Pointer to a real parameter
	pc	Pointer to a real parameter

REAL Vpred_orient2dfast	(	REAL *	pa,
		REAL *	pb,
		REAL *	pc
	)

Approximate 2D orientation test. Nonrobust.

Returns:

a positive value if the points pa, pb, and pc occur in counterclockwise order; a negative value if they occur in clockwise order; and zero if they are collinear. The result is also a rough approximation of twice the signed area of the triangle defined by the three points.

Parameters:

	pa	Pointer to a real parameter
	pb	Pointer to a real parameter
	pc	Pointer to a real parameter

REAL Vpred_orient3d	(	REAL *	pa,
		REAL *	pb,
		REAL *	pc,
		REAL *	pd
	)

Adaptive exact 3D orientation test. Robust.

Returns:

a positive value if the point pd lies below the plane passing through pa, pb, and pc; "below" is defined so that pa, pb, and pc appear in counterclockwise order when viewed from above the plane. Returns a negative value if pd lies above the plane. Returns zero if the points are coplanar. The result is also a rough approximation of six times the signed volume of the tetrahedron defined by the four points.

Parameters:

	pa	Pointer to a real parameter
	pb	Pointer to a real parameter
	pc	Pointer to a real parameter
	pd	Pointer to a real parameter

REAL Vpred_orient3dexact	(	REAL *	pa,
		REAL *	pb,
		REAL *	pc,
		REAL *	pd
	)

Exact 3D orientation test. Robust.

Returns:

a positive value if the point pd lies below the plane passing through pa, pb, and pc; "below" is defined so that pa, pb, and pc appear in counterclockwise order when viewed from above the plane. Returns a negative value if pd lies above the plane. Returns zero if the points are coplanar. The result is also a rough approximation of six times the signed volume of the tetrahedron defined by the four points.

Parameters:

	pa	Pointer to a real parameter
	pb	Pointer to a real parameter
	pc	Pointer to a real parameter
	pd	Pointer to a real parameter

REAL Vpred_orient3dfast	(	REAL *	pa,
		REAL *	pb,
		REAL *	pc,
		REAL *	pd
	)

Approximate 3D orientation test. Nonrobust.

Returns:

a positive value if the point pd lies below the plane passing through pa, pb, and pc; "below" is defined so that pa, pb, and pc appear in counterclockwise order when viewed from above the plane. Returns a negative value if pd lies above the plane. Returns zero if the points are coplanar. The result is also a rough approximation of six times the signed volume of the tetrahedron defined by the four points.

Parameters:

	pa	Pointer to a real parameter
	pb	Pointer to a real parameter
	pc	Pointer to a real parameter
	pd	Pointer to a real parameter