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.

## Macros

#define | INEXACT /* Nothing */
| 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

REAL | Vpred_orient2d (REAL *pa, REAL *pb, REAL *pc)
| Initialize the variables used for exact arithmetic.
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.4 2010/08/12 05:40:37 fetk Exp

Author
  Michael Holst

Attention

      *
      * MALOC = < Minimal Abstraction Layer for Object-oriented C >
      * Copyright (C) 1994-- 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
      *
      *

## Macro Definition Documentation

## INEXACT

#define INEXACT /* Nothing */

Parameters and constants "INEXACT".

## NARROWRAND

#define NARROWRAND narrowdoublerand

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

## REAL

#define REAL double

float or double

Referenced by Vpred_incircle(), Vpred_incircleexact(), Vpred_incirclefast(), Vpred_insphere(), Vpred_insphereexact(), Vpred_inspherefast(), Vpred_orient2d(), Vpred_orient2dexact(), Vpred_orient2dfast(), Vpred_orient3d(), Vpred_orient3dexact(), and Vpred_orient3dfast().

## REALPRINT

#define REALPRINT doubleprint

Print the bit representation of a double.

## REALRAND

#define REALRAND doublerand

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

## UNIFORMRAND

#define UNIFORMRAND uniformdoublerand

Generate a double with random 53-bit significand.

## Function Documentation

## Vpred_incircle()

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

References REAL.

## Vpred_incircleexact()

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

References REAL.

## Vpred_incirclefast()

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

References REAL.

## Vpred_insphere()

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

References REAL.

## Vpred_insphereexact()

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

References REAL.

## Vpred_inspherefast()

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

References REAL.

## Vpred_orient2d()

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

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. */ void Vpred_exactinit(void);

/**

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

References REAL.

## Vpred_orient2dexact()

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

References REAL.

## Vpred_orient2dfast()

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

References REAL.

## Vpred_orient3d()

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

References REAL.

## Vpred_orient3dexact()

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

References REAL.

## Vpred_orient3dfast()

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

References REAL.