Реализация алгоритма Бентли-Оттмана

Question

У меня возникли проблемы с правильной реализацией алгоритма Бентли-Оттмана в 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);
            }
        }
    }
}

Answer 1

Я действительно не могу понять ваш код, не имея представления о том, что именно делают другие классы, но я могу ответить на некоторые другие ваши вопросы.

Сегменты упорядочены в BST по координате Y их пересечения с линией развертки. Поэтому, когда мы встречаем левую конечную точку, мы добавляем сегмент в дерево, используя координату y левой конечной точки входящего сегмента (сравнивая ее с координатой Y пересечения другого сегмента с линией развертки). Когда мы сталкиваемся с правильной конечной точкой, мы удаляем сегмент из дерева. Когда мы сталкиваемся с пересечением, то порядок пересечений двух сегментов с линией развертки переключается, поэтому мы меняем местами два сегмента в дереве. Например, рассмотрим два сегмента

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

Если координата X линии развертки меньше 0, то пересечение сегмента A с линией развертки больше, чем пересечение сегмента B с линией развертки. и если линия развертки больше 0, обратное верно. (Нарисуйте картинку.)

Вероятно, поучительно нарисовать простой пример и проследить, что происходит, шаг за шагом, рисуя линию развертки для каждого события и маркируя сегменты в столбцах между событиями, затем отслеживая BST и проверяя, что BST сохраняет тот же порядок, что и сегменты в регионе, где он действителен. (Извините, если это не так ясно, как могло бы быть.)

Примечание: это предполагает, что ваши сегменты находятся в «общем положении», то есть ни один сегмент не является вертикальным, не более двух сегментов пересекаются в данной точке и т. Д. Работа с сегментами, не находящимися в общем положении, описана на страница википедии