Package org.tinfour.common

Class GeometricOperations

java.lang.Object

org.tinfour.common.GeometricOperations

public class GeometricOperations
extends Object

Provides elements and methods to support geometric operations using "double double" precision where necessary. The double-double precision calculations use extended precision arithmetic to provide 108 bits of mantissa or about 30 decimal digits of precision.

Constructor Summary

Constructors

Constructor	Description
GeometricOperations()	Construct an instance based on a nominal point spacing of 1 unit.
GeometricOperations(Thresholds thresholds)	Construct an instance based on the specified threshold values.

Method Summary

Modifier and Type	Method	Description
double	area(double ax, double ay, double bx, double by, double cx, double cy)	Determines the signed area of triangle ABC.
double	area(Vertex a, Vertex b, Vertex c)	Determines the signed area of triangle ABC.
void	circumcircle(double vax, double vay, double vbx, double vby, double vcx, double vcy, Circumcircle result)	Computes the circumcircle for the coordinates of three vertices.
boolean	circumcircle(Vertex a, Vertex b, Vertex c, Circumcircle result)	Computes the circumcircle for the coordinates of three vertices.
void	clearDiagnostics()	Clear the diagnostic operation counts maintained by this class.
double	direction(double ax, double ay, double bx, double by, double cx, double cy)	Uses extended arithmetic to find the direction of a point with coordinates (cx, cy) compared to a directed edge from vertex A to B.
long	getCircumcircleCount()	Get a diagnostic count of the number of circumcircle calculations
long	getExtendedCircumcircleCount()	Get a diagnostic count of the number of circumcircle calculations that required extended precision arithmetic
long	getExtendedConflictCount()	Get a diagnostic count of the number of incidents where an extended precision calculation was in conflict with the ordinary precision calculation.
long	getExtendedPrecisionInCircleCount()	Get a diagnostic count of the number of incidents where an extended precision calculation was required for an in-circle calculation due to the small-magnitude value of the computed value.
long	getHalfPlaneCount()	Get a diagnostic count of the number of half-plane calculations
long	getInCircleCount()	Get a diagnostic count of the number of times an in-circle calculation was performed.
Thresholds	getThresholds()	Gets the threshold values associated with this instance.
double	halfPlane(double ax, double ay, double bx, double by, double cx, double cy)	Uses extended arithmetic to find the side on which a point lies with respect to a directed edge.
double	inCircle(double ax, double ay, double bx, double by, double cx, double cy, double dx, double dy)	Determines if vertex d lies within the circumcircle of triangle a,b,c, using extended-precision arithmetic when required by small magnitude results.
double	inCircle(Vertex a, Vertex b, Vertex c, Vertex d)	Determines if vertex d lies within the circumcircle of triangle a,b,c, using extended-precision arithmetic when required by small magnitude results.
double	inCircleQuadPrecision(double ax, double ay, double bx, double by, double cx, double cy, double dx, double dy)	Uses quad-precision methods to determines if vertex d lies within the circumcircle of triangle a,b,c.
double	orientation(double ax, double ay, double bx, double by, double cx, double cy)	Use extended arithmetic to compute the signed orientation of the triangle defined by three points

Methods inherited from class java.lang.Object

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

Constructor Detail

GeometricOperations

public GeometricOperations()

Construct an instance based on a nominal point spacing of 1 unit.

GeometricOperations

public GeometricOperations(Thresholds thresholds)

Construct an instance based on the specified threshold values.

Parameters:

thresholds - a valid instance

Method Detail

inCircle

public double inCircle(Vertex a,
                       Vertex b,
                       Vertex c,
                       Vertex d)

Determines if vertex d lies within the circumcircle of triangle a,b,c, using extended-precision arithmetic when required by small magnitude results.

Parameters:

a - a valid vertex

b - a valid vertex

c - a valid vertex

d - a valid vertex

Returns:

positive if d is inside the circumcircle; negative if it is outside; zero if it is on the edge.

inCircle

public double inCircle(double ax,
                       double ay,
                       double bx,
                       double by,
                       double cx,
                       double cy,
                       double dx,
                       double dy)

Determines if vertex d lies within the circumcircle of triangle a,b,c, using extended-precision arithmetic when required by small magnitude results.

Parameters:

ax - the x coordinate of vertex a

ay - the y coordinate of vertex a

bx - the x coordinate of vertex b

by - the y coordinate of vertex b

cx - the x coordinate of vertex c

cy - the y coordinate of vertex c

dx - the x coordinate of vertex d

dy - the y coordinate of vertex d

Returns:

positive if d is inside the circumcircle; negative if it is outside; zero if it is on the edge.

inCircleQuadPrecision

public double inCircleQuadPrecision(double ax,
                                    double ay,
                                    double bx,
                                    double by,
                                    double cx,
                                    double cy,
                                    double dx,
                                    double dy)

Uses quad-precision methods to determines if vertex d lies within the circumcircle of triangle a,b,c. Similar to inCircle() but requires more processing and delivers higher accuracy.

Parameters:

ax - the x coordinate of vertex a

ay - the y coordinate of vertex a

bx - the x coordinate of vertex b

by - the y coordinate of vertex b

cx - the x coordinate of vertex c

cy - the y coordinate of vertex c

dx - the x coordinate of vertex d

dy - the y coordinate of vertex d

