#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include "predicates.h"
#include "rounding.h"

Include dependency graph for predicates.c:

Defines
#define	INEXACT
#define	REAL double
#define	REALPRINT doubleprint
#define	REALRAND doublerand
#define	NARROWRAND narrowdoublerand
#define	UNIFORMRAND uniformdoublerand
#define	Absolute(a) ((a) >= 0.0 ? (a) : -(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
void	gts_predicates_init ()
static int	fast_expansion_sum_zeroelim (int elen, REAL e, int flen, REAL f, REAL *h)
static int	scale_expansion_zeroelim (int elen, REAL e, REAL b, REAL h)
static REAL	estimate (int elen, REAL *e)
static REAL	orient2dadapt (REAL pa, REAL pb, REAL *pc, REAL detsum)
REAL	orient2d (REAL pa, REAL pb, REAL *pc)
static REAL	orient3dadapt (REAL pa, REAL pb, REAL pc, REAL pd, REAL permanent)
REAL	orient3d (REAL pa, REAL pb, REAL pc, REAL pd)
static REAL	incircleadapt (REAL pa, REAL pb, REAL pc, REAL pd, REAL permanent)
REAL	incircle (REAL pa, REAL pb, REAL pc, REAL pd)
static REAL	insphereexact (REAL pa, REAL pb, REAL pc, REAL pd, REAL *pe)
static 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)
Variables
static REAL	splitter
static REAL	resulterrbound
static REAL	ccwerrboundA
static REAL	ccwerrboundB
static REAL	ccwerrboundC
static REAL	o3derrboundA
static REAL	o3derrboundB
static REAL	o3derrboundC
static REAL	iccerrboundA
static REAL	iccerrboundB
static REAL	iccerrboundC
static REAL	isperrboundA
static REAL	isperrboundB
static REAL	isperrboundC

Define Documentation

#define Absolute ( a ) ((a) >= 0.0 ? (a) : -(a))

Definition at line 155 of file predicates.c.

Referenced by incircle(), incircleadapt(), insphere(), insphereadapt(), orient2dadapt(), orient3d(), and orient3dadapt().

#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)

Definition at line 304 of file predicates.c.

#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)

Definition at line 292 of file predicates.c.

#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)

Definition at line 297 of file predicates.c.

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

Value:

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

Definition at line 183 of file predicates.c.

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

Value:

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

Definition at line 179 of file predicates.c.

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

Value:

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

Definition at line 175 of file predicates.c.

Referenced by fast_expansion_sum_zeroelim(), and scale_expansion_zeroelim().

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

Value:

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

Definition at line 171 of file predicates.c.

#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)

Definition at line 287 of file predicates.c.

#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)

Definition at line 320 of file predicates.c.

#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)

Definition at line 279 of file predicates.c.

#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)

Definition at line 283 of file predicates.c.

#define INEXACT

Definition at line 140 of file predicates.c.

Referenced by fast_expansion_sum_zeroelim(), incircleadapt(), insphereadapt(), insphereexact(), orient2dadapt(), orient3dadapt(), and scale_expansion_zeroelim().

#define NARROWRAND narrowdoublerand

Definition at line 146 of file predicates.c.

#define REAL double

Definition at line 143 of file predicates.c.

Referenced by estimate(), fast_expansion_sum_zeroelim(), incircle(), incircleadapt(), insphere(), insphereadapt(), insphereexact(), orient2d(), orient2dadapt(), orient3d(), orient3dadapt(), and scale_expansion_zeroelim().

#define REALPRINT doubleprint

Definition at line 144 of file predicates.c.

#define REALRAND doublerand

Definition at line 145 of file predicates.c.

#define Split	(	a,
		ahi,
		alo
	)

Value:

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

Definition at line 209 of file predicates.c.

Referenced by scale_expansion_zeroelim().

#define Square	(	a,
		x,
		y
	)

Value:

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

Definition at line 256 of file predicates.c.

Referenced by incircleadapt().

#define Square_Tail	(	a,
		x,
		y
	)

Value:

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

Definition at line 250 of file predicates.c.

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

Value:

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

Definition at line 205 of file predicates.c.

#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

Definition at line 198 of file predicates.c.

Referenced by incircleadapt(), insphereadapt(), orient2dadapt(), and orient3dadapt().

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

Value:

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

Definition at line 267 of file predicates.c.

#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)

Definition at line 313 of file predicates.c.

Referenced by orient3dadapt().

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

Value:

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

Definition at line 263 of file predicates.c.

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

Value:

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

Definition at line 223 of file predicates.c.

Referenced by incircleadapt(), insphereadapt(), insphereexact(), orient2dadapt(), and orient3dadapt().

#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

Definition at line 241 of file predicates.c.

#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

Definition at line 230 of file predicates.c.

Referenced by scale_expansion_zeroelim().

#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

Definition at line 215 of file predicates.c.

#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)

Definition at line 363 of file predicates.c.

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

Value:

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

Definition at line 194 of file predicates.c.

Referenced by fast_expansion_sum_zeroelim(), and scale_expansion_zeroelim().

#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

Definition at line 187 of file predicates.c.

#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)

Definition at line 275 of file predicates.c.

Referenced by incircleadapt(), insphereadapt(), insphereexact(), orient2dadapt(), and orient3dadapt().

#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)

Definition at line 333 of file predicates.c.

#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)

Definition at line 271 of file predicates.c.

Referenced by incircleadapt().

#define UNIFORMRAND uniformdoublerand

Definition at line 147 of file predicates.c.

Function Documentation

static REAL estimate	(	int	elen,
		REAL *	e
	)		`[static]`

Definition at line 843 of file predicates.c.

References REAL.

Referenced by incircleadapt(), insphereadapt(), orient2dadapt(), and orient3dadapt().

static int fast_expansion_sum_zeroelim	(	int	elen,
		REAL *	e,
		int	flen,
		REAL *	f,
		REAL *	h
	)		`[static]`

Definition at line 709 of file predicates.c.

References Fast_Two_Sum, INEXACT, REAL, and Two_Sum.

Referenced by incircleadapt(), insphereadapt(), insphereexact(), orient2dadapt(), and orient3dadapt().

void gts_predicates_init ( )

Definition at line 382 of file predicates.c.

References ccwerrboundA, ccwerrboundB, ccwerrboundC, check, FPU_RESTORE, FPU_ROUND_DOUBLE, iccerrboundA, iccerrboundB, iccerrboundC, isperrboundA, isperrboundB, isperrboundC, o3derrboundA, o3derrboundB, o3derrboundC, resulterrbound, and splitter.

Referenced by toporouter_new().

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

Definition at line 2085 of file predicates.c.

References Absolute, det(), FPU_RESTORE, FPU_ROUND_DOUBLE, iccerrboundA, incircleadapt(), and REAL.

Referenced by gts_point_in_circle(), and gts_point_in_triangle_circle().