3622
правки
Изменения
→Особенности реализации и другие частные случаи
[[Файл:skeleton_complex_event_example.jpg]]
===== Параллельные противоположные рёбра =====
С точками <tex> c </tex> и <tex> d </tex> разбираться необходимо следующим образом: как только параллельные рёбра становятся соседними перед событием, нужно проверить, что они соединятся потом в одно ребро после произошедшего события. Если в <tex> \mathrm{LAV} </tex> осталось только два параллельных ребра, то мы удаляем их из <tex> \mathrm{SLAV} </tex>.
Ещё примеры не для слабонервных.
[[Файл:skeleton_parallel_edges.jpg|300px]]
[[Файл:skeleton_more_complex_event_example3.jpg]]
===== Параллельные "соседние" рёбра =====
[[Файл:skeleton_pce_event_example.jpg]]
Другой интересный случай возникает, когда несоседние параллельные рёбра становятся соседними после исчезания рёбер между ними. Такая проблема называется <tex> \mathrm{PCE} </tex> (''parallel consecutive edge problem''). В таком случае можно поступать по-разному.
* На левом рисунке используется <tex>separate\ rule</tex> {{---}} правило, когда два ребра рассматриваются отдельно. Тогда верно утверждение, что каждому ребру соответствует ровно одна грань. И в этом случае можно считать, что новая вершина на стыке двух рёбер движется перпендикулярно рёбрам.
* На среднем рисунке используется <tex>merge\ rule</tex> {{---}} рёбра в таком случае объединяются в одно новое ребро.
Отличать этот случай от предыдущего можно, посмотрев на ориентацию двух рёбер. Если они направлены в одну сторону, то это <tex> \mathrm{PCE} </tex>, если в противоположную, то разбираемся как в предыдущем случае.
===== Множественные события в одной точке =====
Первая проблема, возникающая в этом случае {{---}} точное определение того, что несколько событий произошли в одной точке. Для определения совпадения нескольких событий в одной точке можно поступать приближённо {{---}} вводить с каждой точкой <tex>\varepsilon</tex>-окрестность и смотреть, не попали ли другие точки в эту окрестноить, {{---}} или использовать [[Интервальная арифметика | более точную арифметику]].
Чтобы научиться разбираться с такими случаями в алгоритме, когда мы уже поняли, что в одной точке будет несколько событий, введём понятие '''обобщённого события пересечения''' (англ. ''GIE'', ''generalized intersection event'').
[[Файл:skeleton_chain1.jpg]]
Для начала введём понятие цепочек рёбер, которые вовлечены в событие. То есть такие рёбра, которые сталкиваются в данном событии. Эти цепи упорядочим согласно направлению рёбер (см. рисунок выше).
[[Файл:skeleton_chain2.jpg]]
Мы можем также упорядочить сами цепи вокруг точки события, объединив эти цепи в один циклический список. Таким образом событие получается как бы окружено списком рёбер, которые участвуют в этом событии, и никакие другие рёбра не участвуют. Можно заметить (рисунки <tex> c,\ d,\ e</tex> выше), что соседние рёбра в списке из изначально разных цепей становятся потом соседними в <tex>\mathrm{LAV}</tex>.
Алгоритм обработки GIE следующий:
* '''Шаг внутри цепи:''' в каждой цепи удаляем внутренние рёбра (кроме первого и последнего) {{---}} это соответствует тому, что исчезает несколько рёбер, участвующих в одном <tex>edge\ event'</tex>е. Таким образом остаются цепи только длин <tex>1</tex> или <tex>2</tex>
* '''Шаг цепи из одного звена:''' цепи длины <tex>1</tex> разбиваются в точке события (это соответствует простому <tex>split\ event'</tex>у). Теперь все цепи имеют длину ровно <tex>2</tex>.
* '''Шаг межцепной:''' соединяем соседние цепи (соответствующие одному событию) в циклический список, то есть соединяя конец одной цепи с началом следующей и так далее. То есть мы разбиваем кажду цепь в середине и получаем новые списки длины <tex>2</tex>.
* '''Шаг циклы из двух рёбер:''' списки <tex>\mathrm{LAV}</tex> длины <tex>2</tex> состоящие из двух параллельных рёбер, то есть ограничивающие полигон нулевой площади, удаляются из <tex>\mathrm{SLAV}</tex>.
* '''Шаг PCE:''' разбираемся с <tex> \mathrm{PCE} </tex> согласно принятому нами правилу решения {{---}} правила слияния или правила разделения.
== Алгоритм построения с помощью Motorcycle graph ==