Returns:

positive if d is inside the circumcircle; negative if it is outside; zero if it is on the edge.

halfPlane

public double halfPlane(double ax,
                        double ay,
                        double bx,
                        double by,
                        double cx,
                        double cy)

Uses extended arithmetic to find the side on which a point lies with respect to a directed edge.

Parameters:

ax - the x coordinate of the first vertex in the segment

ay - the y coordinate of the first vertex in the segment

bx - the x coordinate of the second vertex in the segment

by - the y coordinate of the second vertex in the segment

cx - the x coordinate of the point of interest

cy - the y coordinate of the point of interest

Returns:

positive if the point is to the left of the edge, negative if it is to the right, or zero if it lies on the ray coincident with the edge.

direction

public double direction(double ax,
                        double ay,
                        double bx,
                        double by,
                        double cx,
                        double cy)

Uses extended arithmetic to find the direction of a point with coordinates (cx, cy) compared to a directed edge from vertex A to B. This value is given by the dot product (cx-ax, cy-ay) dot (bx-ax, by-ay).

Parameters:

ax - the x coordinate of the initial point on the edge

ay - the y coordinate of the initial point on the edge

bx - the x coordinate of the second point on the edge

by - the y coordinate of the second point on the edge

cx - the coordinate of interest

cy - the coordinate of interest

Returns:

a valid, signed floating point number, potentially zero.

orientation

public double orientation(double ax,
                          double ay,
                          double bx,
                          double by,
                          double cx,
                          double cy)

Use extended arithmetic to compute the signed orientation of the triangle defined by three points

Parameters:

ax - x coordinate of the first point

ay - y coordinate of the first point

bx - x coordinate of the second point

by - y coordinate of the second point

cx - x coordinate of the third point

cy - y coordinate of the third point

Returns:

if the triangle has a counterclockwise order, a positive value; if the triangle is degenerate, a zero value; if the triangle has a clockwise order, a negative value.

getInCircleCount

public long getInCircleCount()

Get a diagnostic count of the number of times an in-circle calculation was performed.

Returns:

a positive integer value

getExtendedPrecisionInCircleCount

public long getExtendedPrecisionInCircleCount()

Get a diagnostic count of the number of incidents where an extended precision calculation was required for an in-circle calculation due to the small-magnitude value of the computed value.

Returns:

a positive integer value

getExtendedConflictCount

public long getExtendedConflictCount()

Get a diagnostic count of the number of incidents where an extended precision calculation was in conflict with the ordinary precision calculation.

Returns:

a positive integer value

getHalfPlaneCount

public long getHalfPlaneCount()

Get a diagnostic count of the number of half-plane calculations

Returns:

a positive integer value

getCircumcircleCount

public long getCircumcircleCount()

Get a diagnostic count of the number of circumcircle calculations

Returns:

a positive integer value

getExtendedCircumcircleCount

public long getExtendedCircumcircleCount()

Get a diagnostic count of the number of circumcircle calculations that required extended precision arithmetic

Returns:

a positive integer value

area

public double area(Vertex a,
                   Vertex b,
                   Vertex c)

Determines the signed area of triangle ABC. If necessary, uses extended arithmetic to compute the area of a nearly degenerate triangle.

Parameters:

a - the initial vertex

b - the second vertex

c - the third vertex

Returns:

a positive value if the triangle is oriented counterclockwise, negative if it is oriented clockwise, or zero if it is degenerate.

area

public double area(double ax,
                   double ay,
                   double bx,
                   double by,
                   double cx,
                   double cy)

Determines the signed area of triangle ABC. If necessary, uses extended arithmetic to compute the area of a nearly degenerate triangle.

Parameters:

ax - the x coordinate of the first vertex in the triangle

ay - the y coordinate of the first vertex in the triangle

bx - the x coordinate of the second vertex in the triangle

by - the y coordinate of the second vertex in the triangle

cx - the x coordinate of the third vertex in the triangle

cy - the y coordinate of the point vertex in the triangle

Returns:

a positive value if the triangle is oriented counterclockwise, negative if it is oriented clockwise, or zero if it is degenerate.

clearDiagnostics

public void clearDiagnostics()

Clear the diagnostic operation counts maintained by this class.

circumcircle

public boolean circumcircle(Vertex a,
                            Vertex b,
                            Vertex c,
                            Circumcircle result)

Computes the circumcircle for the coordinates of three vertices. For efficiency purposes, results are stored in a reusable container instance.

Parameters:

a - Vertex A

b - Vertex B

c - Vertex C

result - a valid instance to store the result.

Returns:

true if the circumcircle was computed successfully with a finite radius; otherwise, false.

circumcircle

public void circumcircle(double vax,
                         double vay,
                         double vbx,
                         double vby,
                         double vcx,
                         double vcy,
                         Circumcircle result)

Computes the circumcircle for the coordinates of three vertices. For efficiency purposes, results are stored in a reusable container instance.

Parameters:

vax - The x coordinate of vertex A

vay - The y coordinate of vertex A

vbx - The x coordinate of vertex B

vby - The y coordinate of vertex B

vcx - The x coordinate of vertex C

vcy - The y coordinate of vertex C

result - a valid instance to store the result.

getThresholds

public Thresholds getThresholds()

Gets the threshold values associated with this instance.

Returns:

a valid instance of Thresholds.