| com.vividsolutions.jts.algorithm |
Contains classes and interfaces implementing fundamental computational geometry algorithms.
Robustness
Geometrical algorithms involve a combination of combinatorial and numerical computation. As with
all numerical computation using finite-precision numbers, the algorithms chosen are susceptible to
problems of robustness. A robustness problem occurs when a numerical calculation produces an
incorrect answer for some inputs due to round-off errors. Robustness problems are especially
serious in geometric computation, since they can result in errors during topology building.
There are many approaches to dealing with the problem of robustness in geometrical computation.
Not surprisingly, most robust algorithms are substantially more complex and less performant than
the non-robust versions. Fortunately, JTS is sensitive to robustness problems in only a few key
functions (such as line intersection and the point-in-polygon test). There are efficient robust
algorithms available for these functions, and these algorithms are implemented in JTS.
Computational Performance
Runtime performance is an important consideration for a production-quality implementation of
geometric algorithms. The most computationally intensive algorithm used in JTS is intersection
detection. JTS methods need to determine both all intersection between the line segments in a
single Geometry (self-intersection) and all intersections between the line segments of two different
Geometries.
The obvious naive algorithm for intersection detection (comparing every segment with every other)
has unacceptably slow performance. There is a large literature of faster algorithms for intersection
detection. Unfortunately, many of them involve substantial code complexity. JTS tries to balance code
simplicity with performance gains. It uses some simple techniques to produce substantial performance
gains for common types of input data.
Package Specification
|
| Java Source File Name | Type | Comment |
| Angle.java | Class | Utility functions for working with angles. |
| BoundaryNodeRule.java | Interface | An interface for rules which determine whether node points
which are in boundaries of lineal geometry components
are in the boundary of the parent geometry collection. |
| CentralEndpointIntersector.java | Class | Computes an approximate intersection of two line segments
by taking the most central of the endpoints of the segments. |
| CentroidArea.java | Class | Computes the centroid of an area geometry. |
| CentroidLine.java | Class | Computes the centroid of a linear geometry. |
| CentroidPoint.java | Class | Computes the centroid of a point geometry. |
| CGAlgorithms.java | Class | Specifies and implements various fundamental Computational Geometric algorithms. |
| ConvexHull.java | Class | Computes the convex hull of a
Geometry . |
| HCoordinate.java | Class | Represents a homogeneous coordinate in a 2-D coordinate space. |
| InteriorPointArea.java | Class | Computes a point in the interior of an area geometry. |
| InteriorPointLine.java | Class | Computes a point in the interior of an linear geometry. |
| InteriorPointPoint.java | Class | Computes a point in the interior of an point geometry. |
| LineIntersector.java | Class | A LineIntersector is an algorithm that can both test whether
two line segments intersect and compute the intersection point
if they do.
The intersection point may be computed in a precise or non-precise manner.
Computing it precisely involves rounding it to an integer. |
| MCPointInRing.java | Class | Implements
PointInRing using
MonotoneChain s and a
BinTree index to
increase performance. |
| MinimumDiameter.java | Class | Computes the minimum diameter of a
Geometry . |
| NonRobustCGAlgorithms.java | Class | Non-robust versions of various fundamental Computational Geometric algorithms,
FOR TESTING PURPOSES ONLY!. |
| NonRobustLineIntersector.java | Class | A non-robust version of
. |
| NotRepresentableException.java | Class | Indicates that a
HCoordinate has been computed which is
not representable on the Cartesian plane. |
| PointInRing.java | Interface | An interface for classes which test whether a
Coordinate lies inside
a ring. |
| PointLocator.java | Class | Computes the topological relationship (
Location )
of a single point to a
Geometry . |
| RobustCGAlgorithms.java | Class | Stub version of RobustCGAlgorithms for backwards compatibility. |
| RobustDeterminant.java | Class | Implements an algorithm to compute the
sign of a 2x2 determinant for double precision values robustly. |
| RobustLineIntersector.java | Class | A robust version of
. |
| SimplePointInAreaLocator.java | Class | Computes whether a point
lies in the interior of an area
Geometry . |
| SimplePointInRing.java | Class | Tests whether a
Coordinate lies inside
a ring, using a linear-time algorithm. |
| SIRtreePointInRing.java | Class | Implements
PointInRing using a
SIRtree index to
increase performance. |