Module math
Package de.grogra.math.util

Class Geometry

java.lang.Object
de.grogra.math.util.Geometry
public final class Geometry extends Object
Robust geometric predicates.

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

Version:
2001.04.03, 2006.08.02
Author:
Dave Hale, Colorado School of Mines

  • Constructor Summary

    Constructors
    Constructor
    Description
    Geometry()
     

  • Method Summary

    Modifier and Type
    Method
    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.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • Geometry

      public Geometry()

  • Method Details

    • centerCircle

      public 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. The latter are assumed to be in CCW order, such that the method leftOfLine(double, double, double, double, double, double) would return a positive number.
      Parameters:
      po - array containing (x,y) coordinates of center.

    • centerCircle

      public 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. The latter are assumed to be in CCW order, such that the method leftOfLine(double, double, double, double, double, double) would return a positive number.
      Parameters:
      po - array containing (x,y) coordinates of center.

    • centerCircle

      public 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. The latter are assumed to be in CCW order, such that the method leftOfLine(double, double, double, double, double, double) would return a positive number.
      Parameters:
      po - array containing (x,y) coordinates of center.

    • centerCircle

      public 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. The latter are assumed to be in CCW order, such that the method leftOfLine(double, double, double, double, double, double) would return a positive number.
      Parameters:
      po - array containing (x,y) coordinates of center.

    • centerCircle3D

      public 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. Because the points have 3-D coordinates, they may specified in any order.
      Parameters:
      po - array containing (x,y,z) coordinates of center.

    • centerSphere

      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)
      Computes the center of the sphere defined by the points a, b, c, and d. The latter are assumed to be in CCW order, such that the method leftOfPlane(double, double, double, double, double, double, double, double, double, double, double, double) would return a positive number.
      Parameters:
      po - array containing (x,y,z) coordinates of center.

    • centerSphere

      public 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. The latter are assumed to be in CCW order, such that the method leftOfPlane(double, double, double, double, double, double, double, double, double, double, double, double) would return a positive number.
      Parameters:
      po - array containing (x,y,z) coordinates of center.

    • centerSphere

      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)
      Computes the center of the sphere defined by the points a, b, c, and d. The latter are assumed to be in CCW order, such that the method leftOfPlane(double, double, double, double, double, double, double, double, double, double, double, double) would return a positive number.
      Parameters:
      po - array containing (x,y,z) coordinates of center.

    • centerSphere

      public 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. The latter are assumed to be in CCW order, such that the method leftOfPlane(double, double, double, double, double, double, double, double, double, double, double, double) would return a positive number.
      Parameters:
      po - array containing (x,y,z) coordinates of center.

    • inCircle

      public 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. The latter are assumed to be in CCW order, such that the method leftOfLine(double, double, double, double, double, double) would return a positive number.
      Returns:
      positive, if inside the circle; negative, if outside the circle; zero, otherwise.

    • inCircle

      public 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. The latter are assumed to be in CCW order, such that the method leftOfLine(double, double, double, double, double, double) would return a positive number.
      Returns:
      positive, if inside the circle; negative, if outside the circle; zero, otherwise.

    • inCircle

      public 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. The latter are assumed to be in CCW order, such that the method leftOfLine(double, double, double, double, double, double) would return a positive number.
      Returns:
      positive, if inside the circle; negative, if outside the circle; zero, otherwise.

    • inCircleFast

      public 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. The latter are assumed to be in CCW order, such that the method leftOfLine(double, double, double, double, double, double) would return a positive number.

      Note: this fast method may return an incorrect result.

      Returns:
      positive, if inside the circle; negative, if outside the circle; zero, otherwise.

    • inCircleFast

      public 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. The latter are assumed to be in CCW order, such that the method leftOfLine(double, double, double, double, double, double) would return a positive number.

      Note: this fast method may return an incorrect result.

      Returns:
      positive, if inside the circle; negative, if outside the circle; zero, otherwise.

    • inCircleFast

      public 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. The latter are assumed to be in CCW order, such that the method leftOfLine(double, double, double, double, double, double) would return a positive number.

      Note: this fast method may return an incorrect result.

      Returns:
      positive, if inside the circle; negative, if outside the circle; zero, otherwise.

    • inOrthoSphere

      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)
      Determines whether or not a weighted point e is inside the ortho-sphere defined by the weighted points a, b, c, and d. The latter are assumed to be in CCW order, such that the method 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.

    • inOrthoSphere

      public 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. The latter are assumed to be in CCW order, such that the method leftOfPlane(double, double, double, double, double, double, double, double, double, double, double, double) would return a positive number.

    • inOrthoSphere

      public 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. The latter are assumed to be in CCW order, such that the method leftOfPlane(double, double, double, double, double, double, double, double, double, double, double, double) would return a positive number.

    • inOrthoSphereFast

      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)
      Determines whether or not a weighted point e is inside the ortho-sphere defined by the weighted points a, b, c, and d. The latter are assumed to be in CCW order, such that the method 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.

    • inOrthoSphereFast

      public 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. The latter are assumed to be in CCW order, such that the method 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.

    • inOrthoSphereFast

      public 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. The latter are assumed to be in CCW order, such that the method 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.

    • inSphere

      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)
      Determines if a point e is inside the sphere defined by the points a, b, c, and d. The latter are assumed to be in CCW order, such that the method leftOfPlane(double, double, double, double, double, double, double, double, double, double, double, double) would return a positive number.
      Returns:
      positive, if inside the sphere; negative, if outside the sphere; zero, otherwise.

    • inSphere

      public 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. The latter are assumed to be in CCW order, such that the method leftOfPlane(double, double, double, double, double, double, double, double, double, double, double, double) would return a positive number.
      Returns:
      positive, if inside the sphere; negative, if outside the sphere; zero, otherwise.

    • inSphere

      public 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. The latter are assumed to be in CCW order, such that the method leftOfPlane(double, double, double, double, double, double, double, double, double, double, double, double) would return a positive number.
      Returns:
      positive, if inside the sphere; negative, if outside the sphere; zero, otherwise.

    • inSphereFast

      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)
      Determines if a point e is inside the sphere defined by the points a, b, c, and d. The latter are assumed to be in CCW order, such that the method 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.

      Returns:
      positive, if inside the sphere; negative, if outside the sphere; zero, otherwise.

    • inSphereFast

      public 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. The latter are assumed to be in CCW order, such that the method 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.

      Returns:
      positive, if inside the sphere; negative, if outside the sphere; zero, otherwise.

    • inSphereFast

      public 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. The latter are assumed to be in CCW order, such that the method 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.

      Returns:
      positive, if inside the sphere; negative, if outside the sphere; zero, otherwise.

    • leftOfLine

      public 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. This is equivalent to determining whether the points a, b, and c are in counter-clockwise (CCW) order.
      Returns:
      positive, if left of line; negative, if right of line; zero, otherwise.

    • leftOfLine

      public 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. This is equivalent to determining whether the points a, b, and c are in counter-clockwise (CCW) order.
      Returns:
      positive, if left of line; negative, if right of line; zero, otherwise.

    • leftOfLine

      public 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. This is equivalent to determining whether the points a, b, and c are in counter-clockwise (CCW) order.
      Returns:
      positive, if left of line; negative, if right of line; zero, otherwise.

    • leftOfLineFast

      public 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. This is equivalent to determining whether the points a, b, and c are in counter-clockwise (CCW) order.

      Note: this fast method may return an incorrect result.

      Returns:
      positive, if left of line; negative, if right of line; zero, otherwise.

    • leftOfLineFast

      public 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. This is equivalent to determining whether the points a, b, and c are in counter-clockwise (CCW) order.

      Note: this fast method may return an incorrect result.

      Returns:
      positive, if left of line; negative, if right of line; zero, otherwise.

    • leftOfLineFast

      public 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. This is equivalent to determining whether the points a, b, and c are in counter-clockwise (CCW) order.

      Note: this fast method may return an incorrect result.

      Returns:
      positive, if left of line; negative, if right of line; zero, otherwise.

    • leftOfPlane

      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)
      Determines if a point d is left of the plane defined by the points a, b, and c. The latter are assumed to be in CCW order, as viewed from the right side of the plane.
      Returns:
      positive, if left of plane; negative, if right of plane; zero, otherwise.

    • leftOfPlane

      public 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. The latter are assumed to be in CCW order, as viewed from the right side of the plane.
      Returns:
      positive, if left of plane; negative, if right of plane; zero, otherwise.

    • leftOfPlane

      public 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. The latter are assumed to be in CCW order, as viewed from the right side of the plane.
      Returns:
      positive, if left of plane; negative, if right of plane; zero, otherwise.

    • leftOfPlaneFast

      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)
      Determines if a point d is left of the plane defined by the points a, b, and c. The latter are assumed to be in CCW order, as viewed from the right side of the plane.

      Note: this fast method may return an incorrect result.

      Returns:
      positive, if left of plane; negative, if right of plane; zero, otherwise.

    • leftOfPlaneFast

      public 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. The latter are assumed to be in CCW order, as viewed from the right side of the plane.

      Note: this fast method may return an incorrect result.

      Returns:
      positive, if left of plane; negative, if right of plane; zero, otherwise.

    • leftOfPlaneFast

      public 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. The latter are assumed to be in CCW order, as viewed from the right side of the plane.

      Note: this fast method may return an incorrect result.

      Returns:
      positive, if left of plane; negative, if right of plane; zero, otherwise.