c# – 实现Bentley-Ottmann算法

没有错误,但并非找到所有交叉点,只有一些.我的猜测是代码的else部分存在错误(当前事件是交叉点时).我不确定伪代码是什么意思通过交换BST中两个段的位置.我这样做的方式好吗？因为最后,两者在BST中并没有真正交换.我也不能改变他们的立场,因为这可能打破BST属性.

另外,我是否正确假设段在BST中按其左端点的Y坐标排序？

我注意到我似乎无法追踪的另一个错误是有时点(0,0)进入eventList. (0,0)由Geometry.Intersects输出,以防没有交集,但在这种情况下,if条件应该阻止它被添加.我不知道它是如何进入的.如果我在添加一个点之后打印eventList的内容,(0,0)永远不会显示.如果我在提取并弹出元素后打印内容,有时会显示(0,0).这可能与Pop()方法搞乱引用有关,还是我的PriorityQueue实现中肯定是一个问题？

如果需要,我也可以显示我的BST和优先级队列的实现.

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,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,segEv,i);
                }
                if (segB != null && Geometry.Intersects(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,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,out i.Point))
                    AddIntersectionEvent(eventList,seg2,i);
                if (segB != null && Geometry.Intersects(seg1,seg1,i);
            }
        }
    }
}