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

#include <LineIntersector.h>

Collaboration diagram for geos::algorithm::LineIntersector:

[legend]

Public Types
enum	intersection_type : uint8_t { NO_INTERSECTION = 0, POINT_INTERSECTION = 1, COLLINEAR_INTERSECTION = 2 }

Public Member Functions
	LineIntersector (const geom::PrecisionModel *initialPrecisionModel=nullptr)

	~LineIntersector ()

bool	isInteriorIntersection ()
	Tests whether either intersection point is an interior point of one of the input segments. More...

bool	isInteriorIntersection (size_t inputLineIndex)
	Tests whether either intersection point is an interior point of the specified input segment. More...

void	setPrecisionModel (const geom::PrecisionModel *newPM)

void	computeIntersection (const geom::Coordinate &p, const geom::Coordinate &p1, const geom::Coordinate &p2)

void	computeIntersection (const geom::Coordinate &p1, const geom::Coordinate &p2, const geom::Coordinate &p3, const geom::Coordinate &p4)
	Computes the intersection of the lines p1-p2 and p3-p4. More...

std::string	toString () const

bool	hasIntersection () const

size_t	getIntersectionNum () const

const geom::Coordinate &	getIntersection (size_t intIndex) const

bool	isIntersection (const geom::Coordinate &pt) const
	Test whether a point is a intersection point of two line segments. More...

bool	isProper () const
	Tests whether an intersection is proper. More...

const geom::Coordinate &	getIntersectionAlongSegment (size_t segmentIndex, size_t intIndex)
	Computes the intIndex'th intersection point in the direction of a specified input line segment. More...

size_t	getIndexAlongSegment (size_t segmentIndex, size_t intIndex)
	Computes the index of the intIndex'th intersection point in the direction of a specified input line segment. More...

double	getEdgeDistance (size_t geomIndex, size_t intIndex) const
	Computes the "edge distance" of an intersection point along the specified input line segment. More...

Static Public Member Functions
static double	interpolateZ (const geom::Coordinate &p, const geom::Coordinate &p0, const geom::Coordinate &p1)
	Return a Z value being the interpolation of Z from p0 and p1 at the given point p. More...

static double	computeEdgeDistance (const geom::Coordinate &p, const geom::Coordinate &p0, const geom::Coordinate &p1)

static double	nonRobustComputeEdgeDistance (const geom::Coordinate &p, const geom::Coordinate &p1, const geom::Coordinate &p2)

static bool	hasIntersection (const geom::Coordinate &p, const geom::Coordinate &p1, const geom::Coordinate &p2)
	Same as above but doesn't compute intersection point. Faster. More...

static bool	isSameSignAndNonZero (double a, double b)

Private Member Functions
bool	isCollinear () const

uint8_t	computeIntersect (const geom::Coordinate &p1, const geom::Coordinate &p2, const geom::Coordinate &q1, const geom::Coordinate &q2)

bool	isEndPoint () const

void	computeIntLineIndex ()

void	computeIntLineIndex (size_t segmentIndex)

uint8_t	computeCollinearIntersection (const geom::Coordinate &p1, const geom::Coordinate &p2, const geom::Coordinate &q1, const geom::Coordinate &q2)

geom::Coordinate	intersection (const geom::Coordinate &p1, const geom::Coordinate &p2, const geom::Coordinate &q1, const geom::Coordinate &q2) const
	This method computes the actual value of the intersection point. More...

bool	isInSegmentEnvelopes (const geom::Coordinate &intPt) const

geom::Coordinate	intersectionSafe (const geom::Coordinate &p1, const geom::Coordinate &p2, const geom::Coordinate &q1, const geom::Coordinate &q2) const

Static Private Member Functions
static geom::Coordinate	nearestEndpoint (const geom::Coordinate &p1, const geom::Coordinate &p2, const geom::Coordinate &q1, const geom::Coordinate &q2)

static double	zGet (const geom::Coordinate &p, const geom::Coordinate &q)

static double	zGetOrInterpolate (const geom::Coordinate &p, const geom::Coordinate &p0, const geom::Coordinate &p1)

static geom::Coordinate	zGetOrInterpolateCopy (const geom::Coordinate &p, const geom::Coordinate &p0, const geom::Coordinate &p1)

