У нас есть несколько полилиний (список точек, имеет начальную и конечную точки, а не циклические) и многоугольники (список точек, циклические, нет такой вещи, как конечные точки).
Мы хотим отобразить каждую ломаную линию на новую ломаную линию, а каждый полигон - на новый многоугольник, чтобы общее число ребер было достаточно маленьким.
Скажем, изначально число ребер равно N, и мы хотим, чтобы в нашем результате было M ребер. N намного больше, чем M.
Полилинии должны сохранять свои начальную и конечную точки, поэтому они вносят как минимум 1 ребро, на один меньше, чем их число вершин. Полигоны должны быть полигонами, поэтому они вносят как минимум 3 ребра, равные их числу вершин. М будет по крайней мере достаточно большим для этого требования.
Выходы должны быть как можно ближе к входам. Это в конечном итоге станет проблемой оптимизации, заключающейся в минимизации некоторой метрики с небольшим допуском к истинному оптимальному решению. Первоначально я бы использовал область симметричной разности оригинала и результата (область между), но если это облегчит другая метрика, я с радостью воспользуюсь этим.
Это нормально, если результаты включают только вершины в оригинале, подгонка будет немного хуже, но может потребоваться уменьшить сложность времени.
Поскольку я запрашиваю алгоритм, было бы неплохо также увидеть реализацию. Скорее всего, мне придется заново реализовать его там, где я буду его использовать, поэтому детали, такие как язык или структуры данных, не будут иметь большого значения.
Что касается того, насколько хорошим должно быть приближение, о том, что вы ожидаете получить от векторного изображения из растрового изображения. Фактически здесь используется инструмент для игры, хотя есть некоторые странные детали для конкретной игры, поэтому количество выходных фронтов фиксировано, а не допуск.
Довольно сложно найти какую-либо информацию о подобных вещах, поэтому, даже не предоставив полностью работоспособного алгоритма, очень хотелось бы получить несколько указателей.