Can't get all intersections with Bentley Ottmann implementation

Question

I have writen a program in Processing to implement the Bentley-Ottmann algorithm for the line segment intersection problem.

The program returns a set of points but it does not find all the intersections. Can anyone tell me please what have I done wrong?

An ArrayList holds the active line segments that intersect the sweep line.
For each endpoint I store its x position and the Line2D it belongs to, at an TreeMap(Double, List(Line2D)) structure.
I am holding a List of Lines2D (TreeMap(Double, List(Line2D) ) because if I find an intersection I report its x position and the two lines that intersect.

I think I followed all the steps required by the algorithm. I've studied from the "Computational Geometry - Algorithms and Applications", and also a pdf named "Computing intersections in a set of line segments: the Bentley-Ottmann algorithm" from Michiel Smid.

Although, I am not taking into account the restrictions about the vertical lines, intersection with three segments etc. most of the times the requirements are met but still the results are not the expected ones.

This is an example

This is my code

import java.util.*;
import java.awt.*;
import java.awt.geom.*;
import java.util.List;
import java.util.concurrent.TimeUnit;

Algorithm algorithm = new Algorithm();
List<Line2D> initialList = new ArrayList<Line2D>();
List<Double> xStructure = new ArrayList<Double>();
Set<Point2D> intersections = new HashSet<Point2D>();

void setup() {
  size(640, 480);
  initialList = algorithm.createListOfRandomLines(5);
  long start = System.currentTimeMillis();
  intersections = algorithm.runBentleyOttmann(initialList);
  long stop = System.currentTimeMillis() - start;
  System.out.println(String.format("Execution Time: %f sec", (float)TimeUnit.MILLISECONDS.toSeconds(stop)));
}

void draw() {
  background(255);
  strokeWeight(1);
  stroke(0);
  for(Line2D l : initialList)
    line((float)l.getX1(), (float)l.getY1(), (float)l.getX2(), (float)l.getY2());
  strokeWeight(5);
  stroke(255,0,0);
  for(Point2D p : intersections)
    point((float)p.getX(), (float)p.getY());
}

class Algorithm {    
  TreeMap<Double, List<Line2D>> xStructure;  
  Double slPosition;
  List<Line2D> slStatus; // Y-structure
  Set<Point2D> intersectionPoints;

  public Algorithm() {
    intersectionPoints = new HashSet<Point2D>();
    slPosition = Double.MIN_VALUE;
    slStatus = new ArrayList<Line2D>();
    xStructure = new TreeMap<Double, List<Line2D>>();
  }

  public Set<Point2D> runBentleyOttmann(List<Line2D> list) {
    //System.out.println("DEBUG INFO: runBentleyOttmann got input a list of " + list.size() + " line segments.");
    xStructure = createMapOfSortedEndpointsAndCorespondingLineSegment(list);
    //System.out.println("DEBUG INFO: runBentleyOttmann x-structure now contains the " + xStructure.size() + "  endpoints.");
    //System.out.println("DEBUG INTO: runBentleyOttmann sweep line is at position " + slPosition);
    //System.out.println("DEBUG INFO: runBentleyOttmann begins while loop");
    while (!xStructure.isEmpty()) {      
      Map.Entry<Double, List<Line2D>> entry = xStructure.pollFirstEntry();
      Double min = entry.getKey();
      slPosition = min;
      List<Line2D> lines = entry.getValue();
      //System.out.println("-----DEBUG INFO: runBentleyOttmann let min be the minimum element of x-structure " + min);      
      //System.out.println("-----DEBUG INFO: runBentleyOttmann delete min from the x-structure");
      //System.out.println("-----DEBUG INFO: runBentleyOttmann checks endpoint type");
      if (checkEndpointType(lines) == EndpointType.LEFT) {
        //System.out.println("----------DEBUG INFO: Endpoint Type LEFT");
        handleLeftEndpoint(lines);        
      }
      else if (checkEndpointType(lines) == EndpointType.RIGHT) {
        //System.out.println("----------DEBUG INFO: Endpoint Type RIGHT");        
        handleRightEndpoint(lines);
      }
      else if (checkEndpointType(lines) == EndpointType.INTERSECTION) {
        //System.out.println("----------DEBUG INFO: Endpoint Type INTERSECTION");
        handleIntersectionEndpoint(lines);
      }
    }
    //System.out.println("DEBUG INFO: runBentleyOttmann ends while loop");
    return intersectionPoints;
  }

  public void handleIntersectionEndpoint(List<Line2D> lines) {
    Line2D l1 = slStatus.get(slStatus.indexOf(lines.get(0)));
    Line2D l2 = slStatus.get(slStatus.indexOf(lines.get(1)));
    if (slStatus.indexOf(l1) > slStatus.indexOf(l2)) {
      Line2D ltemp = slStatus.get(slStatus.indexOf(lines.get(0)));
      l1 = l2;
      l2 = ltemp;
    }
    Line2D prev;
    Line2D next;
    if (slStatus.indexOf(l1) > 0) {
      prev = getAboveLine(l1);
      if (prev != null)
        if (l2.intersectsLine(prev)) {
          Point2D ip = findIntersectionPoint(l2, prev);
          if (ip.getX() > slPosition) {
            intersectionPoints.add(findIntersectionPoint(l2, prev));
            List<Line2D> tempList = new ArrayList<Line2D>();
            tempList.add(l2);
            tempList.add(prev);
            xStructure.put(ip.getX(), tempList);
          }
        }
    } 
    if (slStatus.indexOf(l2) < slStatus.size()-1) {
      next = getBelowLine(l2);
      if (next != null)
        if (l1.intersectsLine(next)) {
          Point2D ip = findIntersectionPoint(l1, next);
          if (ip.getX() > slPosition) {
            intersectionPoints.add(findIntersectionPoint(l1, next));
            List<Line2D> tempList = new ArrayList<Line2D>();
            tempList.add(l1);
            tempList.add(next);
            xStructure.put(ip.getX(), tempList);
          }
        }
    }
    System.out.println(slStatus.indexOf(l1) + " " + slStatus.indexOf(l2));
  }

  public void handleLeftEndpoint(List<Line2D> lines) {
    //System.out.println("HANDLE LEFT ENDPOINT started");
    slStatus.add(lines.get(0));
    //System.out.println("Line [X1=" + lines.get(0).getX1() + ", Y1=" + lines.get(0).getY1() + ", X2=" + lines.get(0).getX2() + ", Y2=" + lines.get(0).getY2() + "] added to Y-Structure.");
    Collections.sort(slStatus, new YComparator());
    //System.out.println("Y-Structure is sorted by Y endpoint");
    Line2D above = getAboveLine(lines.get(0));
    if (above != null)
      if (lines.get(0).intersectsLine(above)) {
        Point2D ip = findIntersectionPoint(lines.get(0), above);
        if (ip.getX() > slPosition) {
          intersectionPoints.add(findIntersectionPoint(lines.get(0), above));
          List<Line2D> tempList = new ArrayList<Line2D>();
          tempList.add(lines.get(0));
          tempList.add(above);
          xStructure.put(ip.getX(), tempList);
        }
      }
    Line2D below = getBelowLine(lines.get(0));
    if (below != null)
      if (lines.get(0).intersectsLine(below)) {
        Point2D ip = findIntersectionPoint(lines.get(0), below);
          if (ip.getX() > slPosition) {
            intersectionPoints.add(findIntersectionPoint(lines.get(0), below));
            List<Line2D> tempList = new ArrayList<Line2D>();
            tempList.add(lines.get(0));
            tempList.add(below);
            xStructure.put(ip.getX(), tempList);
          }
      }
    //System.out.println("HANDLE LEFT ENDPOINT finished");    
  }

  public void handleRightEndpoint(List<Line2D> lines) {
    //System.out.println("HANDLE RIGHT ENDPOINT started");
    Line2D above = getAboveLine(lines.get(0));
    Line2D below = getBelowLine(lines.get(0));
    if (above != null && below != null)    
      if (above.intersectsLine(below)){
        Point2D ip = findIntersectionPoint(lines.get(0), below);
        if (ip.getX() > slPosition)
          intersectionPoints.add(findIntersectionPoint(lines.get(0), below));
      }
    slStatus.remove(lines.get(0));
    //System.out.println("Line [X1=" + lines.get(0).getX1() + ", Y1=" + lines.get(0).getY1() + ", X2=" + lines.get(0).getX2() + ", Y2=" + lines.get(0).getY2() + "] deleted from Y-Structure.");
  }

  public Line2D getAboveLine(Line2D line) {
    if (slStatus.indexOf(line) > 0) {
      Line2D a = slStatus.get(slStatus.indexOf(line)-1);
      //System.out.println("getAboveLine returns line [X1=" + a.getX1() + ", Y1=" + a.getY1() + ", X2=" + a.getX2() + ", Y2=" + a.getY2() + "]");
      return a;
    }
    //System.out.println("getAboveLine returns no line");
    return null;
  }

  public Line2D getBelowLine(Line2D line) {
    if (slStatus.indexOf(line) < slStatus.size()-1) {
      Line2D b = slStatus.get(slStatus.indexOf(line)+1);
      //System.out.println("getBelowLine returns line [X1=" + b.getX1() + ", Y1=" + b.getY1() + ", X2=" + b.getX2() + ", Y2=" + b.getY2() + "]");
      //System.out.println("getAboveLine returns no line");
      return b;
    }
    return null;
  }

  public EndpointType checkEndpointType(List<Line2D> lines) {
    if (lines.size() == 2)
      return EndpointType.INTERSECTION;
    if (slStatus.contains(lines.get(0)))
      return EndpointType.RIGHT;
    if (!slStatus.contains(lines.get(0)))
      return EndpointType.LEFT;  
    return null;
  }

  public List<Line2D> sortEndpointsByXCoordinate(List<Line2D> inputList) {
    List<Line2D> returnList = new ArrayList(inputList);
    Collections.sort(returnList, new XComparator());
    return returnList;
  }

  public TreeMap<Double, List<Line2D>> createMapOfSortedEndpointsAndCorespondingLineSegment(List<Line2D> inputList) {
    TreeMap returnTreeMap = new TreeMap<Double, Line2D>();
    for (Line2D l : inputList) {
      List<Line2D> tempList = new ArrayList<Line2D>();
      tempList.add(l);
      returnTreeMap.put(l.getX1(), tempList);      
      returnTreeMap.put(l.getX2(), tempList);
    }
    return returnTreeMap;
  }

  public List<Double> createListOfSortedEndpoints(List<Line2D> inputList) {
    List<Double> returnList = new ArrayList<Double>();
    for (Line2D l : inputList) {
      returnList.add(l.getBounds().getX());
      returnList.add(l.getBounds().getY());
    }
    Collections.sort(returnList);
    //System.out.println("DEBUG INFO: createListOfSortedEndpoints returns " + returnList.size() + " endpoints");
    return returnList;
  }

  public List<Line2D> createListOfRandomLines(int size) {
    Set<Line2D> hashset = new HashSet<Line2D>();

    Random random = new Random();

    while (hashset.size() != size) {
      Line2D line = new Line2D.Double();
      line.setLine(random.nextInt(width-1)+1, random.nextInt(height-1)+1, random.nextInt(width-1)+1, random.nextInt(height-1)+1);
      hashset.add(line);
    }

    List<Line2D> returnList = new ArrayList(hashset);  

    return returnList;
  }

  public Point2D findIntersectionPoint(Line2D l1, Line2D l2) {
    Double p0_x = l1.getX1();
    Double p0_y = l1.getY1();
    Double p1_x = l1.getX2();
    Double p1_y = l1.getY2();
    Double p2_x = l2.getX1();
    Double p2_y = l2.getY1();
    Double p3_x = l2.getX2();
    Double p3_y = l2.getY2();
    Double s1_x = p1_x - p0_x;
    Double s1_y = p1_y - p0_y;
    Double s2_x = p3_x - p2_x;
    Double s2_y = p3_y - p2_y;
    Double s, t;
    s = (-s1_y * (p0_x - p2_x) + s1_x * (p0_y - p2_y)) / (-s2_x * s1_y + s1_x * s2_y);
    t = ( s2_x * (p0_y - p2_y) - s2_y * (p0_x - p2_x)) / (-s2_x * s1_y + s1_x * s2_y);
    Double i_x, i_y;
    i_x = p0_x + (t * s1_x);
    i_y = p0_y + (t * s1_y);
    Point2D p = new Point2D.Double(i_x, i_y);
    return p;
  }
}

class XComparator implements Comparator<Line2D>{
  public int compare(Line2D l1, Line2D l2){
    return new Double(l1.getBounds().getX()).compareTo(l2.getBounds().getX());
  }
}

class YComparator implements Comparator<Line2D>{
  public int compare(Line2D l1, Line2D l2){
    return new Double(l1.getBounds().getY()).compareTo(l2.getBounds().getY());
  }
}

enum EndpointType {
  LEFT, RIGHT, INTERSECTION
};

Just a thought: floating-point equality tests are a notorious source of bugs, and by making the key type of your TreeMap an FP type, every insertion and lookup implicitly needs (at least) one such comparison. See if multiplying all co-ords by a suitably large number and using integers instead makes the problem goes away. — j_random_hacker
You're going to have to debug your code. Have you tried running through a debugger or adding some print statements to figure out exactly what's going on? Have you narrowed it down to a hard-coded example that just uses two lines that should intersect but aren't detected? Where exactly does the code's execution differ from what you expect? Try to narrow it down to as few lines as possible. This is a lot of code to ask us to debug for you. — Kevin Workman

Stanislav Antonov Stanislav Antonov · Accepted Answer · 2020-01-17T23:27:34

I would recommend considering the following Java implementation: https://github.com/stanislav-antonov/bentley-ottmann

It's clean and minimalistic enough, but still handles all the major edge cases.

Can't get all intersections with Bentley Ottmann implementation

1 Answers