static double	zInterpolate (const geom::Coordinate &p, const geom::Coordinate &p0, const geom::Coordinate &p1)
	Return a Z value being the interpolation of Z from p0 to p1 at the given point p. More...

static double	zInterpolate (const geom::Coordinate &p, const geom::Coordinate &p1, const geom::Coordinate &p2, const geom::Coordinate &q1, const geom::Coordinate &q2)

Private Attributes
const geom::PrecisionModel *	precisionModel

size_t	result

const geom::Coordinate *	inputLines [2][2]

geom::Coordinate	intPt [2]

size_t	intLineIndex [2][2]

bool	isProperVar

Detailed Description

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. (This assumes that the input coordinates have been made precise by scaling them to an integer grid.)

Definition at line 49 of file LineIntersector.h.

Member Enumeration Documentation

enum geos::algorithm::LineIntersector::intersection_type : uint8_t

Enumerator
NO_INTERSECTION	Indicates that line segments do not intersect.
POINT_INTERSECTION	Indicates that line segments intersect in a single point.
COLLINEAR_INTERSECTION	Indicates that line segments intersect in a line segment.

Definition at line 131 of file LineIntersector.h.

Constructor & Destructor Documentation

geos::algorithm::LineIntersector::LineIntersector ( const geom::PrecisionModel * initialPrecisionModel = nullptr )

inline

Definition at line 81 of file LineIntersector.h.

geos::algorithm::LineIntersector::~LineIntersector ( )

inline

Definition at line 88 of file LineIntersector.h.

Member Function Documentation

uint8_t geos::algorithm::LineIntersector::computeCollinearIntersection	(	const geom::Coordinate &	p1,
		const geom::Coordinate &	p2,
		const geom::Coordinate &	q1,
		const geom::Coordinate &	q2
	)

private

static double geos::algorithm::LineIntersector::computeEdgeDistance	(	const geom::Coordinate &	p,
		const geom::Coordinate &	p0,
		const geom::Coordinate &	p1
	)

static

Computes the "edge distance" of an intersection point p in an edge.

The edge distance is a metric of the point along the edge. The metric used is a robust and easy to compute metric function. It is not equivalent to the usual Euclidean metric. It relies on the fact that either the x or the y ordinates of the points in the edge are unique, depending on whether the edge is longer in the horizontal or vertical direction.

NOTE: This function may produce incorrect distances for inputs where p is not precisely on p1-p2 (E.g. p = (139,9) p1 = (139,10), p2 = (280,1) produces distanct 0.0, which is incorrect.

My hypothesis is that the function is safe to use for points which are the result of rounding points which lie on the line, but not safe to use for truncated points.

uint8_t geos::algorithm::LineIntersector::computeIntersect	(	const geom::Coordinate &	p1,
		const geom::Coordinate &	p2,
		const geom::Coordinate &	q1,
		const geom::Coordinate &	q2
	)

private

void geos::algorithm::LineIntersector::computeIntersection	(	const geom::Coordinate &	p,
		const geom::Coordinate &	p1,
		const geom::Coordinate &	p2
	)

Compute the intersection of a point p and the line p1-p2.

This function computes the boolean value of the hasIntersection test. The actual value of the intersection (if there is one) is equal to the value of p.

void geos::algorithm::LineIntersector::computeIntersection	(	const geom::Coordinate &	p1,
		const geom::Coordinate &	p2,
		const geom::Coordinate &	p3,
		const geom::Coordinate &	p4
	)

Computes the intersection of the lines p1-p2 and p3-p4.

void geos::algorithm::LineIntersector::computeIntLineIndex ( )

private

void geos::algorithm::LineIntersector::computeIntLineIndex ( size_t segmentIndex )

private

double geos::algorithm::LineIntersector::getEdgeDistance	(	size_t	geomIndex,
		size_t	intIndex
	)		const

Computes the "edge distance" of an intersection point along the specified input line segment.

Parameters

geomIndex	is 0 or 1
intIndex	is 0 or 1

Returns: the edge distance of the intersection point

size_t geos::algorithm::LineIntersector::getIndexAlongSegment	(	size_t	segmentIndex,
		size_t	intIndex
	)

Computes the index of the intIndex'th intersection point in the direction of a specified input line segment.

Parameters

segmentIndex	is 0 or 1
intIndex	is 0 or 1

Returns: the index of the intersection point along the segment (0 or 1)

const geom::Coordinate& geos::algorithm::LineIntersector::getIntersection ( size_t intIndex ) const

inline

Returns the intIndex'th intersection point

Parameters

intIndex is 0 or 1

Returns: the intIndex'th intersection point

Definition at line 177 of file LineIntersector.h.

const geom::Coordinate& geos::algorithm::LineIntersector::getIntersectionAlongSegment	(	size_t	segmentIndex,
		size_t	intIndex
	)

Computes the intIndex'th intersection point in the direction of a specified input line segment.

Parameters

segmentIndex	is 0 or 1
intIndex	is 0 or 1

Returns: the intIndex'th intersection point in the direction of the specified input line segment

size_t geos::algorithm::LineIntersector::getIntersectionNum ( ) const

inline

Returns the number of intersection points found.

This will be either 0, 1 or 2.

Definition at line 164 of file LineIntersector.h.

static bool geos::algorithm::LineIntersector::hasIntersection	(	const geom::Coordinate &	p,
		const geom::Coordinate &	p1,
		const geom::Coordinate &	p2
	)

static

Same as above but doesn't compute intersection point. Faster.

bool geos::algorithm::LineIntersector::hasIntersection ( ) const

inline

Tests whether the input geometries intersect.

Returns: true if the input geometries intersect

Definition at line 154 of file LineIntersector.h.

static double geos::algorithm::LineIntersector::interpolateZ	(	const geom::Coordinate &	p,
		const geom::Coordinate &	p0,
		const geom::Coordinate &	p1
	)

static

Return a Z value being the interpolation of Z from p0 and p1 at the given point p.

geom::Coordinate geos::algorithm::LineIntersector::intersection	(	const geom::Coordinate &	p1,
		const geom::Coordinate &	p2,
		const geom::Coordinate &	q1,
		const geom::Coordinate &	q2
	)		const

private

This method computes the actual value of the intersection point.

To obtain the maximum precision from the intersection calculation, the coordinates are normalized by subtracting the minimum ordinate values (in absolute value). This has the effect of removing common significant digits from the calculation to maintain more bits of precision.

geom::Coordinate geos::algorithm::LineIntersector::intersectionSafe	(	const geom::Coordinate &	p1,
		const geom::Coordinate &	p2,
		const geom::Coordinate &	q1,
		const geom::Coordinate &	q2
	)		const

private

Computes a segment intersection. Round-off error can cause the raw computation to fail, (usually due to the segments being approximately parallel). If this happens, a reasonable approximation is computed instead.

Parameters

p1	a segment endpoint
p2	a segment endpoint
q1	a segment endpoint
q2	a segment endpoint

Returns: the computed intersection point is stored there

bool geos::algorithm::LineIntersector::isCollinear ( ) const

inlineprivate

Definition at line 283 of file LineIntersector.h.

bool geos::algorithm::LineIntersector::isEndPoint ( ) const

inlineprivate

Definition at line 292 of file LineIntersector.h.

bool geos::algorithm::LineIntersector::isInSegmentEnvelopes ( const geom::Coordinate & intPt ) const

private

Test whether a point lies in the envelopes of both input segments. A correctly computed intersection point should return true for this test. Since this test is for debugging purposes only, no attempt is made to optimize the envelope test.

Returns: true if the input point lies within both input segment envelopes

bool geos::algorithm::LineIntersector::isInteriorIntersection ( )

Tests whether either intersection point is an interior point of one of the input segments.

Returns: true if either intersection point is in the interior of one of the input segments

bool geos::algorithm::LineIntersector::isInteriorIntersection ( size_t inputLineIndex )

Tests whether either intersection point is an interior point of the specified input segment.

Returns: true if either intersection point is in the interior of the input segment

bool geos::algorithm::LineIntersector::isIntersection ( const geom::Coordinate & pt ) const

Test whether a point is a intersection point of two line segments.

Note that if the intersection is a line segment, this method only tests for equality with the endpoints of the intersection segment. It does not return true if the input point is internal to the intersection segment.

Returns: true if the input point is one of the intersection points.

bool geos::algorithm::LineIntersector::isProper ( ) const

inline

Tests whether an intersection is proper.

The intersection between two line segments is considered proper if they intersect in a single point in the interior of both segments (e.g. the intersection is a single point and is not equal to any of the endpoints).

The intersection between a point and a line segment is considered proper if the point lies in the interior of the segment (e.g. is not equal to either of the endpoints).

Returns: true if the intersection is proper

Definition at line 215 of file LineIntersector.h.

static bool geos::algorithm::LineIntersector::isSameSignAndNonZero	(	double	a,
		double	b
	)

static

Returns false if both numbers are zero.

Returns: true if both numbers are positive or if both numbers are negative.

static geom::Coordinate geos::algorithm::LineIntersector::nearestEndpoint	(	const geom::Coordinate &	p1,
		const geom::Coordinate &	p2,
		const geom::Coordinate &	q1,
		const geom::Coordinate &	q2
	)

staticprivate

Finds the endpoint of the segments P and Q which is closest to the other segment. This is a reasonable surrogate for the true intersection points in ill-conditioned cases (e.g. where two segments are nearly coincident, or where the endpoint of one segment lies almost on the other segment).

This replaces the older CentralEndpoint heuristic, which chose the wrong endpoint in some cases where the segments had very distinct slopes and one endpoint lay almost on the other segment.

Parameters

p1	an endpoint of segment P
p2	an endpoint of segment P
q1	an endpoint of segment Q
q2	an endpoint of segment Q

Returns: the nearest endpoint to the other segment

static double geos::algorithm::LineIntersector::nonRobustComputeEdgeDistance	(	const geom::Coordinate &	p,
		const geom::Coordinate &	p1,
		const geom::Coordinate &	p2
	)

static

void geos::algorithm::LineIntersector::setPrecisionModel ( const geom::PrecisionModel * newPM )

inline

Force computed intersection to be rounded to a given precision model.

No getter is provided, because the precision model is not required to be specified.

Parameters

newPM the PrecisionModel to use for rounding

Definition at line 115 of file LineIntersector.h.

std::string geos::algorithm::LineIntersector::toString ( ) const

static double geos::algorithm::LineIntersector::zGet	(	const geom::Coordinate &	p,
		const geom::Coordinate &	q
	)

staticprivate

static double geos::algorithm::LineIntersector::zGetOrInterpolate	(	const geom::Coordinate &	p,
		const geom::Coordinate &	p0,
		const geom::Coordinate &	p1
	)

staticprivate

static geom::Coordinate geos::algorithm::LineIntersector::zGetOrInterpolateCopy	(	const geom::Coordinate &	p,
		const geom::Coordinate &	p0,
		const geom::Coordinate &	p1
	)

staticprivate

static double geos::algorithm::LineIntersector::zInterpolate	(	const geom::Coordinate &	p,
		const geom::Coordinate &	p0,
		const geom::Coordinate &	p1
	)

staticprivate

Return a Z value being the interpolation of Z from p0 to p1 at the given point p.

static double geos::algorithm::LineIntersector::zInterpolate	(	const geom::Coordinate &	p,
		const geom::Coordinate &	p1,
		const geom::Coordinate &	p2,
		const geom::Coordinate &	q1,
		const geom::Coordinate &	q2
	)

staticprivate

Member Data Documentation

const geom::Coordinate* geos::algorithm::LineIntersector::inputLines[2][2]

private

Definition at line 264 of file LineIntersector.h.

size_t geos::algorithm::LineIntersector::intLineIndex[2][2]

private

The indexes of the endpoints of the intersection lines, in order along the corresponding line

Definition at line 276 of file LineIntersector.h.

geom::Coordinate geos::algorithm::LineIntersector::intPt[2]

private

We store real Coordinates here because we must compute the Z of intersection point.

Definition at line 270 of file LineIntersector.h.

bool geos::algorithm::LineIntersector::isProperVar

private

Definition at line 278 of file LineIntersector.h.

const geom::PrecisionModel* geos::algorithm::LineIntersector::precisionModel

private

If makePrecise is true, computed intersection coordinates will be made precise using Coordinate::makePrecise

Definition at line 260 of file LineIntersector.h.

size_t geos::algorithm::LineIntersector::result

private

Definition at line 262 of file LineIntersector.h.

The documentation for this class was generated from the following file:

LineIntersector.h

Public Types

Public Member Functions

Static Public Member Functions

Private Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

Member Enumeration Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation