Отсечение вогнутой линии многоугольника без вырожденных ребер

В последние дни я искал и исследовал Интернет, чтобы найти подходящий метод для моей проблемы.

Проблема:

Обрежьте вогнутый многоугольник по бесконечной линии без направления (на самом деле это многоугольник по плоскости в 3D, но проблема аналогична, я думаю). В настоящее время я использую Sutherland-Hodgman, но получающиеся полигоны иногда содержат части с нулевой площадью, созданные из вырожденных ребер, а также не поддерживают полигоны, содержащие дыры.

Лучший алгоритм, который я нашел, который мог бы решить мою проблему, - это алгоритм Вейлера-Атертона, но он предназначен для отсечения многоугольника с ребрами по часовой стрелке, и все, что у меня есть, - это бесконечная линия (в 3D-плоскости) с отсутствующей информацией о направлении.

Вопрос:

Есть ли алгоритм для обрезки вогнутого многоугольника, который соответствует моим потребностям, или у кого-нибудь есть предложение о том, как изменить алгоритм Вейлера-Атертона для работы в этом случае? Есть веб-страницы, которые предполагают, что его можно обобщить для поддержки большего количества случаев, но я не могу понять это.

//С уважением Эйкен


clipping 3d polygon graphics concave
person Eiken    schedule 07.10.2010    source источник

Ответы (2)


arrow_upward
3
arrow_downward

Нашел подходящий алгоритм в Graphic Gems V, который решает мою проблему. Если у кого-то такая же проблема, вот ссылка:

Гласснер, А., «Отсечение вогнутого многоугольника», в Graphics Gems V, A. Paeth, ed., Academic Press, Cambridge, 1995.

person Eiken    schedule 09.10.2010

arrow_upward
1
arrow_downward

Чтобы решить эту проблему, вы можете использовать полигональный клиппер*, преобразовав линию в обтравочный полигон. Предполагая, что вы не выполняете отсечение в почти горизонтальной плоскости, просто убедитесь, что критический (обрезной) край многоугольника отсечения немного больше, чем вертикальные размеры многоугольника объекта (т. е. край простирается выше и ниже многоугольника объекта). При обрезке почти в горизонтальной плоскости убедитесь, что критический край немного шире объекта.

*например, Clipper — http://sourceforge.net/projects/polyclipping/

Раскрытие информации: я автор Clipper, так что возможны личные предубеждения.

person Angus Johnson    schedule 07.10.2010
comment
Да, я пытался найти хороший способ сделать это. Мой многоугольник, находящийся в трехмерном пространстве, затрудняет решение о том, как преобразовать линию в подходящий многоугольник, поскольку многоугольник объекта может быть повернут странно, что затрудняет решение, в каком направлении от линии (которую я получаю от пересечения плоскости/плоскости) к расширить полигон. - person Eiken; 08.10.2010
comment
Я предполагаю, что вы можете определить линию отсечения в 2D-пространстве. Если его абсолютный наклон меньше 1 (т. е. приближается к горизонтали), то сегмент линии отсечения (и одно ребро вашего многоугольника отсечения) должен выходить за левую и правую границы многоугольника объекта. Другие ребра можно выровнять по осям, просто убедившись, что горизонтальный край находится выше (или ниже) экстента многоугольника объекта. Аналогичным образом, если абсолютный наклон линии отсечения больше 1, используйте ту же логику, но поверните ее на 90 градусов. - person Angus Johnson; 08.10.2010
comment
Да, это будет работать в основном по той же теории, что и алгоритм, который я нашел в Graphic Gems V, за исключением того, что он еще более упрощен для именно того, что я хочу сделать, и я могу пропустить шаг представления моей плоскости в виде линии. Тем не менее спасибо за ваш ответ. Stackoverflow — удивительный ресурс. - person Eiken; 09.10.2010