я возникли проблемы с правильной реализацией алгоритма Бентли-Оттмана в C #. Я пытаюсь реализовать это в соответствии с псевдокодомВот, Я разместил свой основной код ниже. Предполагая мой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);
            }
        }
    }
}