The Segment Checker computes intersections of 2D or 2.5D line segments. In contrast to 3D two line segments are considered to intersect when their 2D projections in the xy-plane intersect. In other words, even if the involved segments are at different heights. Most importantly the Segment Checker is fast and in addition it is robust against degenerate and glancing intersections.
C++ Example: Segment Intersections
Let’s go through the below source code:
- Firstly, create 500 random line segments
- Secondly, create a SegmentChecker and determine just the intersecting segments
- Then draw the intersections
- To demonstrate select just one intersecting segment
pSeg - Afterards determine for
pSegthe overlapping segments with theirSegmentIntersectionType. The possible values are listed in the table further below. - Finally print for any intersecting segment
pOtherSegthe intersection. This intersection may be a point or a segment, for instance. However, the segments might be located at different elevations. As a result the intersection might also consist of two points or two segments.
// d0: segmentChecker
int segmentChecker_main()
{
std::cout<<gRed("\n\n\n+++ +++ +++ +++ +++ +++ +++")<<std::endl;
std::cout<<"\n\n* Fade2.5D Demo - Segment Checker\n"<<std::endl;
// * 1 * Create random segments:
vector<Segment2*> vRndSeg;
for(size_t i=0;i<500;++i)
{
Point2 p0(rnd(100),rnd(100),rnd(20));
Point2 p1(rnd(100),rnd(100),rnd(20));
vRndSeg.push_back(new Segment2(p0,p1));
}
// * 2 * Find all intersecting segments
SegmentChecker segChecker(vRndSeg);
std::vector<Segment2*> vIntersectingSeg;
segChecker.getIllegalSegments(false,vIntersectingSeg);
cout<<"Intersecting segments: "<<vIntersectingSeg.size()<<endl;
// * 3 * Draw the intersections
segChecker.showIllegalSegments(false,"d0_intersections.ps");
if(vIntersectingSeg.empty()) return 0;
// * 4 * Demonstrate just for one intersecting segment
// how to analyze its intersections
Segment2* pSeg(vIntersectingSeg[0]);
cout<<"\nAnalyzing segment no. "<<segChecker.getIndex(pSeg)<<": "<<endl;
// * 5 * Get the intersectors of pSeg
std::vector<std::pair< Segment2*,SegmentIntersectionType> > vIntersectors;
segChecker.getIntersectors(pSeg,false,vIntersectors);
// * 6 * Iterate over the intersectors of pSeg:
for(size_t j=0;j<vIntersectors.size();++j)
{
// a: The intersector and the intersection type
Segment2* pOtherSeg(vIntersectors[j].first);
SegmentIntersectionType sit(vIntersectors[j].second);
cout<<" Conflicting segment no. "<<segChecker.getIndex(pOtherSeg)<<"\t type="<<segChecker.getIntersectionTypeString(sit)<<endl;
// b: Depending on the segment intersection type (sit):
switch(sit)
{
case SIT_ENDPOINT:
case SIT_POINT:
{
// Two segments can intersect at two different z values, thus two intersection points
Point2 isp0,isp1;
segChecker.getIntersectionPoint(sit,*pSeg,*pOtherSeg,isp0,isp1);
cout<<" intersection point on segment "<<segChecker.getIndex(pSeg)<<": "<<isp0<<endl;
cout<<" intersection point on segment "<<segChecker.getIndex(pOtherSeg)<<": "<<isp1<<endl;
break;
}
case SIT_SEGMENT:
{
// Same for a collinear intersection, there may be two segments at different heights
Segment2 iss0,iss1;
segChecker.getIntersectionSegment(*pSeg,*pOtherSeg,iss0,iss1);
cout<<" intersection segment on segment "<<segChecker.getIndex(pSeg)<<": "<<iss0<<endl;
cout<<" intersection segment on segment "<<segChecker.getIndex(pOtherSeg)<<": "<<iss1<<endl;
break;
}
case SIT_NONE: // Never reached
{
cout<<" no intersection, impossible case"<<endl;
break;
}
default: // Never reached
{
cout<<" uninitialized, impossible case"<<endl;
}
}
}
cout<<"\n\nEND\n------------------------------"<<endl;
return 0;
}
| SIT_UNINITIALIZED | Invalid value |
| SIT_NONE | No intersection |
| SIT_SEGMENT | The intersection is a segment (collinear intersection) |
| SIT_POINT | The intersection is a single point differnt from the endpoints |
| SIT_ENDPOINT | The two segments only share a common endpoint |
Analyzing segment no. 0:
Conflicting segment no. 378 type=SIT_POINT
intersection point on segment 0: Point2: -62.7844, 69.3294, 0
intersection point on segment 378: Point2: -62.7844, 69.3294, 0
Conflicting segment no. 323 type=SIT_POINT
intersection point on segment 0: Point2: -74.9106, 72.646, 0
intersection point on segment 323: Point2: -74.9106, 72.646, 0
And so on…. (output truncated)