geometry

predicates.c File Reference

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <sys/time.h>
#include "predicate-constants.h"

Defines

#define INEXACT
#define REAL   double
#define REALPRINT   doubleprint
#define REALRAND   doublerand
#define NARROWRAND   narrowdoublerand
#define UNIFORMRAND   uniformdoublerand
#define Absolute(a)   fabs(a)
#define Fast_Two_Sum_Tail(a, b, x, y)
#define Fast_Two_Sum(a, b, x, y)
#define Fast_Two_Diff_Tail(a, b, x, y)
#define Fast_Two_Diff(a, b, x, y)
#define Two_Sum_Tail(a, b, x, y)
#define Two_Sum(a, b, x, y)
#define Two_Diff_Tail(a, b, x, y)
#define Two_Diff(a, b, x, y)
#define Split(a, ahi, alo)
#define Two_Product_Tail(a, b, x, y)
#define Two_Product(a, b, x, y)
#define Two_Product_Presplit(a, b, bhi, blo, x, y)
#define Two_Product_2Presplit(a, ahi, alo, b, bhi, blo, x, y)
#define Square_Tail(a, x, y)
#define Square(a, x, y)
#define Two_One_Sum(a1, a0, b, x2, x1, x0)
#define Two_One_Diff(a1, a0, b, x2, x1, x0)
#define Two_Two_Sum(a1, a0, b1, b0, x3, x2, x1, x0)
#define Two_Two_Diff(a1, a0, b1, b0, x3, x2, x1, x0)
#define Four_One_Sum(a3, a2, a1, a0, b, x4, x3, x2, x1, x0)
#define Four_Two_Sum(a3, a2, a1, a0, b1, b0, x5, x4, x3, x2, x1, x0)
#define Four_Four_Sum(a3, a2, a1, a0, b4, b3, b1, b0, x7, x6, x5, x4, x3, x2, x1, x0)
#define Eight_One_Sum(a7, a6, a5, a4, a3, a2, a1, a0, b, x8, x7, x6, x5, x4, x3, x2, x1, x0)
#define Eight_Two_Sum(a7, a6, a5, a4, a3, a2, a1, a0, b1, b0, x9, x8, x7, x6, x5, x4, x3, x2, x1, x0)
#define Eight_Four_Sum(a7, a6, a5, a4, a3, a2, a1, a0, b4, b3, b1, b0, x11, x10, x9, x8, x7, x6, x5, x4, x3, x2, x1, x0)
#define Two_One_Product(a1, a0, b, x3, x2, x1, x0)
#define Four_One_Product(a3, a2, a1, a0, b, x7, x6, x5, x4, x3, x2, x1, x0)
#define Two_Two_Product(a1, a0, b1, b0, x7, x6, x5, x4, x3, x2, x1, x0)
#define Two_Square(a1, a0, x5, x4, x3, x2, x1, x0)

Functions

double doublerand ()
double narrowdoublerand ()
double uniformdoublerand ()
float floatrand ()
float narrowfloatrand ()
float uniformfloatrand ()
int grow_expansion (int elen, REAL *e, REAL b, REAL *h)
int grow_expansion_zeroelim (int elen, REAL *e, REAL b, REAL *h)
int expansion_sum (int elen, REAL *e, int flen, REAL *f, REAL *h)
int expansion_sum_zeroelim1 (int elen, REAL *e, int flen, REAL *f, REAL *h)
int expansion_sum_zeroelim2 (int elen, REAL *e, int flen, REAL *f, REAL *h)
int fast_expansion_sum (int elen, REAL *e, int flen, REAL *f, REAL *h)
int fast_expansion_sum_zeroelim (int elen, REAL *e, int flen, REAL *f, REAL *h)
int linear_expansion_sum (int elen, REAL *e, int flen, REAL *f, REAL *h)
int linear_expansion_sum_zeroelim (int elen, REAL *e, int flen, REAL *f, REAL *h)
int scale_expansion (int elen, REAL *e, REAL b, REAL *h)
int scale_expansion_zeroelim (int elen, REAL *e, REAL b, REAL *h)
int compress (int elen, REAL *e, REAL *h)
REAL estimate (int elen, REAL *e)
REAL orient2dfast (REAL *pa, REAL *pb, REAL *pc)
REAL orient2dexact (REAL *pa, REAL *pb, REAL *pc)
REAL orient2dslow (REAL *pa, REAL *pb, REAL *pc)
REAL orient2dadapt (REAL *pa, REAL *pb, REAL *pc, REAL detsum)
REAL orient2d (REAL *pa, REAL *pb, REAL *pc)
REAL orient3dfast (REAL *pa, REAL *pb, REAL *pc, REAL *pd)
REAL orient3dexact (REAL *pa, REAL *pb, REAL *pc, REAL *pd)
REAL orient3dslow (REAL *pa, REAL *pb, REAL *pc, REAL *pd)
REAL orient3dadapt (REAL *pa, REAL *pb, REAL *pc, REAL *pd, REAL permanent)
REAL orient3d (REAL *pa, REAL *pb, REAL *pc, REAL *pd)
REAL incirclefast (REAL *pa, REAL *pb, REAL *pc, REAL *pd)
REAL incircleexact (REAL *pa, REAL *pb, REAL *pc, REAL *pd)
REAL incircleslow (REAL *pa, REAL *pb, REAL *pc, REAL *pd)
REAL incircleadapt (REAL *pa, REAL *pb, REAL *pc, REAL *pd, REAL permanent)
REAL incircle (REAL *pa, REAL *pb, REAL *pc, REAL *pd)
REAL inspherefast (REAL *pa, REAL *pb, REAL *pc, REAL *pd, REAL *pe)
REAL insphereexact (REAL *pa, REAL *pb, REAL *pc, REAL *pd, REAL *pe)
REAL insphereslow (REAL *pa, REAL *pb, REAL *pc, REAL *pd, REAL *pe)
REAL insphereadapt (REAL *pa, REAL *pb, REAL *pc, REAL *pd, REAL *pe, REAL permanent)
REAL insphere (REAL *pa, REAL *pb, REAL *pc, REAL *pd, REAL *pe)

Define Documentation

#define Absolute (  a   )     fabs(a)
 

#define Eight_Four_Sum (  a7,
a6,
a5,
a4,
a3,
a2,
a1,
a0,
b4,
b3,
b1,
b0,
x11,
x10,
x9,
x8,
x7,
x6,
x5,
x4,
x3,
x2,
x1,
x0   ) 
 

Value:

Eight_Two_Sum(a7, a6, a5, a4, a3, a2, a1, a0, b1, b0, _l, _6, _5, _4, _3, \
                _2, _1, _0, x1, x0); \
  Eight_Two_Sum(_l, _6, _5, _4, _3, _2, _1, _0, b4, b3, x11, x10, x9, x8, \
                x7, x6, x5, x4, x3, x2)

#define Eight_One_Sum (  a7,
a6,
a5,
a4,
a3,
a2,
a1,
a0,
b,
x8,
x7,
x6,
x5,
x4,
x3,
x2,
x1,
x0   ) 
 

Value:

Four_One_Sum(a3, a2, a1, a0, b , _j, x3, x2, x1, x0); \
  Four_One_Sum(a7, a6, a5, a4, _j, x8, x7, x6, x5, x4)

#define Eight_Two_Sum (  a7,
a6,
a5,
a4,
a3,
a2,
a1,
a0,
b1,
b0,
x9,
x8,
x7,
x6,
x5,
x4,
x3,
x2,
x1,
x0   ) 
 

Value:

Eight_One_Sum(a7, a6, a5, a4, a3, a2, a1, a0, b0, _k, _6, _5, _4, _3, _2, \
                _1, _0, x0); \
  Eight_One_Sum(_k, _6, _5, _4, _3, _2, _1, _0, b1, x9, x8, x7, x6, x5, x4, \
                x3, x2, x1)

