Wataru, mayton2019, Есть некоторый промежуточный результат, который требуется получить. Надеюсь это прояснит вопрос, хотя результат немного и отличается от исходного вопроса.
Осталось обработать несколько пограничных случаев для завершения задачи.
Идея получилась:
Результат - розовая область. Количество faces совпало, индексы совпали. То, что нужно. И считать уже не надо. Чистая топология. Надо ещё тестировать и пару редких случаев добавить, но ведь работает!
>> я не понимаю при чем здесь фигура Straight Skeleton? Каким образом это меняет задание?
По сути получается, что многоугольник не произвольный. А значит у него появляются дополнительные свойства, которые можно использовать, чтобы получить результат без рассчётов. Это было неясно в самом начале пути.
>> Шикин и Боресков - Компьютерая Графика
Вообще не подходит.
>> Алгоритмы машинной графики и обработки изображений
Там есть на с. 344 некоторая отдалённая информация о похожей задаче, но там она описана в общем туманном виде и для решения не подходит. Там разрезание произвольного многоугольника одной линией и требуются вычисления. У меня разрезание не произвольного многоугольника и не одной линией, а двумя, при том, что все пересечения уже вычислены. Так что отпадает. Всегда есть нюансы.
>>Можно вращать. Если это приносит пользу для алгоритма.
Рассчёты пересечений уже сделаны. Дальнейшие вращения и трансформации не нужны.
>>Напитайся правильной терминологией. Там и алгоритмы описаны и подходы.
Если что-то советуете, то лучше давайте ссылки. Так-то для меня это рандомные чуваки. У меня по первой фамилии просто футболист вывалился. Поэтому дальше даже не смотрел. А алгоритм Straight Skeleton - большая редкость, вряд ли в этой области есть устоявшаяся терминология.
Wataru, Кроме наклонных горизонтальные тоже случаются и да, это тонкий момент. Но алгоритм, который считает пересечения, похоже их пропускает. Но такая пропущенная линия, скорее всего, воспримется как точка без пересечения и тогда я её учту как точку, которая либо не дошла до пересечения, либо находится за пересечением. Точнее пока сказать не могу, будет понятно позже.
>>Про + и - оффсеты не понял
"+" все offset-ы строятся только внутри исходного объекта.
"-" это внешняя область, полученная дополнительным построением по алгоритму Exterior Straight Skeletons and Exterior Offset Co..., чтобы иметь возможность делать offset-ы с отрицательными значениями, вне исходного объекта. Т.е. это не произвольное дополнение. Я не сказал об этом раньше, но не умышленно, а не понимал, что это важно и думал, что можно будет обойтись каким-то общим способом на произвольном многоугольнике. Не прокатило.
Пример соотношения зон и, заодно обзор задачи, так сказать, с высоты птичьего полёта. Высокополигональная фигура из многих мелких отрезков (для увеличения - откройте в отдельном tab):
И вот на каждый такой многоугольник и нужно разбить на отдельные полигоны по offset-ам. Работы много и чем меньше рассчётов, тем лучше.
>> Или пересекаете с несколькими прямоугольниками?
В итоге надо пересечь с несколькими, но делать это нужно по одному прямоугольнику, последовательно.
mayton2019, (почти синхронно), очень близко, с учётом того, что я не совсем корректно составил исходное условие, но мне понравилось, что вы уловили суть! гляньте мой коммент ниже
Wataru, Я ещё раз подумал и оказалось, что я не совсем корректно описал исходные данные в вопросе. Есть следующие проблемы:
Я, конечно, говорил о "горизонтальных линиях", но это не совсем правда. Они параллельные, а фигура может встретится в совершенно произвольном положении, например:
И хоть я и знаю координаты пересечений и точек, но визуальный "угол" поворота мне известен только косвенно. Вращать туда-обратно фигуры нельзя - любая операция вращения/трансформации - влияние на точность, да и на производительность (это помимо самой операции рассчёта)
Теперь о некотором дополнительном анализе реального объекта. Пример одной такой грани (сама фигура - Straight Skeleton - очень интересный объект):
Мысленно нужно добавить ещё два offset - ниже "-" и выше "+". У такой фигуры возможны такие варианты выбора плоскостей между двумя любыми offset:
1. Выбраны два offset в минусе
2. Выбраны два offset в плюсе
3. один offset в плюсе, другой в минусе (даже если каждый сильно больше и + и -).
4. Один offset больше + или меньше -
5. Оба offset за пределами - или за пределами +.
0-0 и есть та самая "горизонтальная" линия. Если внимательно посмотреть по отдельности на свойства offset-ов в + и в -, то у них обнаруживается одно интересное свойство - ближайшая линия к 0-0 всегда является неразрывным основанием в то время как следующий offset может дробиться даже несколько раз.
1,2. Например, если нужно получить результат offset2-offset1 (а я всегда знаю какой из них ближе к 0-0), то количество faces будет равно количеству линий offset2 - 2 шт. При том, что то, что я получу по offset1 - это будет неразрывная ломаная на каждом из двух оснований из offset2. Тоже самое касается и положительной "зоны".
3. Если один offset в +, а другой в -, например, offset8 и offset2, то они будут ВСЕГДА одной фигурой (т.к. 0-0 никогда не разрывается) и достаточно просто обойти контур, отбрасывая всё, что за пределами offset8-2.
Остальные варианты 4-5 рассматриваются аналогично 3 и там либо один обход и получение одной фигуры, либо прямое отсутствие результата.
получается, что такую исходную фигуру "разрезать" между любыми двумя offset с уже полученными точками пересечений offsets можно топологически, без рассчётов. (Результат я пока не воплотил, буду работать над ним, как получу - выложу)
Wataru, Простите, не хочу создавая впечатление, что сомневаюсь в вашем решении. Я рассуждал примерно как вы, поэтому согласен. Задача более широкая и объёмная, поэтому надо аккуратно стыковать решение. К тому же я случайно обнаружил, что ещё и не все условия выполнил, о которых написал в начальном условии, а только казалось, что их выполнил. Сейчас стал проверять и чуть не стал рвать на себе волосы, что не проверил. ) Сейчас все указанные условия выполнены. В целом более высокий уровень по задаче такой - (одна плоскость - это часть общей схемы разрезания смежных плоскостей) https://github.com/user-attachments/assets/680e827...
(Но и это ещё не вся задача)
В принципе вы правы. Мне даже известно направление обхода и направление пересечений (чтобы избежать использование формул), но вот как-то не складывается в один пазл. Буду думать дальше.
res2001,
В итоге получилось почти как и задумывал вначале, только оказалось, что для указания библиотек Boost есть стандартная переменная BOOST_LIBRARYDIR. Теперь команда сборки проекта выглядит одинаково и для Linux и для Windows и для MacOS:
Дмитрий,
>>Делай как написано в документации буста и cmake и всё заработает
У меня устойчивое впечатление, что вы не вникли в суть вопроса. Так-то у меня и без вашего совета всё собирается и работает на разных платформах. Потрудитесь вникнуть в суть вопроса или займитесь другими делами.
res2001,
> то сделайте каталог с бустом субмодулем в git
Хотелось бы какой-то метод, типа передачи переменной из консоли (-DVAR=PATH), но чтобы проверить, что необходимая библиотека присутствует, а если нет, то как-то сообщить пользователю, что нужно для её получения.
Дмитрий,
>С чего это азио не кроссплатформенный?
Вы правы, он-то кроссплатформенный, только я ещё дописал, что он используется для многоточных вычислений, а это требует ещё и компонета thread, который не является кроссплатформенным:
LINK : fatal error LNK1104: cannot open file 'boost_thread-vc143-mt-x64-1_85.lib'
Поэтому без сборки boost не обойтись. Немного не точно написал.
res2001,
> В винде можно использовать vcpkg для MSVC или pacman в msys2 или что-то еще.
Нене, сборка не должна быть частью системы. Используются MSVC на Win и gcc на Linux, Остальные зависимости удалось нормально исключить, чтобы не сохранять к ним привязку. Скажем так, я использую только boost и остальные зависимости в проекте не нужны даже для сборки. Проект собирается в статическую библиотеку. BOOST собирается без проблем двумя командами и на windows и на Linux. В данный момент после сборки проекта вообще не остаётся никаких следов в системе. Нужно, чтобы так и осталось.
Ivan Ustûžanin,
>>используйте auto и make_shared()
Мне auto тоже нравится, это пока для целей тренировки и запоминания объектов библиотеки, чтобы лучше названия запомнить, которыми приходится оперировать.
Осталось обработать несколько пограничных случаев для завершения задачи.