JTS Topology Suite version 1.12

com.vividsolutions.jts.triangulate.quadedge
Class TrianglePredicate

java.lang.Object
  extended by com.vividsolutions.jts.triangulate.quadedge.TrianglePredicate

public class TrianglePredicate
extends java.lang.Object

Algorithms for computing values and predicates associated with triangles. For some algorithms extended-precision implementations are provided, which are more robust (i.e. they produce correct answers in more cases). Also, some more robust formulations of some algorithms are provided, which utilize normalization to the origin.

Author:
Martin Davis

Constructor Summary
TrianglePredicate()
           
 
Method Summary
static boolean isInCircleCC(Coordinate a, Coordinate b, Coordinate c, Coordinate p)
          Computes the inCircle test using distance from the circumcentre.
static boolean isInCircleDDFast(Coordinate a, Coordinate b, Coordinate c, Coordinate p)
           
static boolean isInCircleDDNormalized(Coordinate a, Coordinate b, Coordinate c, Coordinate p)
           
static boolean isInCircleDDSlow(Coordinate a, Coordinate b, Coordinate c, Coordinate p)
          Tests if a point is inside the circle defined by the triangle with vertices a, b, c (oriented counter-clockwise).
static boolean isInCircleNonRobust(Coordinate a, Coordinate b, Coordinate c, Coordinate p)
          Tests if a point is inside the circle defined by the triangle with vertices a, b, c (oriented counter-clockwise).
static boolean isInCircleNormalized(Coordinate a, Coordinate b, Coordinate c, Coordinate p)
          Tests if a point is inside the circle defined by the triangle with vertices a, b, c (oriented counter-clockwise).
static boolean isInCircleRobust(Coordinate a, Coordinate b, Coordinate c, Coordinate p)
          Tests if a point is inside the circle defined by the triangle with vertices a, b, c (oriented counter-clockwise).
static DD triAreaDDFast(Coordinate a, Coordinate b, Coordinate c)
           
static DD triAreaDDSlow(DD ax, DD ay, DD bx, DD by, DD cx, DD cy)
          Computes twice the area of the oriented triangle (a, b, c), i.e., the area is positive if the triangle is oriented counterclockwise.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

TrianglePredicate

public TrianglePredicate()
Method Detail

isInCircleNonRobust

public static boolean isInCircleNonRobust(Coordinate a,
                                          Coordinate b,
                                          Coordinate c,
                                          Coordinate p)
Tests if a point is inside the circle defined by the triangle with vertices a, b, c (oriented counter-clockwise). This test uses simple double-precision arithmetic, and thus may not be robust.

Parameters:
a - a vertex of the triangle
b - a vertex of the triangle
c - a vertex of the triangle
P - the point to test
Returns:
true if this point is inside the circle defined by the points a, b, c

isInCircleNormalized

public static boolean isInCircleNormalized(Coordinate a,
                                           Coordinate b,
                                           Coordinate c,
                                           Coordinate p)
Tests if a point is inside the circle defined by the triangle with vertices a, b, c (oriented counter-clockwise). This test uses simple double-precision arithmetic, and thus is not 10% robust. However, by using normalization to the origin it provides improved robustness and increased performance.

Based on code by J.R.Shewchuk.

Parameters:
a - a vertex of the triangle
b - a vertex of the triangle
c - a vertex of the triangle
P - the point to test
Returns:
true if this point is inside the circle defined by the points a, b, c

isInCircleRobust

public static boolean isInCircleRobust(Coordinate a,
                                       Coordinate b,
                                       Coordinate c,
                                       Coordinate p)
Tests if a point is inside the circle defined by the triangle with vertices a, b, c (oriented counter-clockwise). This method uses more robust computation.

Parameters:
a - a vertex of the triangle
b - a vertex of the triangle
c - a vertex of the triangle
P - the point to test
Returns:
true if this point is inside the circle defined by the points a, b, c

isInCircleDDSlow

public static boolean isInCircleDDSlow(Coordinate a,
                                       Coordinate b,
                                       Coordinate c,
                                       Coordinate p)
Tests if a point is inside the circle defined by the triangle with vertices a, b, c (oriented counter-clockwise). The computation uses DD arithmetic for robustness.

Parameters:
a - a vertex of the triangle
b - a vertex of the triangle
c - a vertex of the triangle
P - the point to test
Returns:
true if this point is inside the circle defined by the points a, b, c

triAreaDDSlow

public static DD triAreaDDSlow(DD ax,
                               DD ay,
                               DD bx,
                               DD by,
                               DD cx,
                               DD cy)
Computes twice the area of the oriented triangle (a, b, c), i.e., the area is positive if the triangle is oriented counterclockwise. The computation uses DD arithmetic for robustness.

Parameters:
ax - the x ordinate of a vertex of the triangle
ay - the y ordinate of a vertex of the triangle
bx - the x ordinate of a vertex of the triangle
by - the y ordinate of a vertex of the triangle
cx - the x ordinate of a vertex of the triangle
cy - the y ordinate of a vertex of the triangle

isInCircleDDFast

public static boolean isInCircleDDFast(Coordinate a,
                                       Coordinate b,
                                       Coordinate c,
                                       Coordinate p)

triAreaDDFast

public static DD triAreaDDFast(Coordinate a,
                               Coordinate b,
                               Coordinate c)

isInCircleDDNormalized

public static boolean isInCircleDDNormalized(Coordinate a,
                                             Coordinate b,
                                             Coordinate c,
                                             Coordinate p)

isInCircleCC

public static boolean isInCircleCC(Coordinate a,
                                   Coordinate b,
                                   Coordinate c,
                                   Coordinate p)
Computes the inCircle test using distance from the circumcentre. Uses standard double-precision arithmetic.

In general this doesn't appear to be any more robust than the standard calculation. However, there is at least one case where the test point is far enough from the circumcircle that this test gives the correct answer.

 LINESTRING
 (1507029.9878 518325.7547, 1507022.1120341457 518332.8225183258,
 1507029.9833 518325.7458, 1507029.9896965567 518325.744909031)
 

Parameters:
a - a vertex of the triangle
b - a vertex of the triangle
c - a vertex of the triangle
p - the point to test
Returns:
true if this point is inside the circle defined by the points a, b, c

JTS Topology Suite version 1.12