实现 Bentley-Ottmann 算法

Question

我在C#中正确实现Bentley-Ottmann算法遇到了一些问题。我正在尝试按照这里的伪代码实现它。我在下面发布了我的主要代码。假设我的BST和PriorityQueue类已经正确实现，你能看到代码中的任何问题吗？

虽然没有错误，但是并没有找到所有的交点，只有一些。我猜测代码中else部分（当前事件为交点时）存在错误。我不确定伪代码中交换BST中两个线段位置的含义。我这样做可以吗？因为最终，两者在BST中并没有真正交换位置。我也不能仅仅改变它们的位置，因为那可能会破坏BST的属性。

另外，我是否正确地认为，在BST中，线段按其左端点的Y坐标排序？

我还注意到另一个无法跟踪的错误是有时点(0, 0)会进入eventList。如果没有交点，则Geometry.Intersects会输出(0, 0)，但在这种情况下，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, 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);
            }
        }
    }
}

- IVlad

Answer 1

如果没有一些关于其他类究竟是做什么的想法，我真的无法理解你的代码，但我可以回答你的其他问题。

BST中的段按其与扫描线相交的Y坐标排序。因此，当我们遇到左端点时，我们使用进入段左端点的y坐标（将其与另一个段与扫描线的交点的Y坐标进行比较）将该段添加到树中。当我们遇到右端点时，我们从树中删除该段。当我们遇到交点时，两个段与扫描线的交点的顺序会发生变化，因此我们在树中交换这两个段。例如，考虑两个段

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

当扫描线的X坐标小于0时，线段A与扫描线的交点大于线段B与扫描线的交点。如果扫描线大于0，则相反。 （画个图吧）

可能有助于绘制一个简单的示例，并逐步跟踪正在发生的事情，为每个事件绘制扫描线并在事件之间的列中标记段，然后跟踪BST并验证BST在其有效区域内保持与段相同的顺序。（如果不够清晰，请见谅。）

注意：这假定您的线段处于“一般位置”，即没有线段是垂直的，在给定点不超过两条线段相交等。处理不在一般位置的线段在wikipedia page上有概述。

- deinst