Segment Checker for Segment Intersections

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++

Let’s start with a simple example:

  • Create 1000 random segments
  • Find all segment intersections
  • Print intersecting segments
  • Visualization

The intersection detection algorithm checks 1000 segments in only 3 ms. Measured on a Core i7 6800K CPU.

Line Segment Intersections: 1000 Segments checked in 0.003 seconds

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;
                }
            }
        }
    }
Output of the above code:
Analyzing segment no. 0:
Conflicting segment no. 788  type=SIT_POINT
intersection point on segment 0: Point2 (0x7fffacdccc60,-1): -39.274804, -50.385439, 0.000000
intersection point on segment 788: Point2 (0x7fffacdcccb0,-1): -39.274804, -50.385439, 0.000000
Conflicting segment no. 155  type=SIT_POINT
intersection point on segment 0: Point2 (0x7fffacdccc60,-1): -40.659588, -53.311972, 0.000000
intersection point on segment 155: Point2 (0x7fffacdcccb0,-1): -40.659588, -53.311972, 0.000000
Conflicting segment no. 680  type=SIT_POINT
intersection point on segment 0: Point2 (0x7fffacdccc60,-1): -38.723394, -49.220118, 0.000000
intersection point on segment 680: Point2 (0x7fffacdcccb0,-1): -38.723394, -49.220118, 0.000000
Analyzing segment no. 1:
Conflicting segment no. 771  type=SIT_POINT
intersection point on segment 1: Point2 (0x7fffacdccc60,-1): -58.600441, 53.323299, 0.000000
intersection point on segment 771: Point2 (0x7fffacdcccb0,-1): -58.600441, 53.323299, 0.000000
Conflicting segment no. 138  type=SIT_POINT
intersection point on segment 1: Point2 (0x7fffacdccc60,-1): -59.929901, 52.484158, 0.000000
intersection point on segment 138: Point2 (0x7fffacdcccb0,-1): -59.929901, 52.484158, 0.000000
Conflicting segment no. 145  type=SIT_POINT

Visualize

Create a postscript visualization.

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

Terrain Example

The below code example is similar but more practical:

  • Create ISO lines from a TIN. These are interesection free
  • Add one additional segment
  • Search all intersected segments
Terrain 2.5D

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

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.

