Implementing the Bentley-Ottmann algorithm

Question

I am having some trouble correctly implementing the Bentley-Ottmann algorithm in C#. I am trying to implement it according to the pseudocode here. I have posted my main code below. Assuming my BST and PriorityQueue classes are implemented correctly, do you see any problems with the code?

There are no errors, but not all intersection points are found, only some. My guess is that there's an error in the else part of the code (when the current event is an intersection point). I'm not sure what the pseudocode means by swapping the position of two segments in the BST. Is the way I do it fine? Because in the end, the two aren't really swapped in the BST. I can't just change their positions either, because that could break the BST properties.

Also, am I right in assuming that segments are ordered in the BST by the Y-coordinate of their left endpoint?

Another error I've noticed that I can't seem to be able to track down is that sometimes the point (0, 0) gets into eventList. (0, 0) is outputted by Geometry.Intersects in case there is no intersection, but in that case the if conditions should stop it from getting added. I have no idea how it gets in. If I print the contents of eventList after adding a point in, (0, 0) never shows up. If I print the contents after extracting and popping an element, (0, 0) sometimes shows up. Could this have anything to do with the Pop() method messing with the references, or is it definitely a problem in my PriorityQueue implementation?

If needed I can show my implementations for the BST and priority queue as well.

static class BentleyOttman
{
    private static void AddIntersectionEvent(PriorityQueue eventList, Segment segEv, Segment segA, SegPoint i)
    {
        i.IntersectingSegments = new Tuple<Segment, Segment>(segEv, segA);
        i.Type = SegmentPointType.IntersectionPoint;

        eventList.Add(i);
    }

    public static void Solve(Panel surface, TextBox debug)
    {
        debug.Clear();
        var segList = Generator.SegList;

        PriorityQueue eventList = new PriorityQueue();

        foreach (Segment s in segList)
        {
            eventList.Add(new SegPoint(s.A, s, SegmentPointType.LeftEndpoint));
            eventList.Add(new SegPoint(s.B, s, SegmentPointType.RightEndpoint));
        }

        BST sweepLine = new BST();
        while (!eventList.Empty)
        {
            SegPoint ev = eventList.Top();

            eventList.Pop();

            if (ev.Type == SegmentPointType.LeftEndpoint)
            {
                Segment segEv = ev.Segment;
                sweepLine.Insert(segEv);

                Segment segA = sweepLine.InorderPre(segEv);
                Segment segB = sweepLine.InorderSuc(segEv);

                SegPoint i = new SegPoint();
                if (segA != null && Geometry.Intersects(segEv, segA, out i.Point))
                {
                    AddIntersectionEvent(eventList, segA, segEv, i);
                }
                if (segB != null && Geometry.Intersects(segEv, segB, out i.Point))
                {
                    AddIntersectionEvent(eventList, segEv, segB, i);
                }
            }
            else if (ev.Type == SegmentPointType.RightEndpoint)
            {
                Segment segEv = ev.Segment;

                Segment segA = sweepLine.InorderPre(segEv);
                Segment segB = sweepLine.InorderSuc(segEv);

                sweepLine.Remove(segEv);

                SegPoint i = new SegPoint();
                if (segA != null && segB != null && Geometry.Intersects(segA, segB, out i.Point))
                {
                    AddIntersectionEvent(eventList, segA, segB, i);
                }
            }
            else
            {
                Generator.DrawPoint(ev.Point, surface, Brushes.Red);

                Segment seg1 = ev.IntersectingSegments.Item1;
                Segment seg2 = ev.IntersectingSegments.Item2;

                sweepLine.Remove(seg1);
                sweepLine.Remove(seg2);

                Segment t = new Segment(seg1);
                seg1 = new Segment(seg2);
                seg2 = new Segment(t);

                sweepLine.Insert(seg1);
                sweepLine.Insert(seg2);

                Segment segA = sweepLine.InorderPre(seg2);
                Segment segB = sweepLine.InorderSuc(seg1);

                SegPoint i = new SegPoint();
                if (segA != null && Geometry.Intersects(seg2, segA, out i.Point))
                    AddIntersectionEvent(eventList, segA, seg2, i);
                if (segB != null && Geometry.Intersects(seg1, segB, out i.Point))
                    AddIntersectionEvent(eventList, seg1, segB, i);
            }
        }
    }
}

Answer 1

I really cannot understand your code without some idea of what exactly the other classes do, but I can answer some of your other questions.

The segments are ordered in the BST by the Y coordinate of their intersection with the sweep line. So when we encounter a left endpoint we add the segment to the tree using the y coordinate of the left endpoint of the entering segment (comparing it with the Y coordinate of the intersection of the other segment with the sweep line). When we encounter a right endpoint we remove the segment from the tree. When we encounter an intersection, then the order of the intersections of the two segments with the sweep line switches, so we swap the two segments in the tree. For example consider the two segments

 A = {(-1,1),(1,-1)} and
 B = {(-1,-1),(1,1)}

When the X coordinate of the sweep line is less than 0 then the intersection of segment A with the sweep line is greater than the intersection of segment B with the sweep line. and if the sweep line is greater than 0 the reverse is true. (Draw a picture.)

It is probably instructive to draw a simple example, and trace what is going on step by step, drawing the sweep line for each event and labeling the segments in columns between the events, then keeping track of the BST and verifying that the BST keeps the same order as the segments in the region where it is valid. (I'm sorry if that is not as clear as it could be.)

Note: This assumes that your segments are in "general position", i.e. that no segment is vertical, no more than two segments intersect at a given point, etc. Dealing with segments not in general position is outlined on the wikipedia page