The Segment Checker computes intersections of 2D or 2.5D line segments. But 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. The Segment Checker is fast and 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)