c# - 实现 Bentley-Ottmann 算法

Question

我在用 C# 正确实现 Bentley-Ottmann 算法时遇到了一些问题。我正在尝试根据伪代码 here 来实现它.我在下面发布了我的主要代码。假设我的 BST 和 PriorityQueue 类实现正确，您是否发现代码有任何问题？

没有错误，但不是所有的交点都找到了，只有一些。我的猜测是代码的 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, 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

如果不了解其他类的确切功能，我真的无法理解您的代码，但我可以回答您的其他一些问题。

线段在 BST 中按其与扫掠线相交的 Y 坐标排序。因此，当我们遇到左端点时，我们使用进入线段左端点的 y 坐标将线段添加到树中(将其与另一线段与扫掠线相交的 Y 坐标进行比较)。当我们遇到右端点时，我们从树中删除该段。当我们遇到一个交叉点时，这两个线段的交点顺序与扫描线交换，所以我们交换树中的两个线段。例如考虑两个部分

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

当扫描线的 X 坐标小于 0 时，线段 A 与扫描线的交点大于线段 B 与扫描线的交点。如果扫描线大于 0，则相反。 (画一幅画。)

画一个简单的例子，一步一步地跟踪发生的事情，画出每个事件的扫描线，并在事件之间的列中标记段，然后跟踪 BST 并验证BST 与其有效区域中的段保持相同的顺序。 (很抱歉，如果这不是很清楚。)

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