Given a set of line segments, the fast C++ class Segment Checker detects if any two segments intersect. Intersection points (or segments in the collinear case) are computed. Segment Checker accepts 2D and 2.5D segments and it copes with glancing segment intersections. With the example source code below you can integrate it into your software within minutes.

Simple Example in C++

The intersection test takes 0.003 seconds for 1000 random line segments

Create 1000 Random Segments

Use generateRandomSegments(..) from module testDataGenerators to create segments within the coordinate range (-100,+100) and with length up to 30.0.

void segmentCheckerSimple_main()
{
  // * 1 *   Create random segments
  vector<Segment2> vRandomSegments;
  generateRandomSegments(1000,-100,+100,30,vRandomSegments,1);
  vector<Segment2*> vRandomSegmentPtrs;
  for(size_t i=0;i<vRandomSegments.size();++i) 
  {
    vRandomSegmentPtrs.push_back(&vRandomSegments[i]);
  }
  ...
}

Find the intersecting segments

Call SegmentChecker::getIllegalSegments(..) to find the intersecting segments. You can choose if endpoint intersections shall be reported or not.

    // * 2 *   Determine all intersecting segments
    SegmentChecker segChecker(vRandomSegmentPtrs);
    std::vector<Segment2*> vIllegalSegments;
    segChecker.getIllegalSegments(false,vIllegalSegments);

Print intersecting segments

Iterate over the intersecting segments and print to stdout.

    // * 3 *   Analyze the intersecting segments
    cout<<"Number of illegal segments: "<<vIllegalSegments.size()<<endl;
    for(size_t i=0;i<vIllegalSegments.size();++i)
    {
        Segment2* pSeg(vIllegalSegments[i]);
        cout<<"\nAnalyzing segment no. "<<segChecker.getIndex(pSeg)<<": "<<endl;

        // Get the intersectors of pSeg
        std::vector<std::pair< Segment2*,SegmentIntersectionType> > vIntersectors;
        segChecker.getIntersectors(pSeg,false,vIntersectors);

        // Iterate over the intersectors of pSeg:
        for(size_t j=0;j<vIntersectors.size();++j)
        {
            // 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;

            // 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;
                }
            }
        }
    }

Visualize

Create a postscript visualization.

    // * 4 *   Visualize the segments and their intersections
    segChecker.showIllegalSegments(false,"simpleSegments_out.ps");

Terrain Example

A 2.5D Terrain Triangulation

Create a set of segments

For demonstration purposes we need a set of segments that we can check and this is the purpose of the code below. Besides, this piece of code is taken from the former terrain triangulation example. Its output is a vector vISO of intersection free segments.

ISO Contours (line segments) of a Terrain

void segmentChecker_main()
{
  // * 1 *   Read terrain points from an ASCII file (X Y Z)
  vector<Point2> vTerrainPoints;
  if(!readXYZ("gaeta_small.xyz",vTerrainPoints)) return;

  // * 2 *   Triangulate the points
  Fade_2D dt;
  dt.insert(vTerrainPoints);

  // * 3 *   Compute ISO contours (these do clearly not intersect each other)
  std::vector<Triangle2*> vTriangles;
  dt.getTrianglePointers(vTriangles);
  std::vector<Segment2> vISO;
  isoContours(vTriangles,vISO);
  cout<<"numTriangles: "<<vTriangles.size()<<", num ISO segments: "<<vISO.size()<<endl;
  ...

Detect intersections

The code above creates 105739 intersection free segments (ISO contours) as shown in the picture above. Now add one additional horizontal segment that intersects a few other segments. Then create a SegmentChecker, register a custom progress bar and call the getIllegalSegments() method. The progress bar is only there for demonstration purposes. It takes only 0.09 seconds to check all 105739 line segments (measured on a Core i7 6800 CPU):

...
  // * 4 *   Create one additional Segment which intersects other segments
  Segment2 fakeSegment(
          Point2(2391500,4569000, 4711),
          Point2(2396000,4569000, 4711));
  vISO.push_back(fakeSegment);

  // * 5 *   Determine intersecting segments
  std::vector<Segment2*> vISOPtr; // Segment Checker needs pointers to segments
  for(size_t i=0;i<vISO.size();++i) vISOPtr.push_back(&amp;vISO[i]);
  MyProgressBar progressBar;

  timer("getIllegalSegments");
    SegmentChecker segChecker(vISOPtr);
    segChecker.subscribe(MSG_PROGRESS,&amp;progressBar);

    std::vector<Segment2*> vIllegalSegments;
    segChecker.getIllegalSegments(false,vIllegalSegments);
  timer("getIllegalSegments"); // Takes 0.09 seconds for 105739 segments of which 37 do intersect

...

Note: For practical reasons the data provided with the demo code has been simplified, it will generate only 42882 ISO segments and find 14 intersections.

Compute the intersection points (or segments in the collinear case)

Earlier we have stored segments with illegal intersections in vIllegalSegments. To analyze the intersection(s) of a certain segment pSeg we call getIntersectors(pSeg,…) which returns the intersecting segments along with their SegmentIntersectionType. Depending on this type we must call either getIntersectionPoint() or getIntersectionSegment() to compute the intersection.

...
  // * 7 *   Analyze the illegal segments
  for(size_t i=0;i<vIllegalSegments.size();++i)
  {
    Segment2* pSeg(vIllegalSegments[i]);
    cout<<"\nAnalyzing segment no. "<<segChecker.getIndex(pSeg)<<": "<<endl;

    // Get the intersectors of pSeg
    std::vector<std::pair< Segment2*,SegmentIntersectionType> > vIntersectors;
    segChecker.getIntersectors(pSeg,false,vIntersectors);

    // Iterate over the intersectors of pSeg:
    for(size_t j=0;j<vIntersectors.size();++j)
    {
            // 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;

            // 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;
                }
                
...

Each (x,y) intersection point is printed twice, namely at different heights z.

Visualize

The code line below draws the set of segments as Postscript graphic. Intersecting segments are highlighted in red, the intersection points are marked blue.

...
  // * 6 *   Visualization
  segChecker.showIllegalSegments(false,"illegalSegments.ps");
...

Illegal segment intersections

Zoom: Intersecting segments (red), intersection points (blue)