2.5D Delaunay Triangulation Examples in C++

Segment Checker for 2D and 2.5D Segment Intersections

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

500 Random Segments
Intersection computation for 500 random segments

Let’s go through the below source code:

  1. Firstly, create 500 random line segments
  2. Secondly, create a SegmentChecker and determine just the intersecting segments
  3. Then draw the intersections
  4. To demonstrate select just one intersecting segment pSeg
  5. Afterards determine for pSeg the overlapping segments with their SegmentIntersectionType. The possible values are listed in the table further below.
  6. Finally print for any intersecting segment pOtherSeg the 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;
	cout<<"Intersecting segments: "<<vIntersectingSeg.size()<<endl;

	// * 3 *   Draw the intersections
	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;

	// * 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):
			case SIT_POINT:
				// Two segments can intersect at two different z values, thus two intersection points
				Point2 isp0,isp1;
				cout<<"    intersection point on segment "<<segChecker.getIndex(pSeg)<<": "<<isp0<<endl;
				cout<<"    intersection point on segment "<<segChecker.getIndex(pOtherSeg)<<": "<<isp1<<endl;

			case SIT_SEGMENT:
				// Same for a collinear intersection, there may be two segments at different heights
				Segment2 iss0,iss1;
				cout<<"    intersection segment on segment "<<segChecker.getIndex(pSeg)<<": "<<iss0<<endl;
				cout<<"    intersection segment on segment "<<segChecker.getIndex(pOtherSeg)<<": "<<iss1<<endl;
			case SIT_NONE: // Never reached
				cout<<"    no intersection, impossible case"<<endl;
			default: // Never reached
				cout<<"    uninitialized, impossible case"<<endl;

	return 0;
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 *