Оптимизация векторного изображения путём удаления избыточных вершин и наложения фигур
Мне надо оптимизировать векторное изображение, построенное с помощью кривых Безье. Изображение на входе, и как оно выглядит, если сдвинуть фигуры:
Я хочу оптимизировать изображение, удалив ненужные линии и полагаясь на наложение фигур, чтобы изображение выглядело так же, но с меньшим числом вершин. Как изображение должно выглядить на выходе:
Я так понимаю, проблему можно разбить на несколько частей:
Найти наложенные друг на друга линии. Это более-менее понятно: вычислять точки по траектории кривой, искать вершины на одной линии. Если вершины точно совпадают, то задача становится тривиальной.
Найти срезанные пути сквозь другие фигуры. Скорее всего, алгоритм для этого существует, но я про него не в курсе. (Здесь мне реально нужна помощь.) Также неясно, сквозь какие фигуры надо искать пути. Полагаю, надо рассмотреть все возможности и сравнить. Наверняка станет яснее, когда я приступлю к делу. (Не откажусь от подсказок/предложений.)
Найти оптимальный порядок наложения фигур, чтобы количество вершин было минимальным. Для нуба в алгоритмах вроде меня алгоритм не очень ясен, но это пахнет какого-то рода минимизацией значения и поиска оптимального "маршрута" к минимальному значению, так что как-нибудь справлюсь. (Поправьте, если я неправ.)
Если в фигуре дырка, скорее всего, это означает, что всё внутри должно быть наложено сверху, так что это простой случай с минимумом вычислений.
В общем и целом, больше всего вопросов относительно пункта (2), поэтому именно в нём мне нужен пинок в нужном направлении.
В терминах изображений выше, как найти кривую Безье для потенциально скрытой внизу части зелёной фигуры через синюю фигуру (и опционально через жёлтую тоже) и наоборот, как как найти кривую Безье для потенциально скрытой внизу части синей фигуры через зелёную фигуру? Путь не обязательно должен быть кратчайшим, важно только то, что в нём наименьшее число вершин.
Собственно, мне надо найти очерченные ниже пути в виде кривых Безье с минимальным числом вершин. Всё остальное можете считать бесполезным контекстом.
