1
#ifndef _SHEWCHUK_PREDICATES_H
2
#define _SHEWCHUK_PREDICATES_H
4
/*****************************************************************************/
6
/* Routines for Arbitrary Precision Floating-point Arithmetic */
7
/* and Fast Robust Geometric Predicates */
12
/* Placed in the public domain by */
13
/* Jonathan Richard Shewchuk */
14
/* School of Computer Science */
15
/* Carnegie Mellon University */
16
/* 5000 Forbes Avenue */
17
/* Pittsburgh, Pennsylvania 15213-3891 */
20
/* This file contains C implementation of algorithms for exact addition */
21
/* and multiplication of floating-point numbers, and predicates for */
22
/* robustly performing the orientation and incircle tests used in */
23
/* computational geometry. The algorithms and underlying theory are */
24
/* described in Jonathan Richard Shewchuk. "Adaptive Precision Floating- */
25
/* Point Arithmetic and Fast Robust Geometric Predicates." Technical */
26
/* Report CMU-CS-96-140, School of Computer Science, Carnegie Mellon */
27
/* University, Pittsburgh, Pennsylvania, May 1996. (Submitted to */
28
/* Discrete & Computational Geometry.) */
30
/* This file, the paper listed above, and other information are available */
31
/* from the Web page http://www.cs.cmu.edu/~quake/robust.html . */
33
/*****************************************************************************/
35
/*****************************************************************************/
37
/* Using this code: */
39
/* First, read the short or long version of the paper (from the Web page */
42
/* Be sure to call exactinit() once, before calling any of the arithmetic */
43
/* functions or geometric predicates. Also be sure to turn on the */
44
/* optimizer when compiling this file. */
47
/* Several geometric predicates are defined. Their parameters are all */
48
/* points. Each point is an array of two or three floating-point */
49
/* numbers. The geometric predicates, described in the papers, are */
51
/* orient2d(pa, pb, pc) */
52
/* orient2dfast(pa, pb, pc) */
53
/* orient3d(pa, pb, pc, pd) */
54
/* orient3dfast(pa, pb, pc, pd) */
55
/* incircle(pa, pb, pc, pd) */
56
/* incirclefast(pa, pb, pc, pd) */
57
/* insphere(pa, pb, pc, pd, pe) */
58
/* inspherefast(pa, pb, pc, pd, pe) */
60
/* Those with suffix "fast" are approximate, non-robust versions. Those */
61
/* without the suffix are adaptive precision, robust versions. There */
62
/* are also versions with the suffices "exact" and "slow", which are */
63
/* non-adaptive, exact arithmetic versions, which I use only for timings */
64
/* in my arithmetic papers. */
65
/*****************************************************************************/
70
double orient2dfast (double *pa, double *pb, double *pc);
71
double orient2dexact(double *pa, double *pb, double *pc);
72
double orient2dslow (double *pa, double *pb, double *pc);
73
double orient2d (double *pa, double *pb, double *pc);
75
double orient3dfast (double *pa, double *pb, double *pc, double *pd);
76
double orient3dexact(double *pa, double *pb, double *pc, double *pd);
77
double orient3dslow (double *pa, double *pb, double *pc, double *pd);
78
double orient3d (double *pa, double *pb, double *pc, double *pd);
81
#endif // _SHEWCHUK_PREDICATES_H