Analyzing segment no. 11116:
Conflicting segment no. 42881  type=SIT_POINT
intersection point on segment 11116: Point2 (0x7ffed439b9c0,-1): 2393836.341463, 4569000.000000, 202.892683
intersection point on segment 42881: Point2 (0x7ffed439ba10,-1): 2393836.341463, 4569000.000000, 4711.000000
Analyzing segment no. 11117:
Conflicting segment no. 42881  type=SIT_POINT
intersection point on segment 11117: Point2 (0x7ffed439b9c0,-1): 2393844.634146, 4569000.000000, 202.892683
intersection point on segment 42881: Point2 (0x7ffed439ba10,-1): 2393844.634146, 4569000.000000, 4711.000000
Analyzing segment no. 11121:
Conflicting segment no. 42881  type=SIT_POINT
intersection point on segment 11121: Point2 (0x7ffed439b9c0,-1): 2393991.682927, 4569000.000000, 202.892683
intersection point on segment 42881: Point2 (0x7ffed439ba10,-1): 2393991.682927, 4569000.000000, 4711.000000
Analyzing segment no. 11252:
Conflicting segment no. 42881  type=SIT_POINT
intersection point on segment 11252: Point2 (0x7ffed439b9c0,-1): 2394938.105691, 4569000.000000, 202.892683
intersection point on segment 42881: Point2 (0x7ffed439ba10,-1): 2394938.105691, 4569000.000000, 4711.000000
Analyzing segment no. 14465:
Conflicting segment no. 42881  type=SIT_POINT
intersection point on segment 14465: Point2 (0x7ffed439b9c0,-1): 2392952.080139, 4569000.000000, 231.748780
intersection point on segment 42881: Point2 (0x7ffed439ba10,-1): 2392952.080139, 4569000.000000, 4711.000000
Analyzing segment no. 14493:
Conflicting segment no. 42881  type=SIT_POINT
intersection point on segment 14493: Point2 (0x7ffed439b9c0,-1): 2393509.343902, 4569000.000000, 231.748780
intersection point on segment 42881: Point2 (0x7ffed439ba10,-1): 2393509.343902, 4569000.000000, 4711.000000
Analyzing segment no. 14502:
Conflicting segment no. 42881  type=SIT_POINT
intersection point on segment 14502: Point2 (0x7ffed439b9c0,-1): 2393675.910061, 4569000.000000, 231.748780
intersection point on segment 42881: Point2 (0x7ffed439ba10,-1): 2393675.910061, 4569000.000000, 4711.000000
Analyzing segment no. 14759:
Conflicting segment no. 42881  type=SIT_POINT
intersection point on segment 14759: Point2 (0x7ffed439b9c0,-1): 2395797.573171, 4569000.000000, 231.748780
intersection point on segment 42881: Point2 (0x7ffed439ba10,-1): 2395797.573171, 4569000.000000, 4711.000000
Analyzing segment no. 18148:
Conflicting segment no. 42881  type=SIT_POINT
intersection point on segment 18148: Point2 (0x7ffed439b9c0,-1): 2392266.439024, 4569000.000000, 260.604878
intersection point on segment 42881: Point2 (0x7ffed439ba10,-1): 2392266.439024, 4569000.000000, 4711.000000
Analyzing segment no. 22858:
Conflicting segment no. 42881  type=SIT_POINT
intersection point on segment 22858: Point2 (0x7ffed439b9c0,-1): 2391922.825203, 4569000.000000, 289.460976
intersection point on segment 42881: Point2 (0x7ffed439ba10,-1): 2391922.825203, 4569000.000000, 4711.000000
Analyzing segment no. 25223:
Conflicting segment no. 42881  type=SIT_POINT
intersection point on segment 25223: Point2 (0x7ffed439b9c0,-1): 2391772.934172, 4569000.000000, 318.317073
intersection point on segment 42881: Point2 (0x7ffed439ba10,-1): 2391772.934172, 4569000.000000, 4711.000000
Analyzing segment no. 27770:
Conflicting segment no. 42881  type=SIT_POINT
intersection point on segment 27770: Point2 (0x7ffed439b9c0,-1): 2391693.243415, 4569000.000000, 347.173171
intersection point on segment 42881: Point2 (0x7ffed439ba10,-1): 2391693.243415, 4569000.000000, 4711.000000
Analyzing segment no. 29860:
Conflicting segment no. 42881  type=SIT_POINT
intersection point on segment 29860: Point2 (0x7ffed439b9c0,-1): 2391614.474255, 4569000.000000, 376.029268
intersection point on segment 42881: Point2 (0x7ffed439ba10,-1): 2391614.474255, 4569000.000000, 4711.000000
Analyzing segment no. 42881:
Conflicting segment no. 29860  type=SIT_POINT
intersection point on segment 42881: Point2 (0x7ffed439b9c0,-1): 2391614.474255, 4569000.000000, 4711.000000
intersection point on segment 29860: Point2 (0x7ffed439ba10,-1): 2391614.474255, 4569000.000000, 376.029268
Conflicting segment no. 27770  type=SIT_POINT
intersection point on segment 42881: Point2 (0x7ffed439b9c0,-1): 2391693.243415, 4569000.000000, 4711.000000
intersection point on segment 27770: Point2 (0x7ffed439ba10,-1): 2391693.243415, 4569000.000000, 347.173171
Conflicting segment no. 25223  type=SIT_POINT
intersection point on segment 42881: Point2 (0x7ffed439b9c0,-1): 2391772.934172, 4569000.000000, 4711.000000
intersection point on segment 25223: Point2 (0x7ffed439ba10,-1): 2391772.934172, 4569000.000000, 318.317073
Conflicting segment no. 22858  type=SIT_POINT
intersection point on segment 42881: Point2 (0x7ffed439b9c0,-1): 2391922.825203, 4569000.000000, 4711.000000
intersection point on segment 22858: Point2 (0x7ffed439ba10,-1): 2391922.825203, 4569000.000000, 289.460976
Conflicting segment no. 18148  type=SIT_POINT
intersection point on segment 42881: Point2 (0x7ffed439b9c0,-1): 2392266.439024, 4569000.000000, 4711.000000
intersection point on segment 18148: Point2 (0x7ffed439ba10,-1): 2392266.439024, 4569000.000000, 260.604878
Conflicting segment no. 14465  type=SIT_POINT
intersection point on segment 42881: Point2 (0x7ffed439b9c0,-1): 2392952.080139, 4569000.000000, 4711.000000
intersection point on segment 14465: Point2 (0x7ffed439ba10,-1): 2392952.080139, 4569000.000000, 231.748780
Conflicting segment no. 14759  type=SIT_POINT
intersection point on segment 42881: Point2 (0x7ffed439b9c0,-1): 2395797.573171, 4569000.000000, 4711.000000
intersection point on segment 14759: Point2 (0x7ffed439ba10,-1): 2395797.573171, 4569000.000000, 231.748780
Conflicting segment no. 14493  type=SIT_POINT
intersection point on segment 42881: Point2 (0x7ffed439b9c0,-1): 2393509.343902, 4569000.000000, 4711.000000
intersection point on segment 14493: Point2 (0x7ffed439ba10,-1): 2393509.343902, 4569000.000000, 231.748780
Conflicting segment no. 11117  type=SIT_POINT
intersection point on segment 42881: Point2 (0x7ffed439b9c0,-1): 2393844.634146, 4569000.000000, 4711.000000
intersection point on segment 11117: Point2 (0x7ffed439ba10,-1): 2393844.634146, 4569000.000000, 202.892683
Conflicting segment no. 11116  type=SIT_POINT
intersection point on segment 42881: Point2 (0x7ffed439b9c0,-1): 2393836.341463, 4569000.000000, 4711.000000
intersection point on segment 11116: Point2 (0x7ffed439ba10,-1): 2393836.341463, 4569000.000000, 202.892683
Conflicting segment no. 14502  type=SIT_POINT
intersection point on segment 42881: Point2 (0x7ffed439b9c0,-1): 2393675.910061, 4569000.000000, 4711.000000
intersection point on segment 14502: Point2 (0x7ffed439ba10,-1): 2393675.910061, 4569000.000000, 231.748780
Conflicting segment no. 11121  type=SIT_POINT
intersection point on segment 42881: Point2 (0x7ffed439b9c0,-1): 2393991.682927, 4569000.000000, 4711.000000
intersection point on segment 11121: Point2 (0x7ffed439ba10,-1): 2393991.682927, 4569000.000000, 202.892683
Conflicting segment no. 11252  type=SIT_POINT
intersection point on segment 42881: Point2 (0x7ffed439b9c0,-1): 2394938.105691, 4569000.000000, 4711.000000
intersection point on segment 11252: Point2 (0x7ffed439ba10,-1): 2394938.105691, 4569000.000000, 202.892683

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

Illegal segment intersections

Intersecting segments (red), intersection points (blue)

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

Spread the word. Share this post!

Leave A Reply

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

*

By continuing to use the site, you agree to the use of cookies. more information

The cookie settings on this website are set to "allow cookies" to give you the best browsing experience possible. If you continue to use this website without changing your cookie settings or you click "Accept" below then you are consenting to this.

Close