File size: 11,396 Bytes
10f2621 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 | /**
* @file vpred.h
* @brief 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
* @verbatim
*
* 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
*
* @endverbatim
*/
#ifndef _VPRED_H_
#define _VPRED_H_
#include <maloc/maloc_base.h>
/* random() prototype seems to be missing in <stdlib.h> */
/*
* if !defined(VOSF1)
* extern long int random(void);
* endif
*/
/* On some machines, the exact arithmetic routines might be defeated by the */
/* use of internal extended precision floating-point registers. Sometimes */
/* this problem can be fixed by defining certain values to be volatile, */
/* thus forcing them to be stored to memory and rounded off. This isn't */
/* a great solution, though, as it slows the arithmetic down. */
/* */
/* To try this out, write "#define INEXACT volatile" below. Normally, */
/* however, INEXACT should be defined to be nothing. ("#define INEXACT".) */
/** @brief Parameters and constants "INEXACT" */
#define INEXACT /* Nothing */
/* #define INEXACT volatile */
/** @brief float or double */
#define REAL double
/** @brief Print the bit representation of a double */
#define REALPRINT doubleprint
/** @brief Generate a double with random 53-bit significand and a
random exponent in [0, 511]. */
#define REALRAND doublerand
/** @brief Generate a double with random 53-bit significand
and a random exponent in [0, 7]. */
#define NARROWRAND narrowdoublerand
/** @brief Generate a double with random 53-bit significand. */
#define UNIFORMRAND uniformdoublerand
/**
* @brief 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);
/**
* @brief Adaptive exact 2D orientation test. Robust.
* @return 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.
* @param pa Pointer to a real parameter
* @param pb Pointer to a real parameter
* @param pc Pointer to a real parameter
*/
REAL Vpred_orient2d(REAL *pa, REAL *pb, REAL *pc);
/**
* @brief Approximate 2D orientation test. Nonrobust.
* @return 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.
* @param pa Pointer to a real parameter
* @param pb Pointer to a real parameter
* @param pc Pointer to a real parameter
*/
REAL Vpred_orient2dfast(REAL *pa, REAL *pb, REAL *pc);
/**
* @brief Exact 2D orientation test. Robust.
* @return 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.
* @param pa Pointer to a real parameter
* @param pb Pointer to a real parameter
* @param pc Pointer to a real parameter
*/
REAL Vpred_orient2dexact(REAL *pa, REAL *pb, REAL *pc);
/**
* @brief Adaptive exact 3D orientation test. Robust.
* @return 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.
* @param pa Pointer to a real parameter
* @param pb Pointer to a real parameter
* @param pc Pointer to a real parameter
* @param pd Pointer to a real parameter
*/
REAL Vpred_orient3d(REAL *pa, REAL *pb, REAL *pc, REAL *pd);
/**
* @brief Approximate 3D orientation test. Nonrobust.
* @return 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.
* @param pa Pointer to a real parameter
* @param pb Pointer to a real parameter
* @param pc Pointer to a real parameter
* @param pd Pointer to a real parameter
*/
REAL Vpred_orient3dfast(REAL *pa, REAL *pb, REAL *pc, REAL *pd);
/**
* @brief Exact 3D orientation test. Robust.
* @return 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.
* @param pa Pointer to a real parameter
* @param pb Pointer to a real parameter
* @param pc Pointer to a real parameter
* @param pd Pointer to a real parameter
*/
REAL Vpred_orient3dexact(REAL *pa, REAL *pb, REAL *pc, REAL *pd);
/**
* @brief Adaptive exact 2D incircle test. Robust.
* @return 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.
* @param pa Pointer to a real parameter
* @param pb Pointer to a real parameter
* @param pc Pointer to a real parameter
* @param pd Pointer to a real parameter
*/
REAL Vpred_incircle(REAL *pa, REAL *pb, REAL *pc, REAL *pd);
/**
* @brief Approximate 2D incircle test. Nonrobust.
* @return 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.
* @param pa Pointer to a real parameter
* @param pb Pointer to a real parameter
* @param pc Pointer to a real parameter
* @param pd Pointer to a real parameter
*/
REAL Vpred_incirclefast(REAL *pa, REAL *pb, REAL *pc, REAL *pd);
/**
* @brief Exact 2D incircle test. Robust.
* @return 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.
* @param pa Pointer to a real parameter
* @param pb Pointer to a real parameter
* @param pc Pointer to a real parameter
* @param pd Pointer to a real parameter
*/
REAL Vpred_incircleexact(REAL *pa, REAL *pb, REAL *pc, REAL *pd);
/**
* @brief Adaptive exact 3D insphere test. Robust.
* @return 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.
* @param pa Pointer to a real parameter
* @param pb Pointer to a real parameter
* @param pc Pointer to a real parameter
* @param pd Pointer to a real parameter
* @param pe Pointer to a real parameter
*/
REAL Vpred_insphere(REAL *pa, REAL *pb, REAL *pc, REAL *pd, REAL *pe);
/**
* @brief Approximate 3D insphere test. Nonrobust.
* @return 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.
* @param pa Pointer to a real parameter
* @param pb Pointer to a real parameter
* @param pc Pointer to a real parameter
* @param pd Pointer to a real parameter
* @param pe Pointer to a real parameter
*/
REAL Vpred_inspherefast(REAL *pa, REAL *pb, REAL *pc, REAL *pd, REAL *pe);
/**
* @brief Exact 3D insphere test. Robust.
* @return 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.
* @param pa Pointer to a real parameter
* @param pb Pointer to a real parameter
* @param pc Pointer to a real parameter
* @param pd Pointer to a real parameter
* @param pe Pointer to a real parameter
*/
REAL Vpred_insphereexact(REAL *pa, REAL *pb, REAL *pc, REAL *pd, REAL *pe);
#endif /* _VPRED_H_ */
|