#define Fast_Two_Diff (  a,
b,
x,
y   ) 
 

Value:

x = (REAL) (a - b); \
  Fast_Two_Diff_Tail(a, b, x, y)

#define Fast_Two_Diff_Tail (  a,
b,
x,
y   ) 
 

Value:

bvirt = a - x; \
  y = bvirt - b

#define Fast_Two_Sum (  a,
b,
x,
y   ) 
 

Value:

x = (REAL) (a + b); \
  Fast_Two_Sum_Tail(a, b, x, y)

#define Fast_Two_Sum_Tail (  a,
b,
x,
y   ) 
 

Value:

bvirt = x - a; \
  y = b - bvirt

#define Four_Four_Sum (  a3,
a2,
a1,
a0,
b4,
b3,
b1,
b0,
x7,
x6,
x5,
x4,
x3,
x2,
x1,
x0   ) 
 

Value:

Four_Two_Sum(a3, a2, a1, a0, b1, b0, _l, _2, _1, _0, x1, x0); \
  Four_Two_Sum(_l, _2, _1, _0, b4, b3, x7, x6, x5, x4, x3, x2)

#define Four_One_Product (  a3,
a2,
a1,
a0,
b,
x7,
x6,
x5,
x4,
x3,
x2,
x1,
x0   ) 
 

Value:

Split(b, bhi, blo); \
  Two_Product_Presplit(a0, b, bhi, blo, _i, x0); \
  Two_Product_Presplit(a1, b, bhi, blo, _j, _0); \
  Two_Sum(_i, _0, _k, x1); \
  Fast_Two_Sum(_j, _k, _i, x2); \
  Two_Product_Presplit(a2, b, bhi, blo, _j, _0); \
  Two_Sum(_i, _0, _k, x3); \
  Fast_Two_Sum(_j, _k, _i, x4); \
  Two_Product_Presplit(a3, b, bhi, blo, _j, _0); \
  Two_Sum(_i, _0, _k, x5); \
  Fast_Two_Sum(_j, _k, x7, x6)

#define Four_One_Sum (  a3,
a2,
a1,
a0,
b,
x4,
x3,
x2,
x1,
x0   ) 
 

Value:

Two_One_Sum(a1, a0, b , _j, x1, x0); \
  Two_One_Sum(a3, a2, _j, x4, x3, x2)

#define Four_Two_Sum (  a3,
a2,
a1,
a0,
b1,
b0,
x5,
x4,
x3,
x2,
x1,
x0   ) 
 

Value:

Four_One_Sum(a3, a2, a1, a0, b0, _k, _2, _1, _0, x0); \
  Four_One_Sum(_k, _2, _1, _0, b1, x5, x4, x3, x2, x1)

#define INEXACT
 

#define NARROWRAND   narrowdoublerand
 

#define REAL   double
 

#define REALPRINT   doubleprint
 

#define REALRAND   doublerand
 

#define Split (  a,
ahi,
alo   ) 
 

Value:

c = (REAL) (splitter * a); \
  abig = (REAL) (c - a); \
  ahi = c - abig; \
  alo = a - ahi

#define Square (  a,
x,
y   ) 
 

Value:

x = (REAL) (a * a); \
  Square_Tail(a, x, y)

#define Square_Tail (  a,
x,
y   ) 
 

Value:

Split(a, ahi, alo); \
  err1 = x - (ahi * ahi); \
  err3 = err1 - ((ahi + ahi) * alo); \
  y = (alo * alo) - err3

#define Two_Diff (  a,
b,
x,
y   ) 
 

Value:

x = (REAL) (a - b); \
  Two_Diff_Tail(a, b, x, y)

#define Two_Diff_Tail (  a,
b,
x,
y   ) 
 

Value:

bvirt = (REAL) (a - x); \
  avirt = x + bvirt; \
  bround = bvirt - b; \
  around = a - avirt; \
  y = around + bround

