Динамическое добавление ребер в граф DCEL / полугол?

Question

Я пытаюсь реализовать систему «черчения» векторной графики, где пользователи могут рисовать линии на экране и взаимодействовать с областями, созданными пересекающимися линиями.Я пытаюсь определить / оценить, что это за области.

Я пробовал несколько разных решений этой проблемы, в основном, ведя список ребер и запуская BFS, чтобы найти кратчайшие циклы, но это привело кМножество проблем, в которых BFS будет сокращаться нелегальными способами, а дырки и вырожденные ребра вызывали больше проблем, чем я мог сосчитать, поэтому я перешел к DCEL, системе полуголовых ребер.

Я читал, казалось бы,все, что я могу по этой теме, включая две статьи, на которые часто ссылаются здесь: http://kaba.hilvi.org/homepage/blog/halfedge/halfedge.htm и http://www.flipcode.com/archives/The_Half-Edge_Data_Structure.shtml. Однако ни одна из них, кажется, не отвечает на эту проблему, которая возникает у меня, когда дело доходит до динамического добавления ребер вgraph.

Допустим, я начинаю с этого единственного ребра. Изображение

Пол ребра соединяются друг с другом в цикле, а глобальная неограниченная «внешняя грань» соединяется с одним из пол ребер.Это просто.

Затем мы добавляем еще одно ребро, прикрепленное к центральной вершине: Изображение

Новые пол ребра работают нормально, и мы обновляем ребра, которыевпадайте в следующие указатели v1, чтобы быть единственными доступными ребрами, которые не являются их близнецами.Опять же, это имеет смысл для меня.

Что меня смущает, так это то, что происходит здесь, когда мы добавляем третий край к центральной вершине: Изображение

Я знаюэто то, что предполагается , чтобы быть похожим и связать, чтобы быть, но я так изумлен, как достичь этого программно, потому что я не уверен, как я могу определить, должен ли край (4,1)указать на ребро (1,2) или ребро (1,3) (аналогично тому, какое ребро должно указывать на (1,4)).

Ответ кажется очевидным при взгляде на изображение, но когда вы пытаетесь рационализировать его надежным, герметичным алгоритмическим способом, мой мозг тает, и я не могу понять это.Учебник, который я читаю (Вычислительная геометрия, Марк де Берг и др., Стр. 35), просто говорит

"[чтобы проверить, где ребро] должно быть в циклическом порядке ребер вокругвершина v ".

Алгоритм, приведенный в статье hilvi.org для поиска исходящих и входящих ребер, с которыми нужно связать, даже не работает, так как он будет принимать вершину 1 и следовать за близнецом своего исходящего ребрапока он не найдет «свободный» край, который в данном случае равен (2,1), что неверно.(Если я не понимаю это неправильно, я мог бы понять всю эту проблему неправильно.)

Так что я совершенно ошеломлен.Моя единственная идея сейчас состоит в том, чтобы создать какой-либо атрибут заголовка для каждой половины ребра, где я измеряю угол, созданный ребром, и выбираю ребра таким образом, и, возможно, это правильно, но это не так, как в структуре пол ребракажется, поддерживает, по крайней мере, в статьях, которые я читаю об этом, кажется, ничто не упоминает ничего подобного.Любая помощь будет принята с благодарностью.Я был над этой проблемой уже больше недели и просто не могу оторваться.

Answer 1

Правильно, поэтому я потратил много времени на обдумывание этой проблемы, и, честно говоря, я немного удивлен, что не могу найти прямой ответ на этот вопрос.Таким образом, на случай, если кто-нибудь в будущем столкнется с аналогичной проблемой, связанной с желанием заполнить полукруглый граф с нуля, вот решение, которое работает.У меня нет блога, поэтому я пишу его здесь.

Я понятия не имею, является ли это ответом best , но он работает за линейное время и кажется мне простым.

Я буду иметь дело со следующими объектами / классами, которые немного отличаются от обычного DCEL:

class Vertex {
    x;
    y;

    edges = []; //A list of all Half Edges with their origin at this vertex.
                //Technically speaking this could be calculated as needed, 
                  and you could just keep a single outgoing edge, but I'm not 
                  in crucial need of space in my application so I'm just 
                  using an array of all of them.
}


class HalfEdge {
    origin; //The Vertex which this half-edge emanates from

    twin; // The half-edge pair to this half-edge

    face; // The region/face this half-edge is incident to

    next; // The half-edge that this half-edge points to
    prev; // The half-edge that points to this half-edge

    angle; //The number of degrees this hedge is CW from the segment (0, 0) -> (inf, 0)
}


class Face {
    outer_edge; //An arbitrary half-edge on the outer boundary defining this face.
    inner_edges = []; //A collection of arbitrary half-edges, each defining
                      //A hole in the face.

    global; //A boolean describing if the face is the global face or not.
            //This could also be done by having a single "global face" Face instance. 
            //This is simply how I did it.
}

