1

Есть задача: разбить самопересекающийся многоугольник на части без самопересечений. Проблему нахождения всех точек пересечения я решил: полным перебором. Знаю, что есть алгоритм Бентли-Оттмана, но мне легче было написать полный перебор, так как не нашел хорошего полноценного описания алгоритма на русском языке.

Вопрос сейчас такой: что мне дальше делать с этими точками? Есть ли какой-то способ, зная эти точки, разбить теперь мой многоугольник? Знаю про способ (по этой ссылке в заголовке "Decompose into Simple Pieces"), при котором это делается с каждым шагом алгоритма Бентли-Оттмана, есть ли какой-то способ сделать аналогично в моем случае? Или все-таки придется разбираться с алгоритмом Бентли-Оттмана? Если да, то, возможно, у кого-то есть хорошее понятное полноценное описание этого алгоритма на русском языке?

2
  • 1
    Вы могли бы проиллюстрировать свой вопрос? Т.е. о каких конкретно многоугольниках и самопересечениях идет речь. Также, решение нужно общее, или ваше условие несколько "стандартизировано" и допускает некоторые упрощения/допущения?
    – Kromster
    12 мая 2020 в 5:01
  • Иллюстрации есть по ссылке, решение нужно общее
    – Arzybek
    13 мая 2020 в 1:42

1 ответ 1

2

Если задача не состоит в том, чтобы всё сделать самостоятельно, посмотрите, что умеет Clipper (Delphi, C++, C# и некоторые другие языки). Работа этой библиотеки основана на алгоритме Vatti.

Функция SimplifyPolygon, похоже, делает то, что Вам требуется

введите сюда описание изображения

введите сюда описание изображения

2
  • Задача состоит в том, чтобы делать все самостоятельно как раз
    – Arzybek
    13 мая 2020 в 1:42
  • Библиотека в исходниках, можно подсмотреть, как это делается.
    – MBo
    13 мая 2020 в 6:10

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.