Categories
Fade2.5D Examples

Segment Checker for 2.5D Segment Intersections

The Segment Checker computes intersections of 3D line segments. Thereby two segments are considered to intersect when their projections in the xy-plane intersect. In other words, even if the involved segments are at different heights. The Segment Checker is fast and it is robust against degenerate and glancing intersections.

C++ Example: Segment Intersections

500 Random Segments
Intersection computation for 500 random segments

Let’s go through the below source code:

  1. Create 500 random line segments
  2. Create a SegmentChecker determine just the intersecting segments
  3. Draw the intersections
  4. To avoid mile-long output select just one intersecting segment pSeg for further demonstration
  5. For pSeg, determine the overlapping segments with their SegmentIntersectionType, whose possible values are listed in the table below.
  6. For any segment pOtherSeg which intersects pSeg the intersection type and the intersection is then printed out. This intersection may be a point or a segment. Or, in case of different height values, 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
Segment Intersection Types

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)

Leave a Reply

Your email address will not be published. Required fields are marked *