Для инициализации вершины в (x, y):

1. Убедитесь, что вершины с заданными (x, y) координатами еще не существует.Если это так, вам не нужно ничего делать (за исключением, может быть, возврата этой существующей вершины, если вы используете ее немедленно).

2. Если это не так, выделите место для исоздайте новую вершину с соответствующими значениями x, y и с ее нулевым ребром.

Для инициализации ребра от вершины A до вершины B:

1. Подобно многим статьям на эту тему, мы создаем два новых экземпляра HalfEdge, один из вершин A в B, один из B в A. Они связаны друг с другом в том, что мы устанавливаем их близнецы, prev иДалее все указатели на другую половину (изгородь).

2. Мы также устанавливаем угол изгороди.Угол рассчитывается по часовой стрелке от положительной оси х.Я реализовал функцию ниже.Это супер важно для правильной работы этой структуры данных, и тот факт, что я не прочитал что-либо в литературе об этой важности, заставляет меня думать, что должно быть лучшеКстати, но я отвлекся.

       setAngle(){
           const dx = this.destination().x - this.origin.x;
           const dy = this.destination().y - this.origin.y;
   
           const l = Math.sqrt(dx * dx + dy * dy);
           if (dy > 0) {
               this.angle = toDeg(Math.acos(dx / l));
           } else {
               this.angle = toDeg(Math.PI * 2 - Math.acos(dx / l));
           }
   
            function toDeg(rads) {
                return 180 * rads / Math.PI;
            }
   
        }
   

3. Далее мы соединяем вершины с их новыми ребрами, добавляя их в список ребер их вершин, а затем сортируем список ребер по хеджу.Углы от наименьшего (0) к наибольшему (359).

4. Затем , и это важный шаг , чтобы правильно связать все, мы берем ближайшийхеджирование с новым хеджированием, которое мы пытаемся связать в порядке CCW.По сути, везде, где наш новый хедж попадает в список краев, это index - 1 (если index = 0, мы возвращаем edges[edges.length - 1]).Возьмите двойника этого края, и он станет нашим AIn, описанным в статье выше.BOut = AIn.next.

5. Устанавливаем AIn.next = hedgeAB и аналогично hedgeAB.prev = AIn, затем hedgeBA.next = AOut, AOut.prev = hedgeBA.Выполните шаги 3-5 для hedgeBA, кроме запуска поиска CCW для вершины B.

6. Затем, если обе вершины A и B были "старыми" вершинами, то есть их списки ребертеперь по крайней мере 2 элемента каждый, новая грань имеет потенциально добавлено, и мы должны найти его (в случае с краями имеется два изолированных ребра и их соединение для создания неограниченной формы ведра или крышки)

Для инициализации грани:

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

2. Для этого мы получаем список всех хеджей на графике.Неважно, как вы это делаете, я решил сохранить массив каждого хеджа, который каждый раз передавал в функцию поиска цикла.

3. Затем мы просматриваем этот списокпока список не пуст, мы берем первый элемент и запускаем его цикл, удаляя все хеджи, которые мы находим по пути из списка, и добавляя его в новый цикл, который мы добавляем в другой список

4. С этим новым списком циклов нам нужно определить, является ли цикл внутренним / внешним циклом. Есть много способов сделать это, и упомянутая выше книга по вычислительной геометрии имеет большой раздел об этом. Тот, который я использовал, чтобы вычислить площадь, определенную каждым циклом. Если область> = 0, цикл определяется «внутренними» изгородями. В противном случае он определяется внешними хеджами.

5. Последний шаг - установить все записи лиц, опять же, вышеупомянутый учебник содержит много подробностей об этом, но основная идея состоит в том, чтобы создать виртуальный «график» этих циклов и соединить внешние циклы (которые являются отверстиями в гранях), их соответствующие внутренние циклы, которые являются внешними границами граней. Для этого вы смотрите на крайнюю левую вершину цикла и бесконечно расширяете луч влево, и «соединяете» цикл с первой обращенной вниз изгородью цикла, в которую попадает луч (я оставлю реализацию вверх для вас, я понятия не имею, является ли мой путь лучшим, короче говоря, я проверял каждый цикл с самой левой вершиной слева от текущего цикла и вычислял самое правое пересечение со значением y самой левой вершины текущего цикла, а затем проверил, если это было вниз).

6. С этим графиком циклов запускайте BFS / DFS, начиная с каждого цикла "внутри хеджа" (не отверстий), и создайте грань с произвольным изгородью из цикла внутреннего хеджа в качестве внешнего края , (или ноль, если это глобальная грань) и произвольное хеджирование от каждого найденного цикла отверстия до внутренних компонентов грани.

Привет, вот так. Если вы проверяете все каждый раз, это обрабатывает все. Он обрабатывает расщепление лица как очарование и очень прочный и быстрый. Я не знаю, правильно ли это , но оно работает.