public final class Geometry
extends java.lang.Object
These geometric predicates are notoriously susceptible to roundoff error. For example, the simplest and fastest test to determine whether a point c is left of a line defined by two points a and b may fail when all three points are nearly co-linear.
Therefore, each predicate is implemented by two types of methods. One method is fast, but may yield incorrect answers. The other method is slower, because it (1) computes a bound on the roundoff error and (2) reverts to an exact algorithm if the fast method might yield the wrong answer.
Most applications should use the slower exact methods. The fast methods are provided only for comparison.
These predicates are adapted from those developed by Jonathan Shewchuk, 1997, Delaunay Refinement Mesh Generation: Ph.D. dissertation, Carnegie Mellon University. (Currently, the methods here do not use Shewchuk's adaptive four-stage pipeline. Instead, only two - the fastest and the exact stages - are used.)
Constructor and Description |
---|
Geometry() |
Modifier and Type | Method and Description |
---|---|
static void |
centerCircle(double[] pa,
double[] pb,
double[] pc,
double[] po)
Computes the center of the circle defined by the points a, b, and c.
|
static void |
centerCircle(double xa,
double ya,
double xb,
double yb,
double xc,
double yc,
double[] po)
Computes the center of the circle defined by the points a, b, and c.
|
static void |
centerCircle(float[] pa,
float[] pb,
float[] pc,
float[] po)
Computes the center of the circle defined by the points a, b, and c.
|
static void |
centerCircle(float xa,
float ya,
float xb,
float yb,
float xc,
float yc,
float[] po)
Computes the center of the circle defined by the points a, b, and c.
|
static void |
centerCircle3D(double xa,
double ya,
double za,
double xb,
double yb,
double zb,
double xc,
double yc,
double zc,
double[] po)
Computes the center of the circle defined by the 3-D points a, b, and c.
|
static void |
centerSphere(double[] pa,
double[] pb,
double[] pc,
double[] pd,
double[] po)
Computes the center of the sphere defined by the points a, b, c, and d.
|
static void |
centerSphere(double xa,
double ya,
double za,
double xb,
double yb,
double zb,
double xc,
double yc,
double zc,
double xd,
double yd,
double zd,
double[] po)
Computes the center of the sphere defined by the points a, b, c, and d.
|
static void |
centerSphere(float[] pa,
float[] pb,
float[] pc,
float[] pd,
float[] po)
Computes the center of the sphere defined by the points a, b, c, and d.
|
static void |
centerSphere(float xa,
float ya,
float za,
float xb,
float yb,
float zb,
float xc,
float yc,
float zc,
float xd,
float yd,
float zd,
float[] po)
Computes the center of the sphere defined by the points a, b, c, and d.
|
static double |
inCircle(double[] pa,
double[] pb,
double[] pc,
double[] pd)
Determines if a point d is inside the circle defined by the points
a, b, and c.
|
static double |
inCircle(double xa,
double ya,
double xb,
double yb,
double xc,
double yc,
double xd,
double yd)
Determines if a point d is inside the circle defined by the points
a, b, and c.
|
static double |
inCircle(float[] pa,
float[] pb,
float[] pc,
float[] pd)
Determines if a point d is inside the circle defined by the points
a, b, and c.
|
static double |
inCircleFast(double[] pa,
double[] pb,
double[] pc,
double[] pd)
Determines if a point d is inside the circle defined by the points
a, b, and c.
|
static double |
inCircleFast(double xa,
double ya,
double xb,
double yb,
double xc,
double yc,
double xd,
double yd)
Determines if a point d is inside the circle defined by the points
a, b, and c.
|
static double |
inCircleFast(float[] pa,
float[] pb,
float[] pc,
float[] pd)
Determines if a point d is inside the circle defined by the points
a, b, and c.
|
static double |
inOrthoSphere(double[] pa,
double[] pb,
double[] pc,
double[] pd,
double[] pe)
Determines whether or not a weighted point e is inside the
ortho-sphere defined by the weighted points a, b, c, and d.
|
static double |
inOrthoSphere(double xa,
double ya,
double za,
double wa,
double xb,
double yb,
double zb,
double wb,
double xc,
double yc,
double zc,
double wc,
double xd,
double yd,
double zd,
double wd,
double xe,
double ye,
double ze,
double we)
Determines whether or not a weighted point e is inside the
ortho-sphere defined by the weighted points a, b, c, and d.
|
static double |
inOrthoSphere(float[] pa,
float[] pb,
float[] pc,
float[] pd,
float[] pe)
Determines whether or not a weighted point e is inside the
ortho-sphere defined by the weighted points a, b, c, and d.
|
static double |
inOrthoSphereFast(double[] pa,
double[] pb,
double[] pc,
double[] pd,
double[] pe)
Determines whether or not a weighted point e is inside the
ortho-sphere defined by the weighted points a, b, c, and d.
|
static double |
inOrthoSphereFast(double xa,
double ya,
double za,
double wa,
double xb,
double yb,
double zb,
double wb,
double xc,
double yc,
double zc,
double wc,
double xd,
double yd,
double zd,
double wd,
double xe,
double ye,
double ze,
double we)
Determines whether or not a weighted point e is inside the
ortho-sphere defined by the weighted points a, b, c, and d.
|
static double |
inOrthoSphereFast(float[] pa,
float[] pb,
float[] pc,
float[] pd,
float[] pe)
Determines whether or not a weighted point e is inside the
ortho-sphere defined by the weighted points a, b, c, and d.
|
static double |
inSphere(double[] pa,
double[] pb,
double[] pc,
double[] pd,
double[] pe)
Determines if a point e is inside the sphere defined by the points
a, b, c, and d.
|
static double |
inSphere(double xa,
double ya,
double za,
double xb,
double yb,
double zb,
double xc,
double yc,
double zc,
double xd,
double yd,
double zd,
double xe,
double ye,
double ze)
Determines if a point e is inside the sphere defined by the points
a, b, c, and d.
|
static double |
inSphere(float[] pa,
float[] pb,
float[] pc,
float[] pd,
float[] pe)
Determines if a point e is inside the sphere defined by the points
a, b, c, and d.
|
static double |
inSphereFast(double[] pa,
double[] pb,
double[] pc,
double[] pd,
double[] pe)
Determines if a point e is inside the sphere defined by the points
a, b, c, and d.
|
static double |
inSphereFast(double xa,
double ya,
double za,
double xb,
double yb,
double zb,
double xc,
double yc,
double zc,
double xd,
double yd,
double zd,
double xe,
double ye,
double ze)
Determines if a point e is inside the sphere defined by the points
a, b, c, and d.
|
static double |
inSphereFast(float[] pa,
float[] pb,
float[] pc,
float[] pd,
float[] pe)
Determines if a point e is inside the sphere defined by the points
a, b, c, and d.
|
static double |
leftOfLine(double[] pa,
double[] pb,
double[] pc)
Determines if a point c is left of the line defined by the
points a and b.
|
static double |
leftOfLine(double xa,
double ya,
double xb,
double yb,
double xc,
double yc)
Determines if a point c is left of the line defined by the
points a and b.
|
static double |
leftOfLine(float[] pa,
float[] pb,
float[] pc)
Determines if a point c is left of the line defined by the
points a and b.
|
static double |
leftOfLineFast(double[] pa,
double[] pb,
double[] pc)
Determines if a point c is left of the line defined by the
points a and b.
|
static double |
leftOfLineFast(double xa,
double ya,
double xb,
double yb,
double xc,
double yc)
Determines if a point c is left of the line defined by the
points a and b.
|
static double |
leftOfLineFast(float[] pa,
float[] pb,
float[] pc)
Determines if a point c is left of the line defined by the
points a and b.
|
static double |
leftOfPlane(double[] pa,
double[] pb,
double[] pc,
double[] pd)
Determines if a point d is left of the plane defined by the
points a, b, and c.
|
static double |
leftOfPlane(double xa,
double ya,
double za,
double xb,
double yb,
double zb,
double xc,
double yc,
double zc,
double xd,
double yd,
double zd)
Determines if a point d is left of the plane defined by the
points a, b, and c.
|
static double |
leftOfPlane(float[] pa,
float[] pb,
float[] pc,
float[] pd)
Determines if a point d is left of the plane defined by the
points a, b, and c.
|
static double |
leftOfPlaneFast(double[] pa,
double[] pb,
double[] pc,
double[] pd)
Determines if a point d is left of the plane defined by the
points a, b, and c.
|
static double |
leftOfPlaneFast(double xa,
double ya,
double za,
double xb,
double yb,
double zb,
double xc,
double yc,
double zc,
double xd,
double yd,
double zd)
Determines if a point d is left of the plane defined by the
points a, b, and c.
|
static double |
leftOfPlaneFast(float[] pa,
float[] pb,
float[] pc,
float[] pd)
Determines if a point d is left of the plane defined by the
points a, b, and c.
|
public static double leftOfLine(double xa, double ya, double xb, double yb, double xc, double yc)
public static double leftOfLine(double[] pa, double[] pb, double[] pc)
public static double leftOfLine(float[] pa, float[] pb, float[] pc)
public static double leftOfLineFast(double xa, double ya, double xb, double yb, double xc, double yc)
Note: this fast method may return an incorrect result.
public static double leftOfLineFast(double[] pa, double[] pb, double[] pc)
Note: this fast method may return an incorrect result.
public static double leftOfLineFast(float[] pa, float[] pb, float[] pc)
Note: this fast method may return an incorrect result.
public static double leftOfPlane(double xa, double ya, double za, double xb, double yb, double zb, double xc, double yc, double zc, double xd, double yd, double zd)
public static double leftOfPlane(double[] pa, double[] pb, double[] pc, double[] pd)
public static double leftOfPlane(float[] pa, float[] pb, float[] pc, float[] pd)
public static double leftOfPlaneFast(double xa, double ya, double za, double xb, double yb, double zb, double xc, double yc, double zc, double xd, double yd, double zd)
Note: this fast method may return an incorrect result.
public static double leftOfPlaneFast(double[] pa, double[] pb, double[] pc, double[] pd)
Note: this fast method may return an incorrect result.
public static double leftOfPlaneFast(float[] pa, float[] pb, float[] pc, float[] pd)
Note: this fast method may return an incorrect result.
public static double inCircle(double xa, double ya, double xb, double yb, double xc, double yc, double xd, double yd)
leftOfLine(double, double, double, double, double, double)
would return a positive number.public static double inCircle(double[] pa, double[] pb, double[] pc, double[] pd)
leftOfLine(double, double, double, double, double, double)
would return a positive number.public static double inCircle(float[] pa, float[] pb, float[] pc, float[] pd)
leftOfLine(double, double, double, double, double, double)
would return a positive number.public static double inCircleFast(double xa, double ya, double xb, double yb, double xc, double yc, double xd, double yd)
leftOfLine(double, double, double, double, double, double)
would return a positive number.
Note: this fast method may return an incorrect result.
public static double inCircleFast(double[] pa, double[] pb, double[] pc, double[] pd)
leftOfLine(double, double, double, double, double, double)
would return a positive number.
Note: this fast method may return an incorrect result.
public static double inCircleFast(float[] pa, float[] pb, float[] pc, float[] pd)
leftOfLine(double, double, double, double, double, double)
would return a positive number.
Note: this fast method may return an incorrect result.
public static double inSphere(double xa, double ya, double za, double xb, double yb, double zb, double xc, double yc, double zc, double xd, double yd, double zd, double xe, double ye, double ze)
leftOfPlane(double, double, double, double, double, double, double, double, double, double, double, double)
would return a positive number.public static double inSphere(double[] pa, double[] pb, double[] pc, double[] pd, double[] pe)
leftOfPlane(double, double, double, double, double, double, double, double, double, double, double, double)
would return a positive number.public static double inSphere(float[] pa, float[] pb, float[] pc, float[] pd, float[] pe)
leftOfPlane(double, double, double, double, double, double, double, double, double, double, double, double)
would return a positive number.public static double inSphereFast(double xa, double ya, double za, double xb, double yb, double zb, double xc, double yc, double zc, double xd, double yd, double zd, double xe, double ye, double ze)
leftOfPlane(double, double, double, double, double, double, double, double, double, double, double, double)
would return a positive number.
Note: this fast method may return an incorrect result.
public static double inSphereFast(double[] pa, double[] pb, double[] pc, double[] pd, double[] pe)
leftOfPlane(double, double, double, double, double, double, double, double, double, double, double, double)
would return a positive number.
Note: this fast method may return an incorrect result.
public static double inSphereFast(float[] pa, float[] pb, float[] pc, float[] pd, float[] pe)
leftOfPlane(double, double, double, double, double, double, double, double, double, double, double, double)
would return a positive number.
Note: this fast method may return an incorrect result.
public static double inOrthoSphere(double xa, double ya, double za, double wa, double xb, double yb, double zb, double wb, double xc, double yc, double zc, double wc, double xd, double yd, double zd, double wd, double xe, double ye, double ze, double we)
leftOfPlane(double, double, double, double, double, double, double, double, double, double, double, double)
would return a positive number.
The weights wa, wb, wc, wd equal the squared radii of spheres associated with the corresponding points a, b, c, and d. The ortho-sphere is orthogonal to each of these four spheres.
If all four weights (and radii) equal zero, then the ortho-sphere
is the circumsphere. In this case, the method inSphere(double, double, double, double, double, double, double, double, double, double, double, double, double, double, double)
is more efficient.
public static double inOrthoSphere(double[] pa, double[] pb, double[] pc, double[] pd, double[] pe)
leftOfPlane(double, double, double, double, double, double, double, double, double, double, double, double)
would return a positive number.public static double inOrthoSphere(float[] pa, float[] pb, float[] pc, float[] pd, float[] pe)
leftOfPlane(double, double, double, double, double, double, double, double, double, double, double, double)
would return a positive number.public static double inOrthoSphereFast(double xa, double ya, double za, double wa, double xb, double yb, double zb, double wb, double xc, double yc, double zc, double wc, double xd, double yd, double zd, double wd, double xe, double ye, double ze, double we)
leftOfPlane(double, double, double, double, double, double, double, double, double, double, double, double)
would return a positive number.
Note: this fast method may return an incorrect result.
public static double inOrthoSphereFast(double[] pa, double[] pb, double[] pc, double[] pd, double[] pe)
leftOfPlane(double, double, double, double, double, double, double, double, double, double, double, double)
would return a positive number.
Note: this fast method may return an incorrect result.
public static double inOrthoSphereFast(float[] pa, float[] pb, float[] pc, float[] pd, float[] pe)
leftOfPlane(double, double, double, double, double, double, double, double, double, double, double, double)
would return a positive number.
Note: this fast method may return an incorrect result.
public static void centerCircle(float xa, float ya, float xb, float yb, float xc, float yc, float[] po)
leftOfLine(double, double, double, double, double, double)
would return a positive number.po
- array containing (x,y) coordinates of center.public static void centerCircle(float[] pa, float[] pb, float[] pc, float[] po)
leftOfLine(double, double, double, double, double, double)
would return a positive number.po
- array containing (x,y) coordinates of center.public static void centerCircle(double xa, double ya, double xb, double yb, double xc, double yc, double[] po)
leftOfLine(double, double, double, double, double, double)
would return a positive number.po
- array containing (x,y) coordinates of center.public static void centerCircle(double[] pa, double[] pb, double[] pc, double[] po)
leftOfLine(double, double, double, double, double, double)
would return a positive number.po
- array containing (x,y) coordinates of center.public static void centerSphere(float xa, float ya, float za, float xb, float yb, float zb, float xc, float yc, float zc, float xd, float yd, float zd, float[] po)
leftOfPlane(double, double, double, double, double, double, double, double, double, double, double, double)
would return a positive number.po
- array containing (x,y,z) coordinates of center.public static void centerSphere(float[] pa, float[] pb, float[] pc, float[] pd, float[] po)
leftOfPlane(double, double, double, double, double, double, double, double, double, double, double, double)
would return a positive number.po
- array containing (x,y,z) coordinates of center.public static void centerSphere(double xa, double ya, double za, double xb, double yb, double zb, double xc, double yc, double zc, double xd, double yd, double zd, double[] po)
leftOfPlane(double, double, double, double, double, double, double, double, double, double, double, double)
would return a positive number.po
- array containing (x,y,z) coordinates of center.public static void centerSphere(double[] pa, double[] pb, double[] pc, double[] pd, double[] po)
leftOfPlane(double, double, double, double, double, double, double, double, double, double, double, double)
would return a positive number.po
- array containing (x,y,z) coordinates of center.public static void centerCircle3D(double xa, double ya, double za, double xb, double yb, double zb, double xc, double yc, double zc, double[] po)
po
- array containing (x,y,z) coordinates of center.