GEOS
3.9.0dev

Contains classes and interfaces implementing fundamental computational geometry algorithms. More...
Namespaces  
distance  
Classes to compute distance metrics between geometries.  
locate  
Classes which determine the Location of points in geometries.  
Classes  
class  Angle 
Utility functions for working with angles. More...  
class  BoundaryNodeRule 
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. More...  
class  CentralEndpointIntersector 
Computes an approximate intersection of two line segments by taking the most central of the endpoints of the segments. More...  
class  Centroid 
Computes the centroid of a Geometry of any dimension. More...  
class  CGAlgorithmsDD 
Implements basic computational geometry algorithms using extended precision floatpoint arithmetic. More...  
class  ConvexHull 
Computes the convex hull of a Geometry. More...  
class  Distance 
Functions to compute distance between basic geometric structures. More...  
class  HCoordinate 
Represents a homogeneous coordinate in a 2D coordinate space. More...  
class  InteriorPointArea 
Computes a point in the interior of an areal geometry. The point will lie in the geometry interior in all except certain pathological cases. More...  
class  InteriorPointLine 
Computes a point in the interior of an linear geometry. More...  
class  InteriorPointPoint 
Computes a point in the interior of an point geometry. More...  
class  Intersection 
Computes the intersection point of two lines. If the lines are parallel or collinear this case is detected and null is returned. More...  
class  Length 
Functions for computing length. More...  
class  LineIntersector 
A LineIntersector is an algorithm that can both test whether two line segments intersect and compute the intersection point if they do. More...  
class  MinimumDiameter 
Computes the minimum diameter of a geom::Geometry. More...  
class  NotRepresentableException 
Indicates that a HCoordinate has been computed which is not representable on the Cartesian plane. More...  
class  Orientation 
Functions to compute the orientation of basic geometric structures including point triplets (triangles) and rings. More...  
class  PointLocation 
Functions for locating points within basic geometric structures such as lines and rings. More...  
class  PointLocator 
Computes the topological relationship (Location) of a single point to a Geometry. More...  
class  RayCrossingCounter 
Counts the number of segments crossed by a horizontal ray extending to the right from a given point, in an incremental fashion. More...  
class  RayCrossingCounterDD 
Counts the number of segments crossed by a horizontal ray extending to the right from a given point, in an incremental fashion. More...  
class  RobustDeterminant 
Implements an algorithm to compute the sign of a 2x2 determinant for double precision values robustly. More...  
Functions  
std::ostream &  operator<< (std::ostream &o, const HCoordinate &c) 
Contains classes and interfaces implementing fundamental computational geometry algorithms.
Geometrical algorithms involve a combination of combinatorial and numerical computation. As with all numerical computation using finiteprecision 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 roundoff 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 nonrobust versions. Fortunately, JTS is sensitive to robustness problems in only a few key functions (such as line intersection and the pointinpolygon test). There are efficient robust algorithms available for these functions, and these algorithms are implemented in JTS.
Runtime performance is an important consideration for a productionquality 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 (selfintersection) 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.