Я пытаюсь реализовать триангуляцию многоугольника, используя широко известный алгоритм двухпроходной линии развертки, который подразделяет многоугольник на монотонные подкомпоненты на первом проходе линии развертки, а затем триангулирует эти монотонные компоненты на втором проходе. Моя текущая реализация работает в общем случае, но я не могу, хоть убей, понять, как адаптировать ее для работы с входами, содержащими несколько совпадающих сегментов краев (сегменты с равными координатами x при перемещении слева направо или равные координаты y при движении справа налево).
Изменить: я только что понял, что то, как я сформулировал этот вопрос, делает его довольно длинным и многословным, поэтому вот быстрый TL; DR; для всех, кто знает о многоугольной триангуляции, но не хочет читать все это: является ли следующая форма допустимым входом для 2-го прохода алгоритма триангуляции? Если да: как адаптировать второй проход для обработки этого, если нет: как мне адаптировать 1-й проход так, чтобы он производил монотонные подкомпоненты, которые можно передать во 2-й проход:
http://www.wouterbijlsma.nl/~wouter/tmp/RTdr6rET9.png
Расширенная версия вопроса ниже этого пункта ;-)
Краткое изложение алгоритма:
Первый проход делит входной многоугольник на «монотонные подкомпоненты». Монотонный подкомпонент - это многоугольник, который можно разделить на 2 связанные цепи, координаты которых отсортированы слева направо (когда алгоритм реализован с использованием вертикальной развертки) или сверху вниз (при использовании горизонтальной развертки). линия). Предположим, мы используем вертикальную линию развертки: каждый монотонный подкомпонент затем может быть разделен на верхнюю цепочку и нижнюю цепочку, соединенные в минимальных и максимальных координатах x, а при сканировании вершин любой цепи координаты x равны увеличивается. Если подкомпонент строго мононтонный, верхняя и нижняя цепочки не могут иметь сегменты кромок с идентичными координатами x (то есть: вертикальные сегменты кромок).
Во втором проходе монотонные подкомпоненты удаляются и подразделяются на треугольники, добавляя внутренние ребра. Идея состоит в том, что каждый подкомпонент перемещается слева направо, и в каждой вершине, на которую попадает линия развертки, может произойти одно из двух: а) нетриангулированная область слева от линии развертки может быть триангулирована путем добавления диагоналей, или b) текущая вершина не может «видеть» какую-либо из ранее развернутых, но необработанных вершин в нетриангулированной области слева от линии развертки. В случае б) вершина помещается в стек («цепочка рефлексов»), и по построению в некоторой точке произойдет случай а), и вершины цепочки рефлексов будут выталкиваться одна за другой и соединяться с диагонали до последней вершины линии развертки.
В приведенном выше описании отсутствуют некоторые детали, но я предполагаю, что любой, кто знает, как ответить на мой вопрос, уже понимает алгоритм, поэтому я не буду здесь вдаваться в подробности.
У меня есть следующая проблема: предположим, у меня есть многоугольник, представляющий стрелку, указывающую влево, например так:
http://www.wouterbijlsma.nl/~wouter/tmp/RTdr6rET9.png
Когда я ввожу эту фигуру в свой алгоритм, проход монотонного подразделения оставляет фигуру нетронутой: в ней есть вертикальные края, поэтому она не строго монотонная, но монотонная, и, насколько я понимаю, алгоритм, его не нужно разделять, прежде чем вы сможете его триангулировать (возможно, здесь я ошибаюсь, потому что мое предположение неверно).
Теперь предположим, что я передаю (немодифицированный) многоугольник стрелки во второй проход для его триангуляции. Что делать с двумя вертикальными кромочными сегментами в основании наконечника стрелки? Алгоритм развертки линии требует, чтобы вершины многоугольника были отсортированы слева направо, поэтому можно предположить, что ответ сводится к тому, как сортировать вершины с одинаковыми координатами x (например, в цепочке, или по координате y, или по индексу границы многоугольника), но какую бы сортировку я ни использовал, триангуляция всегда терпит неудачу.
Назовем крайнюю левую вершину вершиной 0 и упорядочим вершины против часовой стрелки. Это означает, что 4 вершины основания стрелки - это вершины 1, 2, 5 и 6. У нас есть три варианта сортировки:
В некоторых исходных материалах, которые я использовал для реализации алгоритма, говорится: «Сортировать вершины с равными координатами x при увеличении координат y», то есть: 1, 2, 5, 6. Если я сделаю это и разверну их, первый треугольник выйдет нормально ( 0, 1, 2), но после этого алгоритм добавит ребро (5, 2), что создаст компонент с 4 вершинами (0, 2, 5, 6). Ребро (0, 5) не добавляется, потому что алгоритм триангуляции предписывает добавление ребер ко всем предыдущим нетриангулированным вершинам рефлексной цепочки кроме первой (изменение этого параметра нарушит общий случай). Хотя область многоугольника, ограниченная четырьмя вершинами, имеет треугольную форму, очевидно, что это не треугольник, потому что он имеет 4 точки, а также не является допустимым многоугольником по большинству определений, поскольку имеет коллинеарные края.
В другой статье, которую я прочитал, говорится: «Разорвите связи так, чтобы порядок цепочки сохранился». Это означало бы, что 4 вершины в моем примере будут отсортированы 1, 2, 6, 5, поскольку и нижняя, и верхняя цепочки идут слева направо. Если я просканирую их в этом порядке, я снова получу треугольник (0, 1, 2), но следующая просканированная вершина (6) создаст многоугольник (0, 1, 6), что еще хуже, чем в первом случае, потому что он создает ребро (1, 6), которое проходит через вершину 5, но не содержит ее. Сдвиг вершины 5 полностью испортит состояние алгоритма, потому что он создаст вырожденный треугольник (1, 5, 6), линию, а смахивание хвостовых вершин не сможет триангулировать оставшуюся часть многоугольника.
Сортировка в исходном порядке вершин многоугольника (по границе, против часовой стрелки): в этом случае результат будет тот же, что и в случае 1), то есть: 1, 2, 5, 6, что уже было показано как неудачное.
Я начинаю думать, что, возможно, такую форму стрелки следует рассматривать как немонотонную, или (хотя я никогда не видел, чтобы это упоминалось ни в одном описании алгоритма), алгоритм монотонной триангуляции требует, чтобы входные данные были строго монотонный. Может быть, это то, что мне не хватает? И если да, то как мне адаптировать проход монотонного подразделения для работы с (множественными, совпадающими) вертикальными сегментами кромок? Исходный материал, который я использовал, классифицирует все вершины как 'начало', 'конец', 'слияние', 'разделение' или 'регулярный' (нижний / верхний) во время подразделения, но в случае вертикального сегмента эти классификации неоднозначны: согласно Согласно определению этих классов вершин, вершинная часть вертикального сегмента может рассматриваться как начальная / конечная вершина, но также как вершина разделения или слияния. Или, может быть, мне действительно придется отсортировать 4 вершины по их y-координатам, затем создать недопустимый компонент треугольника с 4 вершинами и 2 коллинеарными ребрами, а затем `` исправить это '', удалив вершину на коллинеарные края?
Основным источником, который я использовал для реализации алгоритма, является оригинальная статья GJPT-78, в которой был представлен алгоритм триангуляции, он не является общедоступным (платный доступ), поэтому я не могу связать его здесь, но в Интернете доступно множество материалов курса CS, которые описывают алгоритм, я также использовал их, например:
http://www.cs.ucsb.edu/~suri/cs235/Triangulation.pdf https://www.cs.umd.edu/class/spring2012/cmsc754/Lects/cmsc754-lects.pdf (см. главу "Лекция 6")
Я прочитал довольно много из них. Почти в каждом наборе слайдов, статей, блогов или любого другого описания алгоритма конкретно упоминаются вершины с равными x-координатами (или y-координатами, если используется горизонтальная развертка), но они все просто говорят «мы не предполагаем равных x-координат» и что это ограничение «легко исправить и служит только для упрощения представления» или «не является фундаментальным для алгоритма» или что-то еще. Как ни странно, никто не заботится о подробностях необходимых изменений или обходных путей для поддержки этого случая, или они содержат нечеткое утверждение о сортировке равных x-вершин каким-либо образом, что на практике не решает проблему.
Может быть, я просто немного глуп или упускаю что-то действительно очевидное, но я бездельничал, пытаясь исправить этот угловой случай уже несколько дней без результата, и это начинает действительно разочаровывать. Я предполагал реализовать алгоритм для базового случая (который включает в себя написание структуры данных DCEL, алгоритма линии развертки, отсортированной карты краев, тригонометрии, необходимой для определения внутренних углов и видимости, структур данных для эффективного хранения и поиска классификаций вершин и т. Д. ) было бы почти всей работой, и исправить проблему вертикального края впоследствии было бы тривиально. Прямо сейчас я потратил больше времени, пытаясь исправить вертикальные края, чем на все остальное, что мне нужно, чтобы заставить алгоритм работать для общего случая вместе взятого (он отлично работает для любого многоугольника, который я бросаю на него, если он не работает) t имеют вертикальные края).
Спасибо! Воутер
