Namespace NetTopologySuite.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, NTS 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 NTS.

Computational Performance

Runtime performance is an important consideration for a production-quality implementation of geometric algorithms. The most computationally intensive algorithm used in NTS is intersection detection. NTS 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. NTS 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

Classes

AngleUtility

Utility functions for working with angles. Unless otherwise noted, methods in this class express angles in radians.

Area

Functions for computing area.

BoundaryNodeRules

Provides access to static instances of common IBoundaryNodeRules.

Centroid

Computes the centroid of a Geometry of any dimension. For collections the centroid is computed for the collection of non-empty elements of highest dimension. The centroid of an empty geometry is null

CGAlgorithms3D

Basic computational geometry algorithms for geometry and coordinates defined in 3-dimensional Cartesian space.

CGAlgorithmsDD

Implements basic computational geometry algorithms using DD arithmetic.

ConvexHull

Computes the convex hull of a Geometry. The convex hull is the smallest convex Geometry that contains all the points in the input Geometry. Uses the Graham Scan algorithm.

DistanceComputer

Functions to compute distance between basic geometric structures.

HCoordinate

Represents a homogeneous coordinate in a 2-D coordinate space. In NTS HCoordinates are used as a clean way of computing intersections between line segments.

InteriorPoint

Computes an interior point of a Geometry. An interior point is guaranteed to lie in the interior of the Geometry, if it possible to calculate such a point exactly. For collections the interior point is computed for the collection of non-empty elements of highest dimension. Otherwise, the point may lie on the boundary of the geometry.

The interior point of an empty geometry is POINT EMPTY.

Algorithm

The point is chosen to be "close to the center" of the geometry. The location depends on the dimension of the input:
  • Dimension 2the interior point is constructed in the middle of the longest interior segment of a line bisecting the area.
  • Dimension 1the interior point is the interior or boundary vertex closest to the centroid.
  • Dimension 0the point is the point closest to the centroid.
Centroid MaximumInscribedCircle LargestEmptyCircle

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.

InteriorPointLine

Computes a point in the interior of an linear point. Algorithm: Find an interior vertex which is closest to the centroid of the linestring. If there is no interior vertex, find the endpoint which is closest to the centroid.

InteriorPointPoint

Computes a point in the interior of an point point. Algorithm: Find a point which is closest to the centroid of the point.

IntersectionComputer

Functions to compute intersection points between lines and line segments.

In general it is not possible to compute the intersection point of two lines exactly, due to numerical roundoff. This is particularly true when the lines are nearly parallel. These routines uses numerical conditioning on the input values to ensure that the computed value is very close to the correct value.

The Z-ordinate is ignored, and not populated.

Length

Functions for computing length.

LineIntersector

A LineIntersector is an algorithm that can both test whether two line segments intersect and compute the intersection point(s) if they do.

There are three possible outcomes when determining whether two line segments intersect:

For segments which intersect in a single point, the point may be either an endpoint or in the interior of each segment. If the point lies in the interior of both segments, this is termed a proper intersection. The property IsProper test for this situation.

The intersection point(s) may be computed in a precise or non-precise manner. Computing an intersection point precisely involves rounding it via a supplied PrecisionModel.

LineIntersectors do not perform an initial envelope intersection test to determine if the segments are disjoint. This is because this class is likely to be used in a context where envelope overlap is already known to occur (or be likely).

MinimumBoundingCircle

Computes the Minimum Bounding Circle (MBC) for the points in a Geometry. The MBC is the smallest circle which covers all the input points (this is also sometimes known as the Smallest Enclosing Circle). This is equivalent to computing the Maximum Diameter of the input point set.

MinimumDiameter

Computes the minimum diameter of a Geometry.

NotRepresentableException

Orientation

Functions to compute the orientation of basic geometric structures including point triplets(triangles) and rings. Orientation is a fundamental property of planar geometries (and more generally geometry on two-dimensional manifolds).

Determining triangle orientation is notoriously subject to numerical precision errors in the case of collinear or nearly collinear points. NTS uses extended-precision arithmetic to increase the robustness of the computation.

PointLocation

Functions for locating points within basic geometric structures such as lines and rings.

PointLocator

Computes the topological relationship (Location) of a single point to a Geometry.

RayCrossingCounter

Counts the number of segments crossed by a horizontal ray extending to the right from a given point, in an incremental fashion.

This can be used to determine whether a point lies in a IPolygonal geometry.

The class determines the situation where the point lies exactly on a segment.

When being used for Point-In-Polygon determination, this case allows short-circuiting the evaluation.

RectangleLineIntersector

Computes whether a rectangle intersects line segments.

RobustDeterminant

Implements an algorithm to compute the sign of a 2x2 determinant for double precision values robustly. It is a direct translation of code developed by Olivier Devillers.

The original code carries the following copyright notice:

Author : Olivier Devillers Olivier.Devillers@sophia.inria.fr http:/www.inria.fr:/prisme/personnel/devillers/anglais/determinant.html

Olivier Devillers has allowed the code to be distributed under the LGPL (2012-02-16) saying "It is ok for LGPL distribution."

Copyright (c) 1995 by INRIA Prisme Project BP 93 06902 Sophia Antipolis Cedex, France. All rights reserved

RobustLineIntersector

A robust version of LineIntersector.

Interfaces

IBoundaryNodeRule

An interface for rules which determine whether node points which are in boundaries of ILineal geometry components are in the boundary of the parent geometry collection. The SFS specifies a single kind of boundary node rule, the NetTopologySuite.Algorithm.BoundaryNodeRules.Mod2BoundaryNodeRule rule. However, other kinds of Boundary Node Rules are appropriate in specific situations (for instance, linear network topology usually follows the NetTopologySuite.Algorithm.BoundaryNodeRules.EndPointBoundaryNodeRule.) Some JTS operations (such as RelateOp, BoundaryOp and IsSimpleOp) allow the BoundaryNodeRule to be specified, and respect the supplied rule when computing the results of the operation.

An example use case for a non-SFS-standard Boundary Node Rule is that of checking that a set of LineStrings have valid linear network topology, when turn-arounds are represented as closed rings. In this situation, the entry road to the turn-around is only valid when it touches the turn-around ring at the single (common) endpoint. This is equivalent to requiring the set of LineStrings to be simple under the NetTopologySuite.Algorithm.BoundaryNodeRules.EndPointBoundaryNodeRule. The SFS-standard NetTopologySuite.Algorithm.BoundaryNodeRules.Mod2BoundaryNodeRule is not sufficient to perform this test, since it states that closed rings have no boundary points.

This interface and its subclasses follow the Strategy design pattern.

IPointInAreaLocator

An interface for classes which determine the Location of points in a Geometry

Enums

OrientationIndex

Angle orientation