#define Two_One_Diff (  a1,
a0,
b,
x2,
x1,
x0   ) 
 

Value:

Two_Diff(a0, b , _i, x0); \
  Two_Sum( a1, _i, x2, x1)

#define Two_One_Product (  a1,
a0,
b,
x3,
x2,
x1,
x0   ) 
 

Value:

Split(b, bhi, blo); \
  Two_Product_Presplit(a0, b, bhi, blo, _i, x0); \
  Two_Product_Presplit(a1, b, bhi, blo, _j, _0); \
  Two_Sum(_i, _0, _k, x1); \
  Fast_Two_Sum(_j, _k, x3, x2)

#define Two_One_Sum (  a1,
a0,
b,
x2,
x1,
x0   ) 
 

Value:

Two_Sum(a0, b , _i, x0); \
  Two_Sum(a1, _i, x2, x1)

#define Two_Product (  a,
b,
x,
y   ) 
 

Value:

x = (REAL) (a * b); \
  Two_Product_Tail(a, b, x, y)

#define Two_Product_2Presplit (  a,
ahi,
alo,
b,
bhi,
blo,
x,
y   ) 
 

Value:

x = (REAL) (a * b); \
  err1 = x - (ahi * bhi); \
  err2 = err1 - (alo * bhi); \
  err3 = err2 - (ahi * blo); \
  y = (alo * blo) - err3

#define Two_Product_Presplit (  a,
b,
bhi,
blo,
x,
y   ) 
 

Value:

x = (REAL) (a * b); \
  Split(a, ahi, alo); \
  err1 = x - (ahi * bhi); \
  err2 = err1 - (alo * bhi); \
  err3 = err2 - (ahi * blo); \
  y = (alo * blo) - err3

#define Two_Product_Tail (  a,
b,
x,
y   ) 
 

Value:

Split(a, ahi, alo); \
  Split(b, bhi, blo); \
  err1 = x - (ahi * bhi); \
  err2 = err1 - (alo * bhi); \
  err3 = err2 - (ahi * blo); \
  y = (alo * blo) - err3

#define Two_Square (  a1,
a0,
x5,
x4,
x3,
x2,
x1,
x0   ) 
 

Value:

Square(a0, _j, x0); \
  _0 = a0 + a0; \
  Two_Product(a1, _0, _k, _1); \
  Two_One_Sum(_k, _1, _j, _l, _2, x1); \
  Square(a1, _j, _1); \
  Two_Two_Sum(_j, _1, _l, _2, x5, x4, x3, x2)

#define Two_Sum (  a,
b,
x,
y   ) 
 

Value:

x = (REAL) (a + b); \
  Two_Sum_Tail(a, b, x, y)

#define Two_Sum_Tail (  a,
b,
x,
y   ) 
 

Value:

bvirt = (REAL) (x - a); \
  avirt = x - bvirt; \
  bround = b - bvirt; \
  around = a - avirt; \
  y = around + bround

#define Two_Two_Diff (  a1,
a0,
b1,
b0,
x3,
x2,
x1,
x0   ) 
 

Value:

Two_One_Diff(a1, a0, b0, _j, _0, x0); \
  Two_One_Diff(_j, _0, b1, x3, x2, x1)

#define Two_Two_Product (  a1,
a0,
b1,
b0,
x7,
x6,
x5,
x4,
x3,
x2,
x1,
x0   ) 
 

Value:

