SegmentChecker identifies intersecting line segments. More...

#include <SegmentChecker.h>

Public Member Functions
	SegmentChecker (const std::vector< Segment2 * > &vSegments_)

ClipResult	clipSegment (Segment2 &seg)

void	getIllegalSegments (bool bAlsoEndPointIntersections, std::vector< Segment2 * > &vIllegalSegmentsOut) const

int	getIndex (Segment2 *pSeg) const

void	getIntersectionPoint (SegmentIntersectionType typ, const Segment2 &seg0, const Segment2 &seg1, Point2 &ispOut) const

void	getIntersectionSegment (const Segment2 &seg0, const Segment2 &seg1, Segment2 &issOut) const

SegmentIntersectionType	getIntersectionType (const Segment2 pSeg1, const Segment2 pSeg2) const

void	getIntersectors (Segment2 pTestSegment, bool bAlsoEndPointIntersections, std::vector< std::pair< Segment2 , SegmentIntersectionType > > &vIntersectorsOut) const

Bbox2	getLimit () const

size_t	getNumberOfSegments () const

Segment2 *	getSegment (size_t i) const

void	setLimit (const Bbox2 &bbx)

void	showIllegalSegments (bool bAlsoEndPointIntersections, const char *name) const

void	showSegments (const char *name) const

void	subscribe (MsgType msgType, MsgBase *pMsg)

void	unsubscribe (MsgType msgType, MsgBase *pMsg)

Static Public Member Functions
static const char *	getIntersectionTypeString (SegmentIntersectionType sit)

Detailed Description

SegmentChecker takes a bunch of line segments and fully automatically identifies illegal segment intersections. The intersection points can be computed in 2D and in 2.5D. Further this class offers visualization methods. Due to the underlying datastructure the search algorithm scales very well to large inputs.

Polylines: Intersecting segments are automatically found

See also: http://www.geom.at/segment-checker/

Constructor & Destructor Documentation

◆ SegmentChecker()

GEOM_FADE2D::SegmentChecker::SegmentChecker ( const std::vector< Segment2 * > & vSegments_ )

explicit

Internally this constructor prepares a data structure from vSegments that enables efficient spatial searches. The time complexity is O(n*log(n)).

Parameters

vSegments_ contains the segments to be checked

Member Function Documentation

◆ clipSegment()

ClipResult GEOM_FADE2D::SegmentChecker::clipSegment ( Segment2 & seg )

Clip Segment

Use this method to limit the length of a line-segment to its intersection with a box. The result can be the whole segment, a subsegment, a degenerate segment or the result can be empty. In the last case the segment is not changed but the method returns CR_EMPTY.

Parameters

[in,out] seg is the line segment to be clipped

Returns: CR_INVALID,CR_EMPTY, CR_CLIPPED_DEGENERATE, CR_CLIPPED_NONDEGENERATE, CR_COMPLETE_DEGENERATE, CR_COMPLETE_NONDEGENERATE or CR_INVALID.

Note: In case that you missed to call setLimit() with a valid bounding box before, the method returns CR_INVALID };

◆ getIllegalSegments()

void GEOM_FADE2D::SegmentChecker::getIllegalSegments	(	bool	bAlsoEndPointIntersections,
		std::vector< Segment2 * > &	vIllegalSegmentsOut
	)		const

Get illegal segments

Returns segments which are involved in intersections. Intersections at endpoints are only reported when bAlsoEndPointIntersections is true. The asymptotic time consumption for the lookup per segment S is O(log(n)+k) where k is the number of segments that intersect the minimal bounding box of S. Thus, for n segments the method takes O(n*(log(n)+k)) time.

Segment intersections: (1) Non-collinear, (2) collinear, (3) duplicate segments, (4) endpoint intersection

Parameters

	bAlsoEndPointIntersections	specifies if intersections at endpoints shall be detected
[out]	vIllegalSegmentsOut	is the output vector

◆ getIndex()

int GEOM_FADE2D::SegmentChecker::getIndex ( Segment2 * pSeg ) const

Returns the index of a segment

Parameters

pSeg	is the segment whose index is returned

◆ getIntersectionPoint()

void GEOM_FADE2D::SegmentChecker::getIntersectionPoint	(	SegmentIntersectionType	typ,
		const Segment2 &	seg0,
		const Segment2 &	seg1,
		Point2 &	ispOut
	)		const

Compute the intersection point of two segments

Use getIntersectionType() to determine the segment intersection type sit.

Parameters

	typ	is the intersection type (SIT_POINT or SIT_ENDPOINT for the present method)
	seg0,seg1	are the intersecting segments
[out]	ispOut	is the output intersection point.

Note: pSeg1 and pSeg2 do not need to be from the set that has been used to initialize the SegmentChecker.

◆ getIntersectionSegment()

void GEOM_FADE2D::SegmentChecker::getIntersectionSegment	(	const Segment2 &	seg0,
		const Segment2 &	seg1,
		Segment2 &	issOut
	)		const

Computes the intersection segment of two collinear intersecting segments

Parameters

	seg0,seg1	are intersecting segments such that their SegmentIntersectionType is SIT_SEGMENT
[out]	issOut	is the computed intersection of `seg0` and `seg1`

Note: pSeg1 and pSeg2 do not need to be from the set that has been used to initialize the present object

◆ getIntersectionType()

SegmentIntersectionType GEOM_FADE2D::SegmentChecker::getIntersectionType	(	const Segment2 *	pSeg1,
		const Segment2 *	pSeg2
	)		const

Get the intersection type of two segments

Parameters

pSeg1,pSeg2 are the segments to be checked

Returns: SIT_NONE (no intersection),
SIT_SEGMENT (collinear intersection),
SIT_POINT (intersection somewhere between the endpoints) or
SIT_ENDPOINT (endpoint intersection)

Note: pSeg1 and pSeg2 do not need to be from the set that has been used to initialize the present object

◆ getIntersectionTypeString()

static const char* GEOM_FADE2D::SegmentChecker::getIntersectionTypeString ( SegmentIntersectionType sit )

static

Return the intersection type as a human readable string. This is a convenience function

Parameters

sit	is an intersection type to be converted to a string

◆ getIntersectors()

void GEOM_FADE2D::SegmentChecker::getIntersectors	(	Segment2 *	pTestSegment,
		bool	bAlsoEndPointIntersections,
		std::vector< std::pair< Segment2 *, SegmentIntersectionType > > &	vIntersectorsOut
	)		const

Return segments that intersect a certain segment along with their intersection type

Parameters

	pTestSegment	is the segment to be analyzed
	bAlsoEndPointIntersections	specifies if intersections of type SIT_ENDPOINT shall also be reported.
[out]	vIntersectorsOut	is the output vector. Segments intersecting `pTestSegment` are added to `vIntersectorsOut` along with their intersection type.

Note: When vIntersectorsOut is non-empty, it is not cleared but the intersected segments are added.

The time complexity is O(log(n)+k) where n is the number of segments and k is the number of intersections for pTestSegment.

◆ getLimit()

Bbox2 GEOM_FADE2D::SegmentChecker::getLimit ( ) const

Get Limit

Returns: the bounding box that has been set before using setLimit()

◆ getNumberOfSegments()

size_t GEOM_FADE2D::SegmentChecker::getNumberOfSegments ( ) const

Returns the number of segments contained in this SegmentChecker object

◆ getSegment()

Segment2* GEOM_FADE2D::SegmentChecker::getSegment ( size_t i ) const

Returns the i-th segment

Parameters

i	is the index of the segment to be returned

◆ setLimit()

void GEOM_FADE2D::SegmentChecker::setLimit ( const Bbox2 & bbx )

Set Limit

Sets the bounding box bbx that is used by clipSegment() to limit the length of a line segment

◆ showIllegalSegments()

void GEOM_FADE2D::SegmentChecker::showIllegalSegments	(	bool	bAlsoEndPointIntersections,
		const char *	name
	)		const

Write a postscript file, highlight illegal segments

Parameters

bAlsoEndPointIntersections	specifies if intersections at endpoints are also illegal
name	is the output filename

Visualization of polyline intersections

◆ showSegments()

void GEOM_FADE2D::SegmentChecker::showSegments ( const char * name ) const

Write all segments, with and without intersection, to a postscript file

Parameters

name	is the output filename

Line segments written to a postscript file

◆ subscribe()

void GEOM_FADE2D::SegmentChecker::subscribe	(	MsgType	msgType,
		MsgBase *	pMsg
	)

Register a progress bar object

The SegmentChecker does its job typically in fractions of a second. But inputs may contain a quadratic number of intersections and such tasks take a while. Therefore a user defined message object (your own progress-bar class) can be registered in order to get progress updates. This step is optional.

Parameters

msgType	is the message type. For progress information the type is always MSG_PROGRESS
pMsg	is a user defined progress bar which derives from Fade's MsgBase.

◆ unsubscribe()

void GEOM_FADE2D::SegmentChecker::unsubscribe	(	MsgType	msgType,
		MsgBase *	pMsg
	)

Unregister a progress bar object

Parameters

msgType	is the message type. For progress information the type is always MSG_PROGRESS
pMsg	is a user defined class which derives from Fade's MsgBase

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

SegmentChecker.h

Public Member Functions

Static Public Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ SegmentChecker()

Member Function Documentation

◆ clipSegment()

◆ getIllegalSegments()

◆ getIndex()

◆ getIntersectionPoint()

◆ getIntersectionSegment()

◆ getIntersectionType()

◆ getIntersectionTypeString()

◆ getIntersectors()

◆ getLimit()

◆ getNumberOfSegments()

◆ getSegment()

◆ setLimit()

◆ showIllegalSegments()

◆ showSegments()

◆ subscribe()

◆ unsubscribe()