SegmentChecker identifies intersecting line segments.
More...
#include <SegmentChecker.h>
|
| 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 sit, const Segment2 &seg0, const Segment2 &seg1, Point2 &ispOut0, Point2 &ispOut1) const |
|
void | getIntersectionSegment (const Segment2 &seg0, const Segment2 &seg1, Segment2 &issOut0, Segment2 &issOut1) 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) |
|
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/
◆ SegmentChecker()
GEOM_FADE25D::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 |
◆ clipSegment()
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_FADE25D::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_FADE25D::SegmentChecker::getIndex |
( |
Segment2 * |
pSeg | ) |
const |
Returns the index of a segment
- Parameters
-
pSeg | is the segment whose index is returned |
◆ getIntersectionPoint()
Compute the intersection point(s) of two segments.
Use getIntersectionType() to determine the segment intersection type sit
before. Call this function only when the intersection type is SIT_POINT or SIT_ENDPOINT.
- Parameters
-
| sit | is the segment intersection type (SIT_POINT or SIT_ENDPOINT for the present method) |
| seg0,seg1 | are the intersecting segments |
[out] | ispOut0 | output intersection point at seg0 |
[out] | ispOut1 | output intersection point at seg1 |
The resulting two output intersection points ispOut0
and ispOut1
have always the same (x,y) coordinates but possibly different heights z
.
- Note
pSeg1
and pSeg2
do not need to be from the set of segments that have been used as argument for the constructor of the SegmentChecker. You can use any segments.
◆ getIntersectionSegment()
Compute the intersection segment(s) of two collinear intersecting segments.
Use getIntersectionType() to determine the segment intersection type sit
before. Call this function only when the intersection type is SIT_SEGMENT.
- Parameters
-
| seg0,seg1 | are intersecting segments such that their SegmentIntersectionType is SIT_SEGMENT |
[out] | issOut0 | intersection segment at seg0 |
[out] | issOut1 | intersection segment at seg1 |
The two output segments have always the same (x,y) coordinates but possibly diffent heights z
.
- Note
pSeg1
and pSeg2
do not need to be from the set of segments that have been used as argument for the constructor of the SegmentChecker. You can use any segments.
◆ getIntersectionType()
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()
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_FADE25D::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_FADE25D::SegmentChecker::getLimit |
( |
| ) |
const |
Get Limit
- Returns
- the bounding box that has been set before using setLimit()
◆ getNumberOfSegments()
size_t GEOM_FADE25D::SegmentChecker::getNumberOfSegments |
( |
| ) |
const |
Returns the number of segments contained in this SegmentChecker object
◆ getSegment()
Segment2* GEOM_FADE25D::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_FADE25D::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_FADE25D::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_FADE25D::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_FADE25D::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_FADE25D::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: