Class TrianglePredicate
- java.lang.Object
-
- org.locationtech.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
Constructors Constructor Description TrianglePredicate()
-
Method Summary
All Methods Static Methods Concrete Methods Modifier and Type Method Description 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.
-
-
-
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 triangleb
- a vertex of the trianglec
- a vertex of the trianglep
- 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 100% 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 triangleb
- a vertex of the trianglec
- a vertex of the trianglep
- 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 triangleb
- a vertex of the trianglec
- a vertex of the trianglep
- 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 usesDD
arithmetic for robustness.- Parameters:
a
- a vertex of the triangleb
- a vertex of the trianglec
- a vertex of the trianglep
- 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 usesDD
arithmetic for robustness.- Parameters:
ax
- the x ordinate of a vertex of the triangleay
- the y ordinate of a vertex of the trianglebx
- the x ordinate of a vertex of the triangleby
- the y ordinate of a vertex of the trianglecx
- the x ordinate of a vertex of the trianglecy
- 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 triangleb
- a vertex of the trianglec
- a vertex of the trianglep
- the point to test- Returns:
- true if this point is inside the circle defined by the points a, b, c
-
-