Split(a0, a0hi, a0lo); \
  Split(b0, bhi, blo); \
  Two_Product_2Presplit(a0, a0hi, a0lo, b0, bhi, blo, _i, x0); \
  Split(a1, a1hi, a1lo); \
  Two_Product_2Presplit(a1, a1hi, a1lo, b0, bhi, blo, _j, _0); \
  Two_Sum(_i, _0, _k, _1); \
  Fast_Two_Sum(_j, _k, _l, _2); \
  Split(b1, bhi, blo); \
  Two_Product_2Presplit(a0, a0hi, a0lo, b1, bhi, blo, _i, _0); \
  Two_Sum(_1, _0, _k, x1); \
  Two_Sum(_2, _k, _j, _1); \
  Two_Sum(_l, _j, _m, _2); \
  Two_Product_2Presplit(a1, a1hi, a1lo, b1, bhi, blo, _j, _0); \
  Two_Sum(_i, _0, _n, _0); \
  Two_Sum(_1, _0, _i, x2); \
  Two_Sum(_2, _i, _k, _1); \
  Two_Sum(_m, _k, _l, _2); \
  Two_Sum(_j, _n, _k, _0); \
  Two_Sum(_1, _0, _j, x3); \
  Two_Sum(_2, _j, _i, _1); \
  Two_Sum(_l, _i, _m, _2); \
  Two_Sum(_1, _k, _i, x4); \
  Two_Sum(_2, _i, _k, x5); \
  Two_Sum(_m, _k, x7, x6)

#define Two_Two_Sum (  a1,
a0,
b1,
b0,
x3,
x2,
x1,
x0   ) 
 

Value:

Two_One_Sum(a1, a0, b0, _j, _0, x0); \
  Two_One_Sum(_j, _0, b1, x3, x2, x1)

#define UNIFORMRAND   uniformdoublerand
 

Function Documentation

int compress (  int  elen,
REAL *  e,
REAL *  h
) 
 

double doublerand (   ) 
 

REAL estimate (  int  elen,
REAL *  e
) 
 

int expansion_sum (  int  elen,
REAL *  e,
int  flen,
REAL *  f,
REAL *  h
) 
 

int expansion_sum_zeroelim1 (  int  elen,
REAL *  e,
int  flen,
REAL *  f,
REAL *  h
) 
 

int expansion_sum_zeroelim2 (  int  elen,
REAL *  e,
int  flen,
REAL *  f,
REAL *  h
) 
 

int fast_expansion_sum (  int  elen,
REAL *  e,
int  flen,
REAL *  f,
REAL *  h
) 
 

int fast_expansion_sum_zeroelim (  int  elen,
REAL *  e,
int  flen,
REAL *  f,
REAL *  h
) 
 

float floatrand (   ) 
 

int grow_expansion (  int  elen,
REAL *  e,
REAL  b,
REAL *  h
) 
 

int grow_expansion_zeroelim (  int  elen,
REAL *  e,
REAL  b,
REAL *  h
) 
 

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

REAL incircleadapt (  REAL *  pa,
REAL *  pb,
REAL *  pc,
REAL *  pd,
REAL  permanent
) 
 

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

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

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

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

REAL insphereadapt (  REAL *  pa,
REAL *  pb,
REAL *  pc,
REAL *  pd,
REAL *  pe,
REAL  permanent
) 
 

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

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

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

int linear_expansion_sum (  int  elen,
REAL *  e,
int  flen,
REAL *  f,
REAL *  h
) 
 

int linear_expansion_sum_zeroelim (  int  elen,
REAL *  e,
int  flen,
REAL *  f,
REAL *  h
) 
 

double narrowdoublerand (   ) 
 

float narrowfloatrand (   ) 
 

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

REAL orient2dadapt (  REAL *  pa,
REAL *  pb,
REAL *  pc,
REAL  detsum
) 
 

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

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

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

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

REAL orient3dadapt (  REAL *  pa,
REAL *  pb,
REAL *  pc,
REAL *  pd,
REAL  permanent
) 
 

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

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

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

int scale_expansion (  int  elen,
REAL *  e,
REAL  b,
REAL *  h
) 
 

int scale_expansion_zeroelim (  int  elen,
REAL *  e,
REAL  b,
REAL *  h
) 
 

double uniformdoublerand (   ) 
 

float uniformfloatrand (   ) 
 

Generated on Thu Mar 27 19:04:15 2008 by  doxygen